Симметричная честная резка торта - Symmetric fair cake-cutting

Симметричная распиловка торта это вариант ярмарка разрезания торта проблема, в которой справедливость применяется не только к конечному результату, но и к распределению ролей в процедуре разделения.

В качестве примера рассмотрим праздничный торт, который нужно разделить между двумя детьми с разными вкусами, чтобы каждый ребенок чувствовал, что его / ее доля «справедлива», т.е. стоит не менее половины всего торта. Они могут использовать классический разделяй и выбирай Порядок действий: Алиса разрезает торт на два куска, стоящих в ее глазах ровно 1/2, и Джордж выбирает кусок, который считает более ценным. Результат всегда справедливый. Однако процедура не является симметричной: в то время как Алиса всегда получает значение ровно 1/2 своего значения, Джордж может получить гораздо больше, чем 1/2 своего значения. Таким образом, хотя Алиса не завидует доле Джорджа, она завидует его роли в этой процедуре.

Напротив, рассмотрим альтернативную процедуру, в которой Алиса и Джордж оба делают половинки отметок на торте, то есть каждый из них отмечает место, в котором должен быть разрезан торт, так, чтобы два куска были равны в его / ее глазах. Затем торт разрезается точно между этими разрезами - если разрез Алисы а и разрез Джорджа грамм, то торт разрезается на (a + g) / 2. Если а<грамм, Алиса получает крайнюю левую фигуру, а Джордж - крайнюю правую фигуру; в противном случае Алиса получает крайнюю правую фигуру, а Джордж - крайнюю левую. Окончательный результат остается справедливым. И здесь роли симметричны: единственный случай, когда роли имеют значение в конечном результате, - это когда а=грамм, но в этом случае обе части имеют значение ровно 1/2 для обоих дочерних элементов, поэтому роли не влияют на окончательное значение. Следовательно, альтернативная процедура является справедливой и симметричной.

Идею впервые представили Манабэ и Окамото,[1] кто назвал это без мета-зависти.

Было предложено несколько вариантов симметричной распиловки торта:

  • Анонимная ярмарка порезки торта требует, чтобы не только значения были равны, но и сами части были равны.[2] Это подразумевает симметричную справедливость, но она сильнее. Например, это не удовлетворяет указанное выше симметричное разделение и выбор, поскольку в случае, когда а=грамм, первый агент всегда получает крайнюю левую часть, а второй агент всегда получает крайнюю правую часть.
  • Аристотелевская ярмарка нарезки торта требуется только, чтобы агенты с одинаковыми показателями ценности получали одинаковое значение.[3] Это подразумевается симметричной справедливостью, но она слабее. Например, его удовлетворяет асимметричный вариант «разделяй и выбирай»: если оценки агентов идентичны, то они оба получают значение ровно 1/2.

Определения

Существует торт C, обычно считается одномерным интервалом. Есть п люди. Каждый человек я имеет функцию значения Vя который отображает подмножества C к слабоположительным числам.

А процедура разделения это функция F что отображает п функции значения в раздел C. Произведение, выделенное F агенту я обозначается F(V1,...,Vп; я).

Симметричная процедура

Процедура разделения F называется симметричный если для любой перестановки п из (1, ...,п), и для каждого я:

Vя(F(V1,...,Vп; я)) = Vя(F(Vп (1),...,Vп (п); п−1(я)))

В частности, когда п= 2, процедура будет симметричной, если:

V1(F(V1,V2; 1)) = V1(F(V2,V1; 2)) и V2(F(V1,V2; 2)) = V2(F(V2,V1; 1))

Это означает, что агент 1 получает одно и то же значение вне зависимости от того, играет он первым или вторым, и то же самое верно и для агента 2, как другой пример, когда п= 3, требование симметрии подразумевает (среди прочего):

V1(F(V1,V2,V3; 1)) = V1(F(V2,V3, V1; 3)) = V1(F(V3, V1,V2; 2)).

Анонимная процедура

Процедура разделения F называется анонимный если для любой перестановки п из (1, ...,п), и для каждого я:

F(V1,...,Vп; я) = F(Vп (1),...,Vп (п); п−1(я))

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

Но обратное неверно: вполне возможно, что перестановка дает агенту разные части с равной ценностью.

Аристотелевская процедура

Процедура разделения F называется аристотелевец если, когда Vя=Vk:

Vя(F(V1,...,Vп; я)) = Vk(F(V1,...,Vп; k))

Критерий назван в честь Аристотель, который писал в своей книге по этике: «... когда равные владеют или получают неравные доли, или люди, не равные равные доли, возникают ссоры и жалобы». Каждая симметричная процедура является аристотелевской. Позволять п быть перестановкой, которая меняет я и k. Симметрия подразумевает, что:

Vя(F(V1,....Vя,...,Vk,...,Vп; я)) = Vя(F(V1,....Vk,...,Vя,...,Vп; k))

Но с тех пор Vя=Vk, две последовательности значений-мер идентичны, поэтому отсюда следует определение аристотелизма. резка торта без зависти является аристотелевским: свобода от зависти предполагает, что:

Vя(F(V1,...,Vп; я)) ≥ Vя(F(V1,...,Vп; k))Vk(F(V1,...,Vп; k)) ≥ Vk(F(V1,...,Vп; я))

Но с тех пор Vя=Vk, два неравенства означают, что оба значения равны.

Однако процедура, удовлетворяющая более слабому условию Пропорциональная резка торта не обязательно аристотелевский. Cheze[3] показывает пример с 4 агентами, в которых Процедура Even-Paz для пропорциональной резки торта может давать разные значения агентам с одинаковыми показателями стоимости.

Следующая диаграмма суммирует отношения между критериями:

  • Анонимный → Симметричный → Аристотелевский
  • Без зависти → Аристотелевский
  • Без зависти → Пропорциональный

Процедуры

Каждую процедуру можно сделать "симметричной ожидаемой" путем рандомизации. Например, в асимметричном режиме «разделяй и выбирай» разделитель можно выбрать, бросив монету. Однако такая процедура не является симметричной постфактум. Таким образом, исследования в области симметричной резки торта фокусируются на детерминированные алгоритмы.

Манабэ и Окамото[1] представили симметричные и свободные от зависти («мета-зависти») детерминированные процедуры для двух и трех агентов.

Николо и Ю[2] представили анонимный, свободный от зависти и эффективный по Парето протокол разделения для двух агентов. Протокол реализует распределение в подигра идеальное равновесие при условии, что у каждого агента есть полная информация об оценке другого агента.

Симметричная процедура вырезания и выбора для двух агентов была изучена эмпирически в лабораторном эксперименте.[4] Альтернативные симметричные процедуры нарезки торта для двух агентов: крайняя правая отметка[5] и крайние левые листья.[6]

Cheze[3] представлены несколько процедур:

  • Общая схема преобразования любой процедуры без зависти в симметричную детерминированную процедуру: запустить исходную процедуру п! раз, один раз для каждой перестановки агентов, и выберите один из исходов в соответствии с некоторым топологическим критерием (например, минимизация количества разрезов). Эта процедура нецелесообразна, если п большой.
  • Аристотелевская пропорциональная процедура для п агентов, для чего требуется O (п3) запросов и полиномиальное количество арифметических операций судьи.
  • Симметричная пропорциональная процедура для п агентов, для чего требуется O (п3) запросов, но может потребовать от рефери экспоненциального количества арифметических операций.

Аристотелевская пропорциональная процедура

Аристотелевская процедура Хезе[3] за пропорциональная резка торта расширяет одинокий разделитель процедура. Для удобства мы нормализуем оценки так, чтобы стоимость всего торта была равна п для всех агентов. Цель состоит в том, чтобы дать каждому агенту по фигуре не менее 1.

  1. Один произвольно выбранный игрок называется разделитель, разрезает торт на п фигуры, ценность которых в его глазах равна 1.
  2. Построить двудольный граф грамм = (X + Y, E), в котором каждая вершина из Икс агент, каждая вершина в Y это кусок, и есть грань между агентом Икс и кусок у если только Икс значения у как минимум 1.
  3. Найдите максимальную мощность соответствие без зависти в грамм (соответствие, в котором ни один несоответствующий агент не соседствует с согласованным элементом). Обратите внимание, что разделитель примыкает ко всем п штук, так что |Nграмм(Икс)|= п ≥ | X | (куда Nграмм(Икс) - множество соседей Икс в Y). Следовательно, существует непустое соответствие без зависти.[7] Предположим, что w.l.o.g. что EFM соответствует агентам 1, ...,k на кусочки Икс1,...,ИКСk, и оставляет непревзойденными агенты и детали из k+1 к п.
  4. Для каждого я в 1,...,k для которого Vя(Икся) = 1 - дать Икся агенту я. Теперь разделителю и всем агентам, функция ценности которых идентична функциям делителей, назначается кусок и они имеют одинаковую стоимость.
  5. Рассмотрим теперь агентов я в 1,...,k для которого Vя(Икся)> 1. Разделите их на подмножества с одинаковыми векторами значений для частей. Икс1,...,ИКСk. Для каждого подмножества рекурсивно разделите их части между ними (например, если агенты 1, 3, 4 согласовывают значения всех частей 1, ...,k, затем разделите части Икс1,ИКС3,Икс4 рекурсивно среди них). Теперь все агенты, чьи функции-ценности идентичны, назначаются одному и тому же подмножеству, и они делят суб-пирог, значение которого для них больше, чем их количество, поэтому предварительное условие для рекурсии удовлетворяется.
  6. Рекурсивно разделите несогласованные части Иксk+1, ..., Иксп среди непревзойденных агентов. Обратите внимание, что из-за отсутствия зависти к сопоставлению каждый несогласованный агент оценивает каждую сопоставленную часть меньше 1, поэтому он оценивает оставшиеся части больше, чем количество агентов, поэтому предварительное условие для рекурсии удовлетворяется.

Рекомендации

  1. ^ а б Манабэ, Йошифуми; Окамото, Тацуаки (2010). "Протоколы резки торта без зависти". Материалы 35-й Международной конференции по математическим основам информатики. MFCS'10. Берлин, Гейдельберг: Springer-Verlag: 501–512. ISBN  9783642151545.
  2. ^ а б Николо, Антонио; Ю, Ян (01.09.2008). «Стратегический разделяй и выбирай» (PDF). Игры и экономическое поведение. 64 (1): 268–289. Дои:10.1016 / j.geb.2008.01.006. ISSN  0899-8256.
  3. ^ а б c d Чез, Гийом (11.04.2018). «Не плачь первым! Существуют алгоритмы симметричного справедливого деления». arXiv:1804.03833v1. Цитировать журнал требует | журнал = (помощь)
  4. ^ Киропулу, Мария; Ортега, Хосуэ; Сегал-Халеви, Эрель (2019). «Честная резка торта на практике». Материалы конференции ACM по экономике и вычислениям 2019 г.. EC '19. Нью-Йорк, Нью-Йорк, США: ACM: 547–548. arXiv:1810.08243. Дои:10.1145/3328526.3329592. ISBN  9781450367929. S2CID  53041563.
  5. ^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01.09.2018). «Ресурсо-монотонность и популяционно-монотонность в связном разрезании торта». Математические социальные науки. 95: 19–30. arXiv:1703.08928. Дои:10.1016 / j.mathsocsci.2018.07.001. ISSN  0165-4896. S2CID  16282641.
  6. ^ Ортега, Хосуэ (8 августа 2019 г.). «Очевидные манипуляции при резке торта». arXiv:1908.02988v1. Цитировать журнал требует | журнал = (помощь)
  7. ^ Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (28.01.2019). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv:1901.09527v2. Цитировать журнал требует | журнал = (помощь)