Правдивое разрезание торта

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

Классическая процедура «разделяй и выбирай» при разрезании торта неверна: если разрезатель знает предпочтения выбирающего, он может получить гораздо больше, чем 1/2, действуя стратегически. Например, предположим, что огранщик оценивает кусок по его размеру, а выбирающий оценивает кусок по количеству шоколада в нем. Таким образом, резак может разрезать торт на две части с почти одинаковым количеством шоколада, так что в меньшем куске будет немного больше шоколада. Тогда выбравший возьмет меньший кусок, а огранщик выиграет больший кусок, который может стоить намного больше, чем 1/2 (в зависимости от того, как распределен шоколад).

Рандомизированные механизмы

Существует тривиальный рандомизированный и правдивый механизм справедливого разрезания торта : равномерно случайным образом выберите одного агента и отдайте ему/ей весь торт. Этот механизм тривиально правдив, поскольку не задает вопросов. Более того, ожидание справедливо: ожидаемое значение каждого партнера равно ровно 1/ n . Однако полученное в результате распределение несправедливо. Задача состоит в том, чтобы разработать правдивые механизмы, которые были бы справедливы постфактум, а не только заранее. Разработано несколько таких механизмов.

Точный механизм деления

Точное деление (так называемое консенсусное деление ) — это разделение торта на n частей так, что каждый агент оценивает каждую часть ровно в 1/ n . Существование такого разделения является следствием теоремы Дубинса-Спанье о выпуклости . Более того, существует такое разделение с не более чем $n(n-1)^{2}$ порезы; это следствие теоремы Стромквиста-Вудалла и теоремы о расщеплении ожерелья .

В общем случае точное деление не может быть найдено с помощью конечного алгоритма. Однако его можно обнаружить в некоторых особых случаях, например, когда все агенты имеют кусочно-линейные оценки. Предположим, у нас есть недостоверный алгоритм (или оракул) для нахождения точного деления. Его можно использовать для создания рандомизированного механизма, правдивого в ожиданиях. ^[1]^[2] Рандомизированный механизм представляет собой механизм прямого раскрытия : он начинается с того, что всем агентам предлагается раскрыть все свои показатели ценности:

Попросите агентов сообщить об их показателях стоимости.
Используйте существующий алгоритм/оракул для создания точного деления.
Выполните случайную перестановку раздела консенсуса и дайте каждому партнеру по одному фрагменту.

Здесь ожидаемая ценность каждого агента всегда равна 1/ n независимо от функции сообщаемого значения. Следовательно, механизм правдив – ни один агент не может ничего получить от лжи. Более того, правдивому партнеру гарантировано значение ровно 1/ n с вероятностью 1 (не только в ожидании). Следовательно, у партнеров появляется стимул раскрыть свои истинные ценностные функции.

Суперпропорциональный механизм

— Сверхпропорциональное деление это деление торта, при котором каждый агент получает строго больше 1/ n по своим собственным меркам стоимости. Известно, что такое разделение существует тогда и только тогда, когда существуют хотя бы два агента, которые имеют разные оценки хотя бы одного куска торта. Любой детерминированный механизм, который всегда возвращает пропорциональное деление и всегда возвращает сверхпропорциональное деление, если оно существует, не может быть правдивым.

Моссель и Тамуз представляют сверхпропорциональный рандомизированный механизм, правдивый в ожиданиях: ^[1]

Выберите дивизию из некоторого распределения D по дивизиям.
Попросите каждого агента оценить свою работу.
Если все n оценок больше 1/ n , выполните распределение и завершите.
В противном случае используйте механизм точного деления.

Распределение D на шаге 1 должно быть выбрано таким, чтобы независимо от оценок агентов существовала положительная вероятность того, что будет выбрано сверхпропорциональное разделение, если оно существует. Затем на шаге 2 каждому агенту оптимально сообщать истинное значение: сообщение о более низком значении либо не имеет никакого эффекта, либо может привести к падению ценности агента с суперпропорционального до просто пропорционального (на шаге 4); сообщение о более высоком значении либо не имеет никакого эффекта, либо может привести к падению значения агента с пропорционального до менее 1/ n (на шаге 3).

Примерное точное деление с помощью запросов

Предположим, что вместо того, чтобы напрямую раскрывать свои оценки, агенты раскрывают свои ценности косвенно, отвечая на запросы отметки и оценки (как в модели Робертсона-Уэбба).

Бранзей и Мильтерсен ^[3] покажите, что механизм точного деления можно «дискретизировать» и реализовать в модели запроса. Это дает для любого $\epsilon >0$ , протокол на основе рандомизированных запросов, который запрашивает не более $O(n^{2}/\epsilon )$ запросов, правдив в ожиданиях и распределяет каждому агенту часть ценности между $1/n-\epsilon$ и $1/n+\epsilon$ , по оценкам всех агентов.

С другой стороны, они доказывают, что в любом детерминистическом протоколе, основанном на правдивых запросах, если все агенты положительно оценивают все части торта, существует хотя бы один агент, который получает пустой кусок. Это означает, что если агентов всего два, то хотя бы один агент является «диктатором» и получает весь торт. Очевидно, что любой такой механизм не может быть свободным от зависти.

Рандомизированный механизм для кусочно-постоянных оценок

Предположим, что все агенты имеют кусочно-постоянные оценки . Это означает, что для каждого агента пирог разделен на конечное число подмножеств, а плотность значений агента в каждом подмножестве постоянна. Для этого случая Азиз и Йе предлагают рандомизированный алгоритм, который более экономически эффективен: Ограниченная последовательная диктатура правдива в ожиданиях, устойчива пропорциональна и удовлетворяет свойству, называемому единогласием каждого агента 1/ n : если наиболее предпочтительная длина торта не пересекается от других агентов, то каждый агент получает наиболее предпочтительную 1/ n длины торта. Это слабая форма эффективности, не удовлетворяемая механизмами, основанными на точном разделении. Когда есть только два агента, это также полиномиально и надежно без зависти. ^[4]

Детерминированные механизмы: кусочно-постоянные оценки

Для детерминистических механизмов результаты в основном отрицательные, даже если все агенты имеют кусочно-постоянные оценки.

Курокава, Лай и Прокачча доказывают, что не существует детерминированного, правдивого и свободного от зависти механизма, который требует ограниченного числа запросов Робертсона-Уэбба. ^[5]

Азиз и Йе доказывают, что не существует детерминированного правдивого механизма, который удовлетворял бы хотя бы одному из следующих свойств: ^[4]

Пропорциональный и Парето-оптимальный;
Робастный - пропорциональный и нерасточительный («нерасточительный» означает, что ни одна часть не выделяется агенту, который этого не хочет; это слабее, чем оптимальность по Парето).

Менон и Ларсон вводят понятие ε-правдивости , которое означает, что ни один агент не получает больше, чем долю ε от искажения информации, где ε — положительная константа, независимая от оценок агентов. Они доказывают, что ни один детерминированный механизм не удовлетворяет ни одному из следующих свойств: ^[6]

ε - правдивый, приближенно-пропорциональный и нерасточительный (для констант аппроксимации не более 1/ n );
Правдивый, приблизительно-пропорциональный и связный (для константы аппроксимации не более 1/ n ).

Они представляют небольшую модификацию протокола Эвена-Паза и доказывают, что он ε -правдив с ε = 1 - 3/(2 n ), когда n четно, и ε = 1 - 3/(2 n ) + 1/ n ² когда n нечетно.

Бэй, Чен, Хучжан, Тао и Ву доказывают, что не существует детерминированного, правдивого и свободного от зависти механизма, даже в модели прямого раскрытия, который удовлетворял бы одному из следующих дополнительных свойств: ^[7]

Связанные части;
Нерасточительный;
Позиция не учитывается: распределение части торта основано только на оценке агентами этой части, а не на ее относительном положении на торте.

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

Положительным моментом является то, что в репликационной экономике, где каждый агент воспроизводится k раз, существуют механизмы, свободные от зависти, в которых говорить правду — это равновесие Нэша : ^[7]

При наличии требования к связности в любом механизме, свободном от зависти, высказывание правды сходится к равновесию Нэша, когда k приближается к бесконечности;
Без требования связности в механизме, который равномерно распределяет каждый однородный подинтервал между всеми агентами, высказывание правды является равновесием Нэша уже тогда, когда k ≥ 2.

Тао улучшает предыдущий результат Бэя, Чена, Хучжана, Тао и Ву о невозможности и показывает, что не существует детерминированного, правдивого и пропорционального механизма даже в модели прямого раскрытия и даже когда выполняются все следующие условия: ^[8]

Есть только два агента;
Агенты голодны: оценка каждого агента положительна (т. е. не может быть равна 0);
Механизму разрешено оставлять некоторую часть торта нераспределенной.

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

С положительной стороны, Тао представляет два алгоритма, которые реализуют более слабое понятие, называемое «пропорциональная правдивость без риска» (PRAT). Это означает, что при любом выгодном для агента i отклонении существуют оценки других агентов, по которым я получает меньше своей пропорциональной доли. Это свойство сильнее, чем «правдивость, не склонная к риску», что означает, что при любом выгодном отклонении для i существуют оценки других агентов, по которым я получает меньше, чем его ценность в правдивом сообщении. Он представляет PRAT-алгоритм, не вызывающий зависти, а также PRAT-алгоритм, пропорциональный и связный. ^[8]

Кусочно-равномерные оценки

Предположим, что все агенты имеют кусочно-равномерные оценки . Это означает, что для каждого агента существует подмножество торта, желательное для агента, и ценность агента для каждого куска равна лишь количеству желаемого торта, который он содержит. Например, предположим, что некоторые части торта покрыты равномерным слоем шоколада, а другие нет. Агент, который оценивает каждый кусок только по количеству содержащегося в нем шоколада, имеет кусочно-равномерную оценку. Это частный случай кусочно-постоянных оценок. Для этого особого случая было разработано несколько правдивых алгоритмов.

Чен, Лай, Паркс и Прокачча представляют механизм прямого раскрытия, который является детерминированным , пропорциональным, свободным от зависти , оптимальным по Парето и полиномиальным по времени. ^[2] Это работает для любого количества агентов. Вот иллюстрация механизма CLPP для двух агентов (где торт — это интервал).

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

Теперь, если агент говорит, что ему нужен интервал, который ему на самом деле не нужен, то он может получить более бесполезный торт на шаге 3 и менее полезный торт на шаге 4. Если он говорит, что ему не нужен интервал, который ему действительно нужен , то он получает менее полезный торт на шаге 3 и более полезный торт на шаге 4, однако сумма, полученная на шаге 4, делится с другим агентом, так что в целом лживый агент оказывается в убытке. Этот механизм можно обобщить на любое количество агентов.

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

Примечание : Азиз и Йе. ^[4] представил два механизма, которые расширяют механизм CLPP до кусочно-постоянных оценок - алгоритм поедания торта с ограничениями и алгоритм рыночного равновесия. Однако оба эти расширения перестают быть правдивыми, если оценки не являются кусочно-равномерными.

Майя и Нисан показывают, что механизм CLPP уникален в следующем смысле. ^[9] Рассмотрим частный случай двух агентов с кусочно-равномерными оценками, когда торт равен [0,1], Алисе нужен только подинтервал [0, a ] для некоторого a <1, а Бобу нужен только подинтервал [1- b , 1] для некоторого b <1. Рассмотрим только нерасточительные механизмы — механизмы, которые распределяют каждую желаемую хотя бы одним игроком фигуру тому игроку, который ее хочет. Каждый такой механизм должен дать Алисе подмножество [0, c ] для некоторого c <1, а Бобу — подмножество [1- d ,1] для некоторого d <1. В этой модели:

Нерасточительный детерминированный механизм правдив тогда и только тогда, когда для некоторого параметра t из [0,1] он дает Алисе интервал [0, min( a , max(1- b , t ))], а Бобу интервал [1- мин( б ,макс(1- а ,1- т )),1]
Такой механизм не вызывает зависти тогда и только тогда, когда t =1/2; в данном случае это эквивалентно механизму CLPP

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

Ли, Чжан и Чжан показывают, что механизм CLPP работает хорошо даже при наличии внешних эффектов (т. е. некоторые агенты извлекают некоторую выгоду из ценности, предоставленной другим), пока внешние эффекты достаточно малы. С другой стороны, если внешние эффекты (положительные или отрицательные) велики, не существует истинного, нерасточительного и независимого от позиции механизма. ^[10]

Алиджани, Фархади, Годси, Седдигин и Таджик представляют несколько механизмов для особых случаев кусочно-равномерных оценок: ^[11]

Процесс расширения обрабатывает кусочно-равномерные оценки, где каждый агент имеет один желаемый интервал, и, более того, желаемые интервалы агентов удовлетворяют свойству упорядочения . Это полиномиальное время, правдивое, свободное от зависти и гарантирующее связность частей.
Процесс расширения с разблокировкой обрабатывает кусочно-равномерные оценки, где каждый агент имеет один желаемый интервал, но без требования порядка. Оно является полиномиальным по времени, правдивым, свободным от зависти и не обязательно связным, но делает не более 2 n -2 сокращений.

Бэй, Хучжан и Суксомпонг представляют механизм для двух агентов с кусочно-равномерными оценками, который обладает теми же свойствами CLPP (правдивый, детерминированный, пропорциональный, свободный от зависти, оптимален по Парето и работает за полиномиальное время), но гарантирует, что вся торт выделяется: ^[12]

Найдите наименьший x в [0,1] такой, чтобы желаемая длина Алисы в [0, x ] равнялась желаемой длине Боба в [ x ,1].
Дайте Алисе интервалы в [0, x ], оцененные Алисой, и интервалы в [ x ,1], не оцененные Бобом; отдайте остаток Бобу.

Механизм BHS работает как для разрезания торта, так и для разделения обязанностей (где оценки агентов отрицательны). Обратите внимание, что BHS не удовлетворяет некоторым естественным желаемым свойствам:

Он не гарантирует связность частей , например, когда Алиса хочет [0,1], а Боб хочет [0,0,5], тогда x =0,25, Алиса получает [0,0,25] и [0,5,1], а Боб получает [0,25]. ,0,5].
Оно не является анонимным (см. симметричное честное разрезание торта ) : если Алиса хочет [0,1], а Боб хочет [0,0,5], то Алиса получает желаемую длину 0,75, а Боб получает 0,25, но если оценки поменяются местами ( Алиса хочет [0,0,5], а Боб хочет [0,1]), тогда x =0,5 и оба агента получают желаемую длину 0,5.
Это не забывает позиция : если Алиса хочет [0,0,5], а Боб хочет [0,1], то оба агента получают значение 0,5, но если желаемый интервал Алисы перемещается на [0,5,1], тогда x = 0,75, и Алиса получает 0,25 и Боб получает 0,75.

Это не проблема конкретного механизма: доказуемо невозможно иметь правдивый и свободный от зависти механизм, который распределяет весь пирог и гарантирует любое из этих трех свойств, даже для двух агентов с кусочно-равномерными оценками. ^[12]

Механизм BHS был распространен на любое количество агентов, но только для частного случая кусочно-равномерных оценок, в которых каждому агенту нужен только один интервал вида [0, x _i ].

Яновский ^[13] доказывает, что ни один правдивый механизм не может достичь утилитарно-оптимального разрезания торта , даже если все агенты имеют кусочно-однородные оценки. Более того, ни один правдивый механизм не может обеспечить распределение с утилитарным благосостоянием, по крайней мере, таким же большим, как любой другой механизм. Однако существует простой, правдивый механизм (обозначаемый Lex Order), который не является расточительным : отдайте агенту 1 все части, которые ему нравятся; затем отдайте агенту 2 все части, которые ему нравятся и еще не были переданы агенту 1; и т. д. Вариантом этого механизма является игра «Длина», в которой агенты переименовываются по общей длине желаемых интервалов, так что агент с самым коротким интервалом называется 1, агент со следующим по величине интервалом называется 2. и т. д. Однако это неправдивый механизм:

Если все агенты правдивы, то получается утилитарно-оптимальное распределение.
Если агенты являются стратегическими, то все его хорошо ведущие себя равновесия Нэша эффективны по Парето и свободны от зависти и приносят те же выплаты, что и механизм CLPP.

Краткое изложение правдивых механизмов и результатов невозможности

Имя	Тип	Детерминированный?	#агенты( $н$ )	оценки ^[14]	Работа по дому? ^[15]	Время выполнения	Все? ^[16]	PO? ^[17]	ЕСЛИ? ^[18]	Анон? ^[19]	Конн? ^[20]	Pos.Ob.? ^[21]	Нет отходов? ^[22]
Точное деление ^[1]^[2]	Прямой	Нет	Много	Общий	Да	Неограниченный ^[23]	Да	Нет	Да	Да	Нет	?	?
Суперпропорциональный ^[1]	Прямой	Нет	Много	Общий	Да	Неограниченный	Да	Нет	Нет	Да	Нет	?	?
Дискретное точное деление ^[3]	Запросы	Нет	Много	Общий	Да	$O(n^{2}/\epsilon )$	Да	Нет	$\epsilon$ -ЕСЛИ	Да	Нет	?	?
Ограниченная серийная диктатура ^[4]	Прямой	Нет	Много	ПВК	?	?	Нет	Единогласие	Опора.	?	Нет	?	?
КЛПП ^[2]	Прямой	Да	Много	ПВУ	Нет	Полиномиальный	Нет	Да	Да	Да	Нет	?	Да
БХС 1, 2	Прямой	Да	2	ПВУ	Да	Полиномиальный	Да	Да	Да	Нет	Нет	Нет	Да
БХС 3, 4	Прямой	Да	Много	PWU1	Да	Полиномиальный	Да	Да	Да _{(для тортов)}	?	?	?	Да
Расширение ^[11]	Прямой	Да	Много	PWU1+заказ	?	Полиномиальный	?	?	Да	?	Да	?	?
Расширение+ Разблокировка	Прямой	Да	Много	PWU1	?	Полиномиальный	?	?	Да	?	2 н -2 разреза	?	?
НЕВОЗМОЖНЫЕ КОМБИНАЦИИ:
[БМ] ^[3]	Запросы	Да	2+	Любой
[БХС] ^[12]	Прямой	Да	2+	ПВУ			Да		Да	Да
[БХС]	Прямой	Да	2+	ПВУ			Да		Да		Да
[БХС]	Прямой	Да	2+	ПВУ			Да		Да			Да
[Т] ^[8]	Прямой	Да	2+	ПВК					Да _{(даже для Проп.)}
[БЧТВ] ^[7]	Прямой	Да	2+	ПВК			Да		Да		Да
[БЧТВ]	Прямой	Да	2+	ПВК			Да		Да			Да
[БЧТВ]	Прямой	Да	2+	ПВК			Да		Да				Да
[БЧТВ]	Последовательный	Да	2+	ПВК			Да		Да

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д Моссель, Эльханан; Тамуз, Омер (2010). «Правдиво-справедливое разделение». В Контояннисе Спирос К.; Куцупиас, Элиас; Спиракис, Пол Г. (ред.). Алгоритмическая теория игр – Третий международный симпозиум, SAGT 2010, Афины, Греция, 18–20 октября 2010 г. Труды . Конспекты лекций по информатике. Том. 6386. Спрингер. стр. 288–299. arXiv : 1003.5480 . Бибкод : 2010LNCS.6386..288M . дои : 10.1007/978-3-642-16170-4_25 . ISBN 9783642161704 . S2CID 11732339 .
^ Jump up to: ^а ^б ^с ^д Чен, Илин ; Лай, Джон К.; Паркс, Дэвид К.; Прокачча, Ариэль Д. (1 января 2013 г.). «Правда, справедливость и разрезание торта» (PDF) . Игры и экономическое поведение . 77 (1): 284–297. дои : 10.1016/j.geb.2012.10.009 . ISSN 0899-8256 . S2CID 2096977 .
^ Jump up to: ^а ^б ^с Брынзей, Симина; Мильтерсен, Питер Бро (22 июня 2015 г.). «Теорема о диктатуре для разрезания торта» . Двадцать четвертая международная совместная конференция по искусственному интеллекту .
^ Jump up to: ^а ^б ^с ^д Азиз, Харис; Йе, Чун (2014). «Алгоритмы разрезания торта для кусочно-постоянных и кусочно-равномерных оценок». В Лю, Те-Янь; Ци, Ци; Йе, Иньюй (ред.). Экономика Интернета и Интернета – 10-я Международная конференция WINE 2014, Пекин, Китай, 14–17 декабря 2014 г. Тезисы докладов . Конспекты лекций по информатике. Том. 8877. Спрингер. стр. 1–14. arXiv : 1307.2908 . дои : 10.1007/978-3-319-13129-0_1 .
^ Курокава, Дэвид; Лай, Джон К.; Прокачча, Ариэль Д. (30 июня 2013 г.). «Как разрезать торт до окончания вечеринки» . Двадцать седьмая конференция AAAI по искусственному интеллекту . 27 : 555–561. дои : 10.1609/aaai.v27i1.8629 . S2CID 12638556 .
^ Менон, Виджай; Ларсон, Кейт (17 мая 2017 г.). «Детерминистический, стратегический и справедливый разрез торта». arXiv : 1705.06306 [ cs.GT ].
^ Jump up to: ^а ^б ^с Бэй, Сяохуэй; Чен, Нин; Хучжан, Гуанда; Тао, Бяошуай; Ву, Цзяцзюнь (2017). «Разрезание торта: зависть и правда» . Материалы 26-й Международной совместной конференции по искусственному интеллекту . IJCAI'17. АААИ Пресс: 3625–3631. ISBN 9780999241103 .
^ Jump up to: ^а ^б ^с Тао, Бяошуай (13 июля 2022 г.). «О существовании честных механизмов для резки тортов» . Материалы 23-й конференции ACM по экономике и вычислениям . стр. 404–434. arXiv : 2104.07387 . дои : 10.1145/3490486.3538321 . ISBN 9781450391504 . S2CID 233241229 .
^ Майя, Авишай; Нисан, Ноам (2012). «Разрезание торта для двух игроков, совместимое со стимулами». В Голдберге, Пол В. (ред.). Интернет и сетевая экономика – 8-й международный семинар, WINE 2012, Ливерпуль, Великобритания, 10–12 декабря 2012 г. Материалы . Конспекты лекций по информатике. Том. 7695. Спрингер. стр. 170–183. arXiv : 1210.0155 . дои : 10.1007/978-3-642-35311-6_13 . ISBN 9783642353116 . S2CID 1927798 .
^ Ли, Минминг; Чжан, Цзялинь; Чжан, Цян (22 июня 2015 г.). «Правдивые механизмы разрезания торта с внешними эффектами: не заставляйте их слишком сильно заботиться о других!» . Двадцать четвертая международная совместная конференция по искусственному интеллекту .
^ Jump up to: ^а ^б Алиджани, Реза; Фархади, Маджид; Годси, Мохаммед; Седдигин, Масуд; Таджик, Ахмад С. (10 февраля 2017 г.). «Механизмы без зависти с минимальным количеством сокращений» . Тридцать первая конференция AAAI по искусственному интеллекту . 31 . дои : 10.1609/aaai.v31i1.10584 . S2CID 789550 .
^ Jump up to: ^а ^б ^с Бэй, Сяохуэй; Хучжан, Гуанда; Суксомпонг, Варут (2020). «Правдивый справедливый раздел без свободного распоряжения» . Социальный выбор и благосостояние . 55 (3): 523–545. arXiv : 1804.06923 . дои : 10.1007/s00355-020-01256-0 . ПМЦ 7497335 . ПМИД 33005068 .
^ Яновский, Егор (01 марта 2012 г.). «Механизмы резки торта». arXiv : 1203.0100 [ cs.GT ].
^ PWC = кусочно-постоянный, PWU = кусочно-равномерный, PWU1 = кусочно-равномерный с одним желаемым интервалом.
^ Может ли алгоритм обрабатывать торты с отрицательной полезностью (работой по дому).
^ Разделен ли весь торт без утилизации.
^ Всегда ли полученное распределение является оптимальным по Парето .
^ Всегда ли полученное распределение не вызывает зависти .
^ Является ли механизм анонимным .
^ Всегда ли полученные части соединены.
^ механизма Независимо от положения .
^ Гарантирует ли алгоритм нерасточность.
^ Во время выполнения преобладает расчет точного деления . В общем случае он неограничен, но в особых случаях может быть полиномиальным.

[:0-1] Jump up to: ^а ^б ^с ^д Моссель, Эльханан; Тамуз, Омер (2010). «Правдиво-справедливое разделение». В Контояннисе Спирос К.; Куцупиас, Элиас; Спиракис, Пол Г. (ред.). Алгоритмическая теория игр – Третий международный симпозиум, SAGT 2010, Афины, Греция, 18–20 октября 2010 г. Труды . Конспекты лекций по информатике. Том. 6386. Спрингер. стр. 288–299. arXiv : 1003.5480 . Бибкод : 2010LNCS.6386..288M . дои : 10.1007/978-3-642-16170-4_25 . ISBN 9783642161704 . S2CID 11732339 .

[:1-2] Jump up to: ^а ^б ^с ^д Чен, Илин ; Лай, Джон К.; Паркс, Дэвид К.; Прокачча, Ариэль Д. (1 января 2013 г.). «Правда, справедливость и разрезание торта» (PDF) . Игры и экономическое поведение . 77 (1): 284–297. дои : 10.1016/j.geb.2012.10.009 . ISSN 0899-8256 . S2CID 2096977 .

[:5-3] Jump up to: ^а ^б ^с Брынзей, Симина; Мильтерсен, Питер Бро (22 июня 2015 г.). «Теорема о диктатуре для разрезания торта» . Двадцать четвертая международная совместная конференция по искусственному интеллекту .

[:6-4] Jump up to: ^а ^б ^с ^д Азиз, Харис; Йе, Чун (2014). «Алгоритмы разрезания торта для кусочно-постоянных и кусочно-равномерных оценок». В Лю, Те-Янь; Ци, Ци; Йе, Иньюй (ред.). Экономика Интернета и Интернета – 10-я Международная конференция WINE 2014, Пекин, Китай, 14–17 декабря 2014 г. Тезисы докладов . Конспекты лекций по информатике. Том. 8877. Спрингер. стр. 1–14. arXiv : 1307.2908 . дои : 10.1007/978-3-319-13129-0_1 .

[5] Курокава, Дэвид; Лай, Джон К.; Прокачча, Ариэль Д. (30 июня 2013 г.). «Как разрезать торт до окончания вечеринки» . Двадцать седьмая конференция AAAI по искусственному интеллекту . 27 : 555–561. дои : 10.1609/aaai.v27i1.8629 . S2CID 12638556 .

[6] Менон, Виджай; Ларсон, Кейт (17 мая 2017 г.). «Детерминистический, стратегический и справедливый разрез торта». arXiv : 1705.06306 [ cs.GT ].

[:42-7] Jump up to: ^а ^б ^с Бэй, Сяохуэй; Чен, Нин; Хучжан, Гуанда; Тао, Бяошуай; Ву, Цзяцзюнь (2017). «Разрезание торта: зависть и правда» . Материалы 26-й Международной совместной конференции по искусственному интеллекту . IJCAI'17. АААИ Пресс: 3625–3631. ISBN 9780999241103 .

[:44-8] Jump up to: ^а ^б ^с Тао, Бяошуай (13 июля 2022 г.). «О существовании честных механизмов для резки тортов» . Материалы 23-й конференции ACM по экономике и вычислениям . стр. 404–434. arXiv : 2104.07387 . дои : 10.1145/3490486.3538321 . ISBN 9781450391504 . S2CID 233241229 .

[:2-9] Майя, Авишай; Нисан, Ноам (2012). «Разрезание торта для двух игроков, совместимое со стимулами». В Голдберге, Пол В. (ред.). Интернет и сетевая экономика – 8-й международный семинар, WINE 2012, Ливерпуль, Великобритания, 10–12 декабря 2012 г. Материалы . Конспекты лекций по информатике. Том. 7695. Спрингер. стр. 170–183. arXiv : 1210.0155 . дои : 10.1007/978-3-642-35311-6_13 . ISBN 9783642353116 . S2CID 1927798 .

[10] Ли, Минминг; Чжан, Цзялинь; Чжан, Цян (22 июня 2015 г.). «Правдивые механизмы разрезания торта с внешними эффектами: не заставляйте их слишком сильно заботиться о других!» . Двадцать четвертая международная совместная конференция по искусственному интеллекту .

[:7-11] Jump up to: ^а ^б Алиджани, Реза; Фархади, Маджид; Годси, Мохаммед; Седдигин, Масуд; Таджик, Ахмад С. (10 февраля 2017 г.). «Механизмы без зависти с минимальным количеством сокращений» . Тридцать первая конференция AAAI по искусственному интеллекту . 31 . дои : 10.1609/aaai.v31i1.10584 . S2CID 789550 .

[:3-12] Jump up to: ^а ^б ^с Бэй, Сяохуэй; Хучжан, Гуанда; Суксомпонг, Варут (2020). «Правдивый справедливый раздел без свободного распоряжения» . Социальный выбор и благосостояние . 55 (3): 523–545. arXiv : 1804.06923 . дои : 10.1007/s00355-020-01256-0 . ПМЦ 7497335 . ПМИД 33005068 .

[13] Яновский, Егор (01 марта 2012 г.). «Механизмы резки торта». arXiv : 1203.0100 [ cs.GT ].

[14] PWC = кусочно-постоянный, PWU = кусочно-равномерный, PWU1 = кусочно-равномерный с одним желаемым интервалом.

[15] Может ли алгоритм обрабатывать торты с отрицательной полезностью (работой по дому).

[16] Разделен ли весь торт без утилизации.

[17] Всегда ли полученное распределение является оптимальным по Парето .

[18] Всегда ли полученное распределение не вызывает зависти .

[19] Является ли механизм анонимным .

[20] Всегда ли полученные части соединены.

[21] механизма Независимо от положения .

[22] Гарантирует ли алгоритм нерасточность.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]