Ярмарка разрезания торта

Справедливое разрезание торта — это своего рода проблема справедливого дележа . Проблема связана с гетерогенным ресурсом, таким как торт с разными начинками, который считается делимым — его можно разрезать на сколь угодно маленькие кусочки, не теряя при этом их ценности. Ресурс необходимо разделить между несколькими партнерами, которые имеют разные предпочтения в отношении разных частей торта, т. е. кто-то предпочитает шоколадную начинку, кто-то предпочитает вишню, а кто-то просто хочет кусок как можно большего размера. Разделение должно быть единогласно справедливым: каждый должен получить часть, которая считается справедливой долей.

«Торт» — это всего лишь метафора ; процедуры справедливого разрезания торта могут использоваться для разделения различных видов ресурсов, таких как земельные участки, рекламные площади или время вещания.

Прототипом справедливого разрезания торта является «разделяй и выбирай» , который упоминается в книге Бытия для разрешения конфликта Авраама и Лота . Эта процедура решает проблему справедливого дележа двух человек. Современное исследование справедливого разрезания торта началось во время Второй мировой войны , когда Хьюго Штайнхаус попросил своих учеников Стефана Банаха и Бронислава Кнастера найти обобщение принципа «разделяй и выбирай» для трех или более человек. Они разработали последнюю процедуру уменьшения . ^[1] Сегодня честное разрезание торта является предметом интенсивных исследований в области математики , информатики , экономики и политологии . ^[2]

Предположения [ править ]

Существует торт C , который обычно считается либо конечным 1-мерным сегментом, 2-мерным многоугольником или конечным подмножеством многомерной евклидовой плоскости R. ^д.

Имеется n с субъективными функциями ценности над C. людей У каждого человека i есть функция ценности Vi _, которая отображает подмножества C в числа. Все функции цены предполагаются абсолютно непрерывными относительно длины, площади или (вообще) меры Лебега . ^[3] Это означает, что нет «атомов» — нет особых точек, которым один или несколько агентов присваивают положительное значение, поэтому все части торта являются делимыми. Во многих случаях функции цены предполагаются сигма-аддитивными (ценность целого равна сумме значений его частей).

C необходимо разделить на n непересекающихся подмножеств, так чтобы каждый человек получил непересекающееся подмножество. Часть, выделенная человеку i, называется $X_{i}$ , и $C=X_{1}\sqcup \cdots \sqcup X_{n}$ .

Русские люди на C. имеют равные права Т.е. нет спора о правах людей – все согласны с тем, что все остальные имеют право на справедливую долю. Единственная проблема заключается в том, как разделить пирог так, чтобы каждый получил справедливую долю.

В следующих примерах в качестве иллюстрации будет использоваться следующий торт.

Торт состоит из двух частей: шоколадной и ванильной.
Есть два человека: Алиса и Джордж.
Алиса оценивает шоколад как 9, а ваниль как 1.
Джордж оценивает шоколад на 6, а ваниль на 4.

Требования правосудия [ править ]

Пропорциональность [ править ]

Оригинальным и наиболее распространенным критерием справедливости является пропорциональность (ПР). При пропорциональном разрезании торта каждый получает кусок, который он оценивает как минимум в 1/ n от стоимости всего торта. В примере с тортом пропорционального деления можно добиться, отдав всю ваниль и 4/9 шоколада Джорджу (по стоимости 6,66), а остальные 5/9 шоколада Алисе (по стоимости 5). ). В символах:

\forall {i}:\ V_{i}(X_{i})\geq 1/n

Для n людей с аддитивными оценками всегда существует пропорциональное деление. Наиболее распространенными протоколами являются:

Последний уменьшитель — протокол, который может гарантировать, что n частей соединены (т. е. ни один человек не получит набор из двух или более несвязных частей). В частности, если торт представляет собой одномерный интервал, то каждый человек получает интервал. Этот протокол дискретен и может воспроизводиться по очереди. Для этого требуется O( n ²) действия.
Процедура Дубинса-Спаньера с подвижным ножом представляет собой непрерывную версию уменьшителя Ласта. ^[4]
Протокол Финка (также известный как последовательные пары или одиночный выбор ) — это дискретный протокол, который можно использовать для онлайн-разделения: при пропорциональном разделении для n — 1 партнеров, когда в партию входит новый партнер, протокол изменяет существующее разделение так, что и новый партнер, и существующие партнеры остаются с 1/ n . Недостаток в том, что каждый партнер получает большое количество несвязных частей.
Протокол Эвена-Паза , основанный на рекурсивном разделении торта и группы агентов пополам, требует всего O( n log n ) действий. Это самый быстрый из возможных детерминированных протоколов пропорционального деления и самый быстрый из возможных протоколов пропорционального деления, который может гарантировать, что части соединены.
Протокол Эдмондса-Пруса — это рандомизированный протокол, который требует всего O( n ) действий, но гарантирует лишь частично пропорциональное деление (каждый партнер получает как минимум 1/ an , где a — некоторая константа), и он может дать каждому партнеру набор «крошки» вместо единого связного куска.
Протокол о разделе земли Бека может привести к пропорциональному разделу спорной территории между несколькими соседними странами, так что каждая страна получает долю, которая одновременно связана и примыкает к ее нынешней территории.
Протокол суперпропорционального дележа Вудалла обеспечивает деление, которое дает каждому партнеру строго больше 1/ n , при условии, что по крайней мере два партнера имеют разные мнения о стоимости хотя бы одной части.

см. в разделе «Пропорциональное разрезание торта» Более подробную информацию и полные ссылки .

Критерий пропорциональности можно обобщить на ситуации, в которых права людей не равны. Например, при пропорциональном разрезании торта с различными правами торт принадлежит акционерам, так что одному из них принадлежит 20%, а другому — 80% торта. Это приводит к критерию взвешенной пропорциональности (WPR):

\forall i:V_{i}(X_{i})\geq w_{i}

Где w _i — веса, сумма которых равна 1.

Свобода от зависти [ править ]

Еще один распространенный критерий — отсутствие зависти (EF). При разрезании торта без зависти каждый получает кусок, который он ценит не меньше, чем любой другой кусок. В символах:

\forall i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})

В некоторых случаях существуют подразумеваемые отношения между пропорциональностью и отсутствием зависти, как показано в следующей таблице:

Агенты	оценки	ЭФ подразумевает пиар?	PR подразумевает EF?
2	добавка	Да	Да
2	общий	Нет	Нет
3+	добавка	Да	Нет
3+	общий	Нет	Нет

Протокол «разделяй и выбирай» находит распределение, которое всегда равно EF. Если функции стоимости аддитивны, то это деление также является PR; в противном случае пропорциональность не гарантируется.

Подразделение EF для n человек существует даже в том случае, если оценки не аддитивны, при условии, что они могут быть представлены как последовательные наборы предпочтений. Деление EF изучалось отдельно для случая, когда части необходимо соединить, и для более простого случая, когда части можно разъединить.

Для связных частей основными результатами являются:

Процедура Стромквиста с перемещением ножей обеспечивает разделение на 3 человек без зависти: каждому из них дается нож и им предлагается непрерывно перемещать ножи по торту заранее заданным образом.
Протокол Симмонса может дать приближенное разделение без зависти для n человек с произвольной точностью. Если функции стоимости аддитивны, то деление также будет пропорциональным. В противном случае разделение все равно будет свободным от зависти, но не обязательно пропорциональным. Алгоритм дает быстрый и практичный способ решения некоторых проблем справедливого дележа. ^[5]^[6]

Оба эти алгоритма бесконечны: первый непрерывен, а сходимость второго может занять бесконечное время. Фактически, ни один конечный протокол не может обеспечить свободное от зависти разделение связных интервалов на 3 и более человек.

Для возможно несвязных частей основные результаты таковы:

Дискретная процедура Селфриджа-Конвея обеспечивает деление без зависти для 3 человек с использованием не более 5 сокращений.
Процедура перемещения ножей Брамса-Тейлора-Цвикера позволяет без зависти разделить 4 человека, используя не более 11 разрезов.
Реентерабельный вариант протокола Last Diminisher находит аддитивное приближение к разделению без зависти в ограниченном времени. В частности, для каждой константы $\epsilon >0$ , он возвращает деление, в котором стоимость каждого партнера равна как минимум наибольшему значению минус $\epsilon$ , во времени $O(n^{2}/\epsilon )$ .
Три разные процедуры, одна предложенная Брамсом и Тейлором (1995) , другая Робертсоном и Уэббом (1998) людей без зависти и одна Пихурко (2000), приводят к разделению n . Оба алгоритма требуют конечного, но неограниченного числа разрезов.
Процедура Азиза и Маккензи (2016) ^[7] находит свободное от зависти разделение для n человек по ограниченному числу запросов.

Отрицательный результат в общем случае гораздо слабее, чем в связном. Все, что мы знаем, это то, что каждый алгоритм деления без зависти должен использовать как минимум Ω( n ²) запросы. Существует большой разрыв между этим результатом и сложностью выполнения самой известной процедуры.

см. в разделе «Разрезание торта без зависти» Более подробную информацию и полные ссылки .

Другие критерии [ править ]

Третий, менее распространенный критерий – это справедливость (EQ). При справедливом разделе каждый человек имеет одинаковую ценность. В примере с тортом справедливого разделения можно добиться, раздав каждому половину шоколада и половину ванили, так что каждый человек получит ценность 5. В символах:

\forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})

Четвертый критерий – точность . Если право каждого партнера i равно w _i , то точным разделением является разделение, в котором:

\forall {i,j}:\ V_{i}(X_{j})=w_{j}

Если все веса равны (1/ n ), то деление называется совершенным и:

\forall i,j:\ V_{i}(X_{j})=1/n

Геометрические требования [ править ]

В некоторых случаях фигуры, распределяемые между партнерами, должны не только быть справедливыми, но и удовлетворять некоторым геометрическим ограничениям.

Наиболее распространенным ограничением является возможность подключения . Если «торт» представляет собой одномерный интервал, это означает, что каждый кусок также является интервалом. Если торт представляет собой одномерный круг («пирог»), это означает, что каждый кусок представляет собой дугу; см. честную нарезку пирога .
Еще одним ограничением является смежность . Это ограничение касается случая, когда «пирог» представляет собой спорную территорию, которую приходится делить между соседними странами. В этом случае может потребоваться, чтобы участок, выделенный каждой стране, примыкал к ее нынешней территории; это ограничение решается задачей Хилла о разделе земли .
При разделе земли часто существуют двумерные геометрические ограничения, например, каждый участок должен представлять собой квадрат или (в более общем смысле) толстый объект . ^[8]

Процедурные требования [ править ]

Помимо желаемых свойств конечных разделов, существуют также желаемые свойства процесса деления. Одним из таких свойств является правдивость (она же совместимость стимулов ), которая бывает двух уровней.

Слабая правдивость означает, что если партнер раскрывает алгоритму свою истинную меру стоимости, он гарантированно получит свою справедливую долю (например, 1/ n стоимости всего торта в случае пропорционального деления), независимо от того, что делают другие партнеры. . Даже если все остальные партнеры составят коалицию с единственной целью навредить ему, он все равно получит свою гарантированную долю. Большинство алгоритмов разрезания торта правдивы в этом смысле. ^[1]
Сильная правдивость означает, что ни один партнер не получит выгоды от лжи. То есть говорить правду – это доминирующая стратегия . Большинство протоколов разрезания торта не совсем правдивы, но некоторые правдивые протоколы были разработаны; см. правдивое разрезание торта .

Еще одним свойством является симметрия : не должно быть разницы между разными ролями в процедуре. Было изучено несколько вариантов этого свойства:

Анонимность требует, чтобы при перестановке агентов и повторном выполнении процедуры каждый агент получал точно такой же фрагмент, как и при исходном выполнении. Это сильное условие; на данный момент анонимная процедура известна только для двух агентов.
Симметрия требует, чтобы при перестановке агентов и повторном выполнении процедуры каждый агент получал то же значение , что и при исходном выполнении. Это слабее, чем анонимность; в настоящее время известна симметричная и пропорциональная процедура для любого числа агентов, требующая O( n ³) запросы. Известна симметричная и независтливая процедура для любого числа агентов, но она занимает гораздо больше времени – требуется n ! выполнение существующей процедуры без зависти.
Аристотелианство требует, чтобы, если два агента имеют одинаковую меру стоимости, они получали одинаковую ценность. Это слабее, чем симметрия; оно удовлетворяется любой процедурой, свободной от зависти. Более того, аристотелева и пропорциональная процедура известна для любого числа агентов и занимает O( n ³) запросы.

см. в разделе «симметричное разрезание торта» Подробности и ссылки .

Третья группа процедурных требований — это монотонность : когда процедура деления повторно применяется с меньшим/большим пирогом и меньшим/большим набором агентов, полезность всех агентов должна измениться в одном и том же направлении. см . в разделе «Монотонность ресурса» Подробнее .

Требования к эффективности [ править ]

Помимо справедливости принято учитывать и экономическую эффективность деления; см. эффективное разрезание торта . Существует несколько уровней эффективности:

Более слабое понятие – эффективность по Парето . Этого можно легко удовлетворить, просто отдав весь торт одному человеку; задача состоит в том, чтобы удовлетворить его в сочетании со справедливостью. См . «Эффективное разделение без зависти» .
Более сильное понятие — утилитарная максимизация — максимизация суммы полезностей. (УМ). Когда функции стоимости аддитивны, существуют подразделения единой системы обмена сообщениями. Интуитивно, чтобы создать подразделение UM, мы должны отдать каждый кусок пирога тому, кто ценит его больше всего. В примере с тортом подразделение UM отдало бы весь шоколад Алисе и всю ваниль Джорджу, достигая утилитарной ценности 9 + 4 = 13. Этот процесс легко осуществить, когда функции стоимости кусочно-постоянны, т.е. торт можно разделить на куски так, чтобы плотность стоимости каждого куска была постоянной для всех людей. Когда функции ценности не являются кусочно-постоянными, существование распределений UM следует из классических теорем теории меры. См. Утилитарное разрезание торта .

Эффективное ярмарочное разделение [ править ]

Для n человек с аддитивными функциями ценности всегда существует подразделение PEEF. Это теорема Веллера . ^[9]

Если торт представляет собой одномерный интервал и каждый человек должен получить связный интервал, справедлив следующий общий результат: если функции ценности строго монотонны (т. е. каждый человек строго предпочитает кусок всем его подмножествам), то каждое деление EF является также ПЭ. ^[10] Следовательно, протокол Симмонса в этом случае производит деление PEEF.

Если торт представляет собой одномерный круг (т.е. интервал, две конечные точки которого топологически идентифицированы) и каждый человек должен получить связную дугу, то предыдущий результат не выполняется: деление EF не обязательно является PE. Кроме того, существуют пары (неаддитивных) функций значения, для которых не существует разделения PEEF. Однако если имеется 2 агента и хотя бы один из них имеет аддитивную функцию значения, то разделение PEEF существует. ^[11]

Если торт одномерный, но каждый человек может получить его несвязное подмножество, то разделение EF не обязательно является PE. В этом случае требуются более сложные алгоритмы поиска деления PEEF.

Если функции ценности аддитивны и кусочно-постоянны, то существует алгоритм, который находит деление PEEF. ^[12] Если функции плотности значений являются аддитивными и липшицевыми , то их можно аппроксимировать как кусочно-постоянные функции «настолько близко, насколько нам нравится», поэтому этот алгоритм аппроксимирует деление PEEF «настолько близко, насколько нам нравится». ^[12]

Подразделение EF не обязательно является UM. ^[13]^[14] Один из способов справиться с этой трудностью — найти среди всех возможных подразделений EF то, которое имеет наибольшую утилитарную ценность. Эта проблема изучалась для торта, который представляет собой одномерный интервал, каждый человек может получать несвязные кусочки, а функции ценности аддитивны. ^[15]

Модели вычислений [ править ]

Для рассуждения о сложности алгоритмов во время выполнения необходима модель вычислений . В литературе распространено несколько таких моделей:

Модель запроса Робертсона-Уэбба , в которой алгоритм может задавать каждому агенту запрос одного из двух типов: «оценить данный кусок пирога» или «отметить кусок пирога заданным значением».
Модель движущихся ножей – в которой алгоритм непрерывно перемещает один или несколько ножей над тортом, пока некоторые агенты не кричат «стоп».
Модель прямого раскрытия, в которой все агенты раскрывают механизму всю свою оценку. Эта модель имеет смысл только тогда, когда оценки могут быть представлены кратко, например, когда они кусочно-равномерны, кусочно-постоянны или кусочно-линейны .
Модель одновременных отчетов, в которой агенты одновременно отправляют дискретизацию своих показателей стоимости. Дискретизация — это последовательность точек отсечения и значений частей между этими точками отсечения (например: протокол для двух агентов может потребовать, чтобы каждый агент сообщал о последовательности из трех точек отсечения (0, x , 1), где значения (0, x ) и ( x ,1) равны 1/2). ^[16]

Разделение нескольких тортов [ править ]

Существует обобщение задачи о разрезании торта, в которой тортов несколько, и каждому агенту нужно получить кусок от каждого торта.

Клотье, Найман и Су ^[17] Изучите разделение нескольких тортов без зависти для двух игроков. Для двух тортов они доказывают, что распределение EF может не существовать, если имеется 2 агента и каждый торт разделен на 2 части. Однако распределение EF существует, когда имеется 2 агента и один пирог разрезается на 3 части (наименее нужная часть отбрасывается), или когда имеется 3 агента и каждый торт разрезается на 2 части (один агент игнорируется; распределение составляет EF для оставшихся двух).
Лебер, Менье и Карбонно ^[18] докажите для двух тортов, что распределение EF всегда существует, когда имеется 3 агента и каждый торт разрезается на 5 частей (два наименее желательных куска в каждом торте отбрасываются).
Найман, Су и Зербиб ^[19] докажите для k тортов, что распределение EF всегда существует, когда имеется k ( n -1)+1 агент и каждый торт разрезан на n частей (распределение равно EF для некоторого набора из n агентов).

Две связанные проблемы:

Разрезка многослойного торта, ^[20] где торты расположены «слоями», а кусочки одного и того же агента не должны перекрываться (например, каждый торт представляет собой время, в течение которого определенный объект доступен в течение дня; агент не может использовать два объекта одновременно).
Ярмарка разрезания нескольких тортов, ^[21] где агенты не хотят получить кусок от каждого торта, наоборот, они хотят получить кусочки от как можно меньшего количества тортов.

Разделение тортов [ править ]

Бэй, Лу и Суксомпонг ^[22] Представьте модель, в которой вместо того, чтобы делить отдельный кусок пирога каждому агенту, агенты должны вместе выбрать кусок пирога, который они все разделят. Это можно рассматривать как вариант выборов в комитеты , где кандидаты делятся. Существует континуум кандидатов, представленный действительным интервалом [0, c ], и цель состоит в том, чтобы выбрать подмножество этого интервала с общей длиной не более k , где k и c могут быть любыми действительными числами с 0 < k. < с . Они обобщают понятие обоснованного представления на этот случай. Лу, Питерс, Азиз, Бэй и Суксомпонг ^[23] распространите эти определения на настройки со смешанными делимыми и неделимыми кандидатами (см. обоснованное представление ).

См. также [ править ]

Справедливое распределение предметов - аналогичная проблема, в которой предметы, которые нужно разделить, неделимы.

Ссылки [ править ]

↑ Перейти обратно: Перейти обратно: ^а ^б Штайнхаус, Хьюго (1949). «Проблема справедливого дележа». Эконометрика . 17 : 315–9. дои : 10.2307/1907319 . JSTOR 1907319 .
^ Ариэль Прокачча, «Алгоритмы разрезания торта». Глава 13 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )
^ Хилл, ТП; Моррисон, Кентукки (2010). «Осторожно разрезаем торты». Математический журнал колледжа . 41 (4): 281. CiteSeerX 10.1.1.185.656 . дои : 10.4169/074683410x510272 . S2CID 3813775 .
^ Дубинс, Лестер Эли ; Спаниер, Эдвин Генри (1961). «Как красиво разрезать торт». Американский математический ежемесячник . 68 (1): 1–17. дои : 10.2307/2311357 . JSTOR 2311357 .
^ «Калькулятор справедливого дивизиона» . Архивировано из оригинала 28 февраля 2010 г. Проверено 10 июля 2014 г.
^ Иварс Петерсон (13 марта 2000 г.). «Честная сделка для соседей по дому» . МатТрек . Архивировано из оригинала 20 сентября 2012 года . Проверено 10 июля 2014 г.
^ Азиз, Харис; Маккензи, Саймон (27 августа 2017 г.). «Дискретный и ограниченный протокол разрезания торта без зависти для любого количества агентов». arXiv : 1604.03655 [ cs.DS ].
^ Сегал-Халеви, Эрель; Ницан, Шмуэль; хасидим, Авинатан; Ауманн, Йонатан (2017). «Честно и справедливо: разрезание торта в двух измерениях». Журнал математической экономики . 70 : 1–28. arXiv : 1409.4511 . дои : 10.1016/j.jmateco.2017.01.007 . S2CID 1278209 .
^ Веллер, Д. (1985). «Справедливое деление измеримого пространства». Журнал математической экономики . 14 :5–17. дои : 10.1016/0304-4068(85)90023-0 .
^ Берлиант, М.; Томсон, В.; Дунц, К. (1992). «О справедливом разделе разнородного товара». Журнал математической экономики . 21 (3): 201. doi : 10.1016/0304-4068(92)90001-n .
^ Томсон, В. (2006). «Дети плачут на днях рождения. Почему?». Экономическая теория . 31 (3): 501–521. дои : 10.1007/s00199-006-0109-3 . S2CID 154089829 .
↑ Перейти обратно: Перейти обратно: ^а ^б Рейньерс, Дж. Х.; Поттерс, ДЖЕМ (1998). «О нахождении оптимального по Парето деления без зависти». Математическое программирование . 83 (1–3): 291–311. дои : 10.1007/bf02680564 . S2CID 10219505 .
^ Караяннис, И.; Какламанис, К.; Канеллопулос, П.; Киропулу, М. (2011). «Эффективность ярмарочного разделения». Теория вычислительных систем . 50 (4): 589. CiteSeerX 10.1.1.475.9976 . дои : 10.1007/s00224-011-9359-y . S2CID 8755258 .
^ Ауманн, Ю.; Домбб, Ю. (2010). «Эффективность справедливого разделения со связанными частями» . Интернет и сетевая экономика . Конспекты лекций по информатике. Том. 6484. стр. 26 . CiteSeerX 10.1.1.391.9546 . дои : 10.1007/978-3-642-17572-5_3 . ISBN 978-3-642-17571-8 .
^ Колер, Юга Джулиан; Лай, Джон Кван; Паркс, Дэвид С; Прокачча, Ариэль (2011). Оптимальная резка торта без зависти . АААИ.
^ Балкански, Эрик; Брынзей, Симина; Курокава, Дэвид; Прокачча, Ариэль (21 июня 2014 г.). «Одновременное разрезание торта» . Материалы конференции AAAI по искусственному интеллекту . 28 (1). дои : 10.1609/aaai.v28i1.8802 . ISSN 2374-3468 . S2CID 1867115 .
^ Клотье, Джон; Найман, Кэтрин Л.; Су, Фрэнсис Эдвард (01 января 2010 г.). «Дивизион нескольких тортов без зависти для двух игроков» . Математические социальные науки . 59 (1): 26–37. arXiv : 0909.0301 . doi : 10.1016/j.mathsocsci.2009.09.002 . ISSN 0165-4896 . S2CID 15381541 .
^ Леберт, Николя; Менье, Фредерик; Карбонно, Квентин (1 ноября 2013 г.). «Дивизионы «м-торт» для двух игроков и два торта для трех игроков без зависти . Письма об исследованиях операций . 41 (6): 607–610. дои : 10.1016/j.orl.2013.07.010 . ISSN 0167-6377 . S2CID 7937916 .
^ Найман, Кэтрин; Су, Фрэнсис Эдвард; Зербиб, Шира (15 сентября 2020 г.). «Справедливое деление на несколько частей» . Дискретная прикладная математика . 283 : 115–122. arXiv : 1710.09477 . дои : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
^ Хоссейни, Хади; Игараси, Аюми; Сирнс, Эндрю (28 апреля 2020 г.). «Справедливое разделение времени: разрезание многослойного торта». arXiv : 2004.13397 [ cs.GT ].
^ Сегал-Халеви, Эрель (11 марта 2021 г.). «Ярмарка разрезания нескольких тортов» . Дискретная прикладная математика . 291 : 15–35. дои : 10.1016/j.dam.2020.10.011 . ISSN 0166-218X . S2CID 219792647 .
^ Бэй, Сяохуэй; Лу, Синьхан; Суксомпонг, Варут (28 июня 2022 г.). «Правдивый обмен тортами» . Материалы конференции AAAI по искусственному интеллекту . 36 (5): 4809–4817. arXiv : 2112.05632 . дои : 10.1609/aaai.v36i5.20408 . ISSN 2374-3468 .
^ Лу, Синьхан; Петерс, Янник; Азиз, Харис; Бэй, Сяохуэй; Суксомпонг, Варут (26 июня 2023 г.). «Голосование на основе одобрения смешанными товарами» . Материалы конференции AAAI по искусственному интеллекту . 37 (5): 5781–5788. arXiv : 2211.12647 . дои : 10.1609/aaai.v37i5.25717 . ISSN 2374-3468 .

Дальнейшее чтение [ править ]

[steinhaus48-1] Перейти обратно: Перейти обратно: ^а ^б Штайнхаус, Хьюго (1949). «Проблема справедливого дележа». Эконометрика . 17 : 315–9. дои : 10.2307/1907319 . JSTOR 1907319 .

[handbook-2] Ариэль Прокачча, «Алгоритмы разрезания торта». Глава 13 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )

[3] Хилл, ТП; Моррисон, Кентукки (2010). «Осторожно разрезаем торты». Математический журнал колледжа . 41 (4): 281. CiteSeerX 10.1.1.185.656 . дои : 10.4169/074683410x510272 . S2CID 3813775 .

[ds61-4] Дубинс, Лестер Эли ; Спаниер, Эдвин Генри (1961). «Как красиво разрезать торт». Американский математический ежемесячник . 68 (1): 1–17. дои : 10.2307/2311357 . JSTOR 2311357 .

[5] «Калькулятор справедливого дивизиона» . Архивировано из оригинала 28 февраля 2010 г. Проверено 10 июля 2014 г.

[6] Иварс Петерсон (13 марта 2000 г.). «Честная сделка для соседей по дому» . МатТрек . Архивировано из оригинала 20 сентября 2012 года . Проверено 10 июля 2014 г.

[7] Азиз, Харис; Маккензи, Саймон (27 августа 2017 г.). «Дискретный и ограниченный протокол разрезания торта без зависти для любого количества агентов». arXiv : 1604.03655 [ cs.DS ].

[8] Сегал-Халеви, Эрель; Ницан, Шмуэль; хасидим, Авинатан; Ауманн, Йонатан (2017). «Честно и справедливо: разрезание торта в двух измерениях». Журнал математической экономики . 70 : 1–28. arXiv : 1409.4511 . дои : 10.1016/j.jmateco.2017.01.007 . S2CID 1278209 .

[w85-9] Веллер, Д. (1985). «Справедливое деление измеримого пространства». Журнал математической экономики . 14 :5–17. дои : 10.1016/0304-4068(85)90023-0 .

[btd92-10] Берлиант, М.; Томсон, В.; Дунц, К. (1992). «О справедливом разделе разнородного товара». Журнал математической экономики . 21 (3): 201. doi : 10.1016/0304-4068(92)90001-n .

[t07-11] Томсон, В. (2006). «Дети плачут на днях рождения. Почему?». Экономическая теория . 31 (3): 501–521. дои : 10.1007/s00199-006-0109-3 . S2CID 154089829 .

[rp98-12] Перейти обратно: Перейти обратно: ^а ^б Рейньерс, Дж. Х.; Поттерс, ДЖЕМ (1998). «О нахождении оптимального по Парето деления без зависти». Математическое программирование . 83 (1–3): 291–311. дои : 10.1007/bf02680564 . S2CID 10219505 .

[13] Караяннис, И.; Какламанис, К.; Канеллопулос, П.; Киропулу, М. (2011). «Эффективность ярмарочного разделения». Теория вычислительных систем . 50 (4): 589. CiteSeerX 10.1.1.475.9976 . дои : 10.1007/s00224-011-9359-y . S2CID 8755258 .

[14] Ауманн, Ю.; Домбб, Ю. (2010). «Эффективность справедливого разделения со связанными частями» . Интернет и сетевая экономика . Конспекты лекций по информатике. Том. 6484. стр. 26 . CiteSeerX 10.1.1.391.9546 . дои : 10.1007/978-3-642-17572-5_3 . ISBN 978-3-642-17571-8 .

[clpp11-15] Колер, Юга Джулиан; Лай, Джон Кван; Паркс, Дэвид С; Прокачча, Ариэль (2011). Оптимальная резка торта без зависти . АААИ.

[16] Балкански, Эрик; Брынзей, Симина; Курокава, Дэвид; Прокачча, Ариэль (21 июня 2014 г.). «Одновременное разрезание торта» . Материалы конференции AAAI по искусственному интеллекту . 28 (1). дои : 10.1609/aaai.v28i1.8802 . ISSN 2374-3468 . S2CID 1867115 .

[17] Клотье, Джон; Найман, Кэтрин Л.; Су, Фрэнсис Эдвард (01 января 2010 г.). «Дивизион нескольких тортов без зависти для двух игроков» . Математические социальные науки . 59 (1): 26–37. arXiv : 0909.0301 . doi : 10.1016/j.mathsocsci.2009.09.002 . ISSN 0165-4896 . S2CID 15381541 .

[18] Леберт, Николя; Менье, Фредерик; Карбонно, Квентин (1 ноября 2013 г.). «Дивизионы «м-торт» для двух игроков и два торта для трех игроков без зависти . Письма об исследованиях операций . 41 (6): 607–610. дои : 10.1016/j.orl.2013.07.010 . ISSN 0167-6377 . S2CID 7937916 .

[19] Найман, Кэтрин; Су, Фрэнсис Эдвард; Зербиб, Шира (15 сентября 2020 г.). «Справедливое деление на несколько частей» . Дискретная прикладная математика . 283 : 115–122. arXiv : 1710.09477 . дои : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .

[20] Хоссейни, Хади; Игараси, Аюми; Сирнс, Эндрю (28 апреля 2020 г.). «Справедливое разделение времени: разрезание многослойного торта». arXiv : 2004.13397 [ cs.GT ].

[21] Сегал-Халеви, Эрель (11 марта 2021 г.). «Ярмарка разрезания нескольких тортов» . Дискретная прикладная математика . 291 : 15–35. дои : 10.1016/j.dam.2020.10.011 . ISSN 0166-218X . S2CID 219792647 .

[:10-22] Бэй, Сяохуэй; Лу, Синьхан; Суксомпонг, Варут (28 июня 2022 г.). «Правдивый обмен тортами» . Материалы конференции AAAI по искусственному интеллекту . 36 (5): 4809–4817. arXiv : 2112.05632 . дои : 10.1609/aaai.v36i5.20408 . ISSN 2374-3468 .

[23] Лу, Синьхан; Петерс, Янник; Азиз, Харис; Бэй, Сяохуэй; Суксомпонг, Варут (26 июня 2023 г.). «Голосование на основе одобрения смешанными товарами» . Материалы конференции AAAI по искусственному интеллекту . 37 (5): 5781–5788. arXiv : 2211.12647 . дои : 10.1609/aaai.v37i5.25717 . ISSN 2374-3468 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]