Справедливое разделение пирогов

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

В качестве примера рассмотрим праздничный торт в форме диска . Торт следует разделить между несколькими детьми так, чтобы ни один ребенок не завидовал другому (как в стандартной задаче о разрезании торта), с дополнительным ограничением, что разрезы должны быть радиальными, так что каждый ребенок получает круглый сектор .

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

Другое возможное применение — разделение периодического времени, например, разделение суточного цикла на периоды «по вызову».

Модель

Круговая диаграмма обычно моделируется как одномерный интервал [0,2π] (или [0,1]), в котором определены две конечные точки.

Эта модель была представлена ​​в 1985 году, а затем в 1993 году. ^{[1] [2]}

Каждая процедура справедливого разрезания торта может быть применена и к разрезанию пирога, просто игнорируя тот факт, что две конечные точки идентифицированы. Например, если процедура разрезания торта привела к разделению, в котором Алиса получает [0,1/3], а Джордж получает [1/3,1], то мы бы дали Алисе круговой сектор в 120 градусов, а Джорджу — оставшийся сектор в 240 градусов.

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

Два партнера

Разделение без зависти

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

Разделение пирога EF всегда можно найти с помощью метода «раздели и выбери» : один партнер разрезает пирог на два сектора, которые он считает равными, а другой партнер выбирает сектор, который он считает лучшим. Но для пирога могут быть возможны и лучшие деления.

Деление без зависти и эффективное по Парето

Разделение называется Парето-эффективным (ПЭ), если ни одно другое разделение не лучше для одного партнера и не хуже для другого. Часто Парето-эффективность оценивается только по отношению к подмножеству всех возможных разделений. То есть только разделений на два смежных сектора (разделений с минимальным числом разрезов).

Деление называется PEEF, если оно является одновременно PE и EF.

Когда оценки партнеров являются (аддитивными) мерами, следующая процедура движущегося ножа гарантирует разделение, которое является EF и PE относительно разделений на два смежных сектора. ^[3]

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

Другой партнер (Выбирающий) наблюдает этот процесс в течение всего цикла. Затем, в следующем цикле, он определяет позицию, которая, по его мнению, дает максимальное значение одному из двух определенных таким образом секторов. Выбирающий получает этот сектор, а Вращающий получает другой сектор.

Это разделение, очевидно, EF, поскольку Rotator безразличен между двумя секторами, Chooser получает лучший сектор. Это PE, поскольку нет раздела, который дал бы Chooser большее значение и оставил бы Rotator значение 1/2.

Ограничения аддитивности

Вышеуказанная процедура работает только в том случае, если функция ценности Ротатора аддитивна, так что равные доли всегда имеют одинаковое значение 1/2. Если ее значение не аддитивно, то деление все равно будет свободным от зависти, но не обязательно эффективным по Парето.

Более того, когда оценки обоих партнеров не суммируются (поэтому ни один из них не может играть роль Ротатора), разделение PEEF не всегда существует. ^[4]

Консенсусное деление и взвешенное пропорциональное деление

Раздел называется точным разделом (или консенсусным разделом ), если стоимость части точно соответствует стоимости всех партнеров, при этом веса заранее определены. ${\displaystyle i}$ ${\displaystyle w_{i}}$ ${\displaystyle w_{i}}$

Предположим, что сумма всех весов равна 1, а значение пирога для всех агентов также нормализовано до 1. По теореме Стромквиста-Вудалла для каждого веса существует подмножество , которое является объединением не более чем секторов, которые все партнеры оценивают ровно в . Для агентов это подразумевает, что всегда существует консенсусное разделение пирога со связанными секторами: дать агенту 1 сектор, который стоит ровно для обоих агентов, и дать агенту 2 оставшийся сектор, который стоит для обоих агентов ( альтернативное доказательство см. в ^{[5] ).} ${\displaystyle w\in [0,1]}$ ${\displaystyle C_{w}}$ ${\displaystyle n-1}$ ${\displaystyle w}$ ${\displaystyle n=2}$ ${\displaystyle w_{1}}$ ${\displaystyle 1-w_{1}=w_{2}}$

Это можно обобщить на любое количество агентов: каждая часть, кроме последней, требует не более разрезов, поэтому общее количество требуемых разрезов равно . ${\displaystyle 2(n-1)}$ ${\displaystyle 2(n-1)^{2}}$

Раздел называется пропорциональным, если каждый из двух партнеров получает значение не менее 1/2. Он называется взвешенным пропорциональным (WPR), если партнер получает значение не менее , где — заранее заданные веса, представляющие различные права партнеров на пирог. Вышеуказанная процедура показывает, что в пироге всегда существует раздел WPR со связанными частями. Это контрастирует с некруглым пирогом (интервалом), в котором WPR со связанными частями может не существовать. ${\displaystyle i}$ ${\displaystyle w_{i}}$ ${\displaystyle w_{i}}$

Взвешенное деление без зависти

Если оценки партнеров абсолютно непрерывны по отношению друг к другу, то существует разделение WPR, которое также является взвешенно-свободным от зависти (WEF) и эффективным по Парето (PE), а соотношение между оценками партнеров составляет в точности w ₁ / w ₂ . ^[5]

Доказательство . Для каждого угла t пусть ⁠ ⁠ ${\displaystyle y(t)}$ будет углом, в котором отношение ⁠ ⁠ ${\displaystyle {\frac {v_{1}(t,y(t))}{v_{2}(t,y(t))}}={\frac {w_{1}}{w_{2}}}.}$

Функция ⁠ ⁠ ${\displaystyle v_{1}([t,y(t)])}$ является непрерывной функцией t , которая достигает максимума для некоторого ⁠ ⁠ ${\displaystyle t^{\ast }}$ . Разрежьте пирог радиальными разрезами в ⁠ ⁠ ${\displaystyle t^{\ast }}$ и ⁠ ⁠ ${\displaystyle y(t^{\ast })}$ , отдав кусок ⁠ ⁠ ${\displaystyle [t^{\ast },y(t^{\ast })]}$ партнеру № 1, а дополнение — партнеру № 2. Разделение — WEF, потому что ценность каждого партнера — это ровно его причитающаяся доля. Это PE, потому что доля партнера № 1 максимизирована, поэтому невозможно отдать больше партнеру № 2, не навредив партнеру № 1.

Справедливое разделение

Справедливый раздел — это раздел, при котором субъективная ценность обоих партнеров одинакова (т.е. каждый партнер одинаково счастлив).

Всегда существует раздел пирога между двумя партнерами, который является как свободным от зависти, так и справедливым. Однако в настоящее время не известна процедура для нахождения такого раздела. ^[3]

Когда меры ценности партнеров абсолютно непрерывны по отношению друг к другу (т. е. каждая часть, которая имеет положительную ценность для одного партнера, также имеет положительную ценность для другого партнера), то существует раздел, который свободен от зависти, справедлив и эффективен по Парето. Опять же, процедура неизвестна. ^[3]

Истинное разделение

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

Правило дележа называется диктаторским , если оно распределяет весь торт между одним, заранее определенным партнером.

Правило деления PE является истинным тогда и только тогда, когда оно является диктаторским. ^[4]

Три или более партнеров

1-из-(н+1) процедура длянпартнеры

Айер и Хунс ^[6] были первыми, кто представил специализированный протокол для деления пирога. В их протоколе каждый агент отмечает ( n +1) непересекающихся частей на пироге. Алгоритм дает каждому агенту одну из его/ее частей.

Разделение без зависти для 3 партнеров

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

Но есть более простой алгоритм, который использует преимущество круглости пирога. ^{[7] [3]}

Партнер А непрерывно вращает три радиальных ножа вокруг пирога, сохраняя, по его/ее мнению, 1/3-1/3-1/3 секторов.

Партнер B измеряет стоимость этих 3 секторов. Обычно они все имеют разные стоимости, но в какой-то момент два сектора будут иметь одинаковую стоимость. Почему? Потому что после поворота на 120 градусов сектор, который ранее был самым ценным, теперь становится менее ценным, а другой сектор теперь становится самым ценным. Следовательно, по теореме о промежуточной стоимости , в повороте должна быть позиция, когда партнер B рассматривает два сектора как равные по величине. В этот момент партнер B кричит «стоп».

Затем партнеры выбирают сектора в следующем порядке: C - B - A. Партнер C, конечно, не чувствует зависти, поскольку он выбирает первым; у партнера B есть по крайней мере один больший сектор для выбора; а партнер A считает, что все части в любом случае имеют одинаковую ценность.

Деление без зависти и эффективное по Парето

Для 3 партнеров существуют пирог и соответствующие меры, для которых распределение не является PEEF. ^[8]

Это также верно для более чем 3 партнеров. Это верно даже если все функции ценности аддитивны и строго положительны (т.е. каждый партнер ценит каждый отдельный кусочек пирога). ^[3]

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

Пропорциональное разделение с различными правами

Когда есть 3 или более партнеров с разными правами, необходимо весовое пропорциональное (WPR) разделение. Разделение WPR со связанными частями не всегда существует. ^[5]

Это аналогично результату невозможности для одномерного интервального торта и двух партнеров (см. пропорциональное разрезание торта с различными правами ).

Внешние ссылки

• Земельные участки в Брондбю-Хавебю (Дания) поделены как куски пирога.

Ссылки

1. Стромквист, В.; Вудалл, Д. Р. (1985). «Наборы, на которых согласуются несколько мер». Журнал математического анализа и приложений . 108 : 241–248. doi : 10.1016/0022-247x(85)90021-6 .
2. Гейл, Д. (2009). «Математические развлечения». The Mathematical Intelligencer . 15 : 48–52. doi :10.1007/BF03025257. S2CID  189883039.
3. Барбанель, Дж. Б.; Брамс, С. Дж.; Стромквист, В. (2009). «Разрезание пирога — это не кусок торта». American Mathematical Monthly . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . doi :10.4169/193009709X470407. 
4. Томсон, В. (2006). «Дети плачут на днях рождения. Почему?». Экономическая теория . 31 (3): 501–521. doi :10.1007/s00199-006-0109-3. S2CID  154089829.
5. Brams, SJ; Jones, MA; Klamler, C. (2007). «Пропорциональное разрезание пирога». International Journal of Game Theory . 36 (3–4): 353. doi :10.1007/s00182-007-0108-z. S2CID  19624080.
6. Айер, Картик; Хунс, Майкл (2005). Мирсман, Роберт; Тари, Захир (ред.). «Многоагентные переговоры для справедливого и беспристрастного распределения ресурсов». На пути к осмысленным интернет-системам 2005: CoopIS, DOA и ODBASE . Конспект лекций по информатике. 3760. Берлин, Гейдельберг: Springer: 453–465. doi :10.1007/11575771_29. ISBN 978-3-540-32116-3.
7. Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). «Решение с помощью движущегося ножа для деления торта без зависти четырьмя лицами». Труды Американского математического общества . 125 (2): 547–554. CiteSeerX 10.1.1.104.3390 . doi :10.1090/s0002-9939-97-03614-9. S2CID  17233874. 
8. Stromquist, Walter (июнь 2007 г.). «Пирог, который нельзя разрезать справедливо». Dagstuhl Seminar Proceedings 07261. Получено 15 декабря 2014 г.