Теоремы существования и быстрые алгоритмы для задач справедливого дележа

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