Семинар Добрушинской лаборатории

Когда: вторник 27 мая, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Олег Мусин (University of Texas Rio Grande Valley),
"Теоремы существования и быстрые алгоритмы для задач справедливого дележа / Existence theorems and fast algorithms for fair division problems"

У известной проблемы справедливого дележа — долгая история. У этой задачи имеется множество форм и она возникает в многочисленных жизненных ситуациях. В этом докладе я рассмотрю теоремы существования для задач справедливой аренды и разрезания торта, а также обобщения этих теорем.

Вторая часть доклада — это совместная работа, которая была мотивирована публикацией в New York Times: "To Divide the Rent, Start With a Triangle" by Albert Sun (April 28, 2014)", к которой прилагается калькулятор для справедливой аренды, основанный на работе Фрэнсиса Су. В недавно опубликованной статье мы рассматриваем алгоритмическую сложность задач справедливого дележа и минимизацию количества запросов необходимых для нахождения приближенного решения с желаемой точностью. Для нескольких классов задач справедливого дележа показано, что при определенных естественных условиях на множествах предпочтений достаточно логарифмического количества запросов относительно точности.

#ВШМ_Добрушинский