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

В задаче о справедливом разрезании торта партнеры часто имеют разные права. Например, ресурс может принадлежать двум акционерам, таким образом, что Алиса владеет 8/13, а Джордж владеет 5/13. Это приводит к критерию взвешенной пропорциональности (WPR): существует несколько весов , которые в сумме дают 1, и каждый партнер должен получить по крайней мере часть ресурса по своей собственной оценке. ${\displaystyle w_{i}}$ ${\displaystyle i}$ ${\displaystyle w_{i}}$

Напротив, в более простой пропорциональной установке разрезания торта веса равны: для всех ${\displaystyle w_{i}=1/n}$ ${\displaystyle i}$

Для поиска деления WPR можно использовать несколько алгоритмов.

Клонирование

Предположим, что все веса являются рациональными числами с общим знаменателем . Таким образом, веса равны , причем . Для каждого игрока создайте клонов с одинаковой мерой ценности. Общее количество клонов равно . Найдите пропорциональное распределение торта между ними. Наконец, раздайте каждому партнеру куски его клонов. ${\displaystyle D}$ ${\displaystyle p_{1}/D,\dots ,p_{n}/D}$ ${\displaystyle p_{1}+\cdots +p_{n}=D}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$ ${\displaystyle D}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$

Робертсон и Уэбб ^{[1] : 36} показывают более простую процедуру для двух партнеров: Алиса разрезает торт на куски, равные по ее мнению; Джордж выбирает самые ценные по его мнению куски, а Алиса забирает оставшиеся куски. ${\displaystyle D}$ ${\displaystyle p_{G}}$ ${\displaystyle p_{A}}$

Эта простая процедура требует разрезов, которые могут быть очень большими. Например, если Алиса имеет право на 8/13, а Джордж имеет право на 5/13, то в начальном разделе необходимо 13-1=12 разрезов. ${\displaystyle D-1}$

Количество требуемых запросов составляет ${\displaystyle D\lceil \log _{2}(D)\rceil .}$

Разделы Рамсея

Предположим, что торт нужно разделить между Алисой и Джорджем, Алиса имеет право на 8/13, а Джордж имеет право на 5/13. Торт можно разделить следующим образом.

• Алиса разрезает торт на 6 частей в пропорции 5:3:2:1:1:1 .
• Джордж отмечает те произведения, которые имеют для него, по крайней мере, ту ценность, которую упомянула Алиса.

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

Случай 1: Есть подмножество отмеченных частей, сумма которых равна 5. Например, если Джордж отмечает 3-ю часть и три 1-ю часть. Затем это подмножество отдается Джорджу, а остаток отдается Алисе. Теперь у Джорджа есть по крайней мере 5/13, а у Алисы ровно 8/13.

Случай 2: Есть подмножество неотмеченных частей, сумма которых равна 8. Например, если Джордж отметит часть из 3 и только одну часть из 1. Затем это подмножество отдается Алисе, а остаток отдается Джорджу. Теперь у Алисы ровно 8, а Джордж отказался от суммы меньше 8, поэтому у него есть по крайней мере 5/13.

Можно доказать, что хорошие случаи являются единственно возможными. То есть, каждое подмножество 5:3:2:1:1:1 ЛИБО имеет подмножество, сумма которого равна 5, ЛИБО его дополнение имеет подмножество, сумма которого равна 8. Следовательно, приведенный выше алгоритм всегда находит распределение WPR с заданными соотношениями. Количество используемых разрезов равно всего 5.

МакЭвани, Робертсон и Уэбб ^{[1] : 36–41  [2]} обобщают эту идею, используя концепцию разбиений Рамсея (названную в честь теории Рамсея ).

Формально: если и являются положительными целыми числами, то разбиение называется разбиением Рамсея для пары , если для любого подсписка , либо существует подсписок , сумма которого равна , либо существует подсписок , сумма которого равна . ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$ ${\displaystyle P}$ ${\displaystyle k_{1}+k_{2}}$ ${\displaystyle k_{1},k_{2}}$ ${\displaystyle L\subseteq P}$ ${\displaystyle L}$ ${\displaystyle k_{1}}$ ${\displaystyle P\setminus L}$ ${\displaystyle k_{2}}$

В примере выше и разбиение равно 5:3:2:1:1:1, что является разбиением Рамсея. Более того, это самое короткое разбиение Рамсея в данном случае, поэтому оно позволяет нам использовать небольшое количество разрезов. ${\displaystyle k_{1}=8}$ ${\displaystyle k_{2}=5}$

Разбиения Рамсея всегда существуют. Более того, всегда существует единственное кратчайшее разбиение Рамсея. Его можно найти с помощью простого варианта алгоритма Евклида . Алгоритм основан на следующей лемме: ^{[1] : 143–144}

Если , и является разбиением , и , то является разбиением . Более того, является минимальным разбиением Рамсея для пары тогда и только тогда, когда является минимальным разбиением Рамсея для пары . ${\displaystyle p_{1}<a<b}$ ${\displaystyle P=(p_{1},\dots ,p_{n})}$ ${\displaystyle b}$ ${\displaystyle P'=(b,p_{1},\dots ,p_{n})}$ ${\displaystyle P'}$ ${\displaystyle a+b}$ ${\displaystyle P'}$ ${\displaystyle a,b}$ ${\displaystyle P}$ ${\displaystyle a,b-a}$

Эта лемма приводит к следующему рекурсивному алгоритму.

${\displaystyle FindMinimalRamsey(a,b)}$:

1. Упорядочим входные данные таким образом, чтобы . ${\displaystyle a<b}$
2. Толкать . ${\displaystyle a}$
3. Если , то нажимаем и завершаем. ${\displaystyle a=b-a=1}$ ${\displaystyle 1,1}$
4. Если , то . ${\displaystyle b-a\neq 1}$ ${\displaystyle FindMinimalRamsey(a,b-a)}$

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

Алгоритму нужно как минимум разрезов, где — золотое сечение. В большинстве случаев это число лучше, чем делать разрезы. Но если , то разрезы нужны, так как единственное разбиение Рамсея пары — это последовательность с единицами. ${\displaystyle \log _{\phi }\min(a,b)}$ ${\displaystyle \phi =(1+{\sqrt {5}})/2}$ ${\displaystyle a+b-1}$ ${\displaystyle a=1}$ ${\displaystyle b=a+b-1}$ ${\displaystyle b,1}$ ${\displaystyle b+1}$

Разрезанный почти пополам

Предположим снова, что Алиса имеет право на 8/13, а Джордж имеет право на 5/13. Торт можно разделить следующим образом.

• Джордж разрезает торт на две части в соотношении 7:6.
• Алиса выбирает одну из частей, которая стоит для нее не меньше ее заявленной стоимости. Рассмотрим два случая:
  • Алиса выбирает 7. Затем Алиса имеет право на еще 1, а оставшуюся часть следует разделить в соотношении 5:1.
  • Алиса выбирает 6. Затем Алиса имеет право на еще 2, а оставшуюся часть следует разделить в соотношении 5:2.
• В обоих случаях оставшийся кусок меньше и соотношение меньше. В конце концов соотношение становится 1:1 и оставшийся торт можно разделить с помощью cut and choose .

Общая идея аналогична протоколу Эвена-Паса : ^{[1] : 42–44} : ${\displaystyle CutNearHalves(a,b)}$

1. Упорядочите входные данные таким образом, чтобы . Предположим, что Алиса имеет право на , а Джордж имеет право на . ${\displaystyle a<b}$ ${\displaystyle b/(a+b)}$ ${\displaystyle a/(a+b)}$
2. Попросите Джорджа разрезать торт примерно пополам, то есть:
   • если четно, то Джордж разрезает торт на две равные по его мнению части; ${\displaystyle a+b}$
   • если нечетно, то Джордж разрезает торт на две части, соотношение стоимости которых находится в его глазах. ${\displaystyle a+b}$ ${\displaystyle (a+b-1)/2:(a+b+1)/2}$
3. По крайней мере одна из частей имеет для Алисы ценность не менее заявленной Джорджем; отдайте эту часть Алисе.
4. Предположим, что часть, взятая Алисой, имеет стоимость , где . Колл . ${\displaystyle c/(a+b)}$ ${\displaystyle c\in \{(a+b-1)/2,(a+b)/2,(a+b+1)/2)}$ ${\displaystyle CutNearHalves(b,a-c)}$

Алгоритм разрезания почти пополам требует максимум разрезов, поэтому он всегда эффективнее алгоритма разбиения Рэмси. ${\displaystyle \log _{2}\min(a,b)}$

Алгоритм cut-near-halves не всегда оптимален. Например, предположим, что соотношение составляет 7:3.

• Для деления почти пополам может потребоваться не менее четырех разрезов: сначала Джордж разрезает в соотношении 5:5, и Алиса получает 5. Затем Алиса разрезает в соотношении 3:2; предположим, Джордж выбирает 2. Затем Джордж разрезает в соотношении 2:1; предположим, Алиса выбирает 1. Наконец, они разрезают и выбирают остаток.
• Мы можем добиться большего, позволив Джорджу разрезать в соотношении 6:4. Если Алиса выбирает 4, то соотношение становится 3:3, и мы можем немедленно использовать «разрезать и выбрать». Если Алиса выбирает 6, то соотношение становится 3:1. Алиса разрезает в соотношении 2:2, Джордж выбирает 2, и нам нужен еще один шаг «разрезать и выбрать». В общем, требуется максимум три разреза.

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

Алгоритм можно обобщить на n агентов; количество требуемых запросов равно ${\displaystyle n(n-1)\lceil \log _{2}(D)\rceil .}$

Cseh и Fleiner ^[3] представили алгоритм для деления многомерного торта среди любого количества агентов с любыми правами (включая иррациональные права) за конечное количество запросов. Их алгоритм требует запросов в модели запросов Робертсона-Уэбба ; таким образом, он более эффективен, чем клонирование агентов и разрезание почти пополам. Они доказывают, что эта сложность времени выполнения является оптимальной. ${\displaystyle 2(n-1)\lceil \log _{2}(D)\rceil }$

Алгоритмы для нерациональных прав

Когда права не являются рациональными числами, методы, основанные на клонировании, не могут быть использованы, поскольку знаменатель бесконечен. Шишидо и Зенг представили алгоритм, называемый «отметить-отрезать-выбрать », который также может обрабатывать иррациональные права, но с неограниченным числом сокращений. ^[4]

Алгоритм Чеха и Флейнера также можно адаптировать для работы с нерациональными правами в конечном числе запросов. ^[5]

Количество требуемых разрезов

Помимо количества требуемых запросов, также интересно минимизировать количество требуемых разрезов, чтобы разделение не было слишком дробным. Алгоритмы Шишидо-Зенга дают справедливое разделение с не более чем разрезами и строго-справедливое разделение с не более чем разрезами. ^[4] ${\displaystyle 2\cdot 3^{n-2}}$ ${\displaystyle 4\cdot 3^{n-2}}$

В худшем случае, по крайней мере, могут потребоваться разрезы. Брамс, Джонс и Кламлер ^[6] показывают пример для n = 2. Торт, состоящий из четырех последовательных регионов, должен быть разделен между Алисой и Джорджем, чьи оценки следующие: ${\displaystyle 2(n-1)}$

Обратите внимание, что общая стоимость торта составляет 8 для обоих партнеров. Если , то Алиса имеет право на стоимость не менее 6. Чтобы дать Алисе ее должную долю в связанном куске, мы должны дать ей либо три самых левых куска, либо три самых правых куска. В обоих случаях Джордж получает кусок стоимостью всего 1, что меньше его должной доли 2. Чтобы добиться дележа WPR в этом случае, мы должны дать Джорджу его должную долю в центре торта, где его стоимость относительно велика, но тогда Алиса получит два несвязанных куска. ^[7] ${\displaystyle w_{A}\geq 0.75}$

Сигал-Халеви ^[8] показывает, что если торт круглый (т. е. две конечные точки идентифицированы), то связное разделение WPR для двух человек всегда возможно; это следует из теоремы Стромквиста–Вудалла . Рекурсивно применяя эту теорему для нахождения точных разделений , можно получить разделение WPR, используя не более разрезов, когда n является степенью 2, и аналогичное число, когда n является общим. ${\displaystyle 2n\cdot (\log _{2}n-1)+2}$

Крю, Нараянан и Спиркл ^[9] улучшили эту верхнюю границу до 3 n -4, используя следующий протокол:

• Попросите каждого агента i отметить x таким образом, чтобы V _i (0, x )=1/2.
• Расположите агентов в порядке возрастания их оценок, разрывая связи произвольно.
• Добавьте агентов в указанном выше порядке в множество P. Остановитесь непосредственно перед тем, как общий вес агентов в P превысит 1/2.
• Первый агент, который не был добавлен в P, называется t , а множество агентов после t называется Q. Теперь:
  • Все агенты в значении P (0, x ) не менее 1/2, а их общий вес не более 1/2;
  • Все агенты в значении Q ( x,1 ) не менее 1/2, а их общий вес не более 1/2;
  • Агент t оценивает как (0,x), так и ( x,1 ) ровно в 1/2.
• Если и P, и Q непусты, то агент t делится между P и Q таким образом, что общий вес в каждом наборе равен ровно 1/2. Торт разрезается в точке x , и процедура продолжается рекурсивно. Это приводит к следующему рекуррентному соотношению (где k — число агентов в P , не включая клон агента t ): . Добавление начального условия дает заявленное число . ${\displaystyle {\text{Cuts}}(n+1)\leq \max _{1\leq k\leq n-1}(1+{\text{Cuts}}(k+1)+{\text{Cuts}}(n-k+1))}$ ${\displaystyle {\text{Cuts}}(2)=2}$ ${\displaystyle {\text{Cuts}}(n)\leq 3n-4}$

• Более сложный случай — P пуст (случай, когда Q пуст, аналогичен). Это подразумевает, что вес t составляет не менее 1/2, и все агенты оценивают (0, x ) не более 1/2. В этом случае мы находим некоторый y, такой, что агент t оценивает (0, y ) в точности w _t , и пытаемся разбить агентов на P и Q, как и раньше. Если снова один из этих наборов пуст, то мы знаем, что все агенты оценивают (0, y ) не менее w _t . Следовательно, по теореме о промежуточном значении должно быть значение z в ( x , y ), для которого один из агентов, который не является t , оценивает (0, z ) в точности так же, как t . Затем мы можем разрезать торт в точке z и повторить процедуру, как в первом случае.

Точное количество требуемых разрезов остается открытым вопросом. Самый простой открытый случай — когда есть 3 агента и веса равны 1/7, 2/7, 4/7. Неизвестно, равно ли количество требуемых разрезов 4 (как в нижней границе) или 5 (как в верхней границе).

Смотрите также

Цзэн ^[10] представил алгоритм для приблизительного разрезания торта без зависти с различными правами.

Далл'Альо и МакЧерони ^{[11] : Теория 3} доказала существование пропорционального разрезания торта с различными правами, даже когда предпочтения агентов описываются неаддитивными отношениями предпочтений, при условии, что они удовлетворяют определенным аксиомам.

Ссылки

1. Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258. OL  2730675W.
2. Макэвани, Кевин; Робертсон, Джек; Уэбб, Уильям (1992). «Разбиения Рамсея целых чисел и справедливые деления». Combinatorica . 12 (2): 193. doi :10.1007/bf01204722. S2CID  19376212.
3. Cseh, Ágnes; Fleiner, Tamás (2020-06-01). «Сложность разрезания торта с неравными долями». ACM Transactions on Algorithms . 16 (3): 29:1–29:21. arXiv : 1709.03152 . doi : 10.1145/3380742. ISSN  1549-6325. S2CID  218517351.
4. Шишидо, Харунор; Цзэн, Дао-Чжи (1999). «Алгоритмы пометки-выбора-отсечения для справедливого и строго справедливого деления». Групповое решение и переговоры . 8 (2): 125–137. doi :10.1023/a:1008620404353. ISSN  0926-2644. S2CID  118080310.
5. Чех, Агнес; Флейнер, Тамаш (2018), «Сложность разрезания торта с неравными долями», Алгоритмическая теория игр , Springer International Publishing, стр. 19–30, arXiv : 1709.03152 , doi : 10.1007/978-3-319-99660-8_3, ISBN 9783319996592, S2CID  19245769
6. 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.
7. Обратите внимание, что существует связанное деление, в котором соотношения между значениями партнеров составляют 3:1 — отдайте Алисе два самых левых куска и 8/11 третьего куска (значение 4+16/11=60/11) и отдайте Джорджу оставшиеся 3/11 и самый правый кусок (значение 1+9/11=20/11). Однако это разделение не является WPR, поскольку ни один из партнеров не получает причитающуюся ему долю.
8. Сегал-Халеви, Эрель (14.03.2018). «Разрезание торта с разными правами: сколько разрезов нужно?». Журнал математического анализа и приложений . 480 : 123382. arXiv : 1803.05470 . doi : 10.1016/j.jmaa.2019.123382. S2CID  3901524.
9. Крю, Логан; Нараянан, Бхаргав; Спиркл, Софи (16.09.2019). «Непропорциональное деление». arXiv : 1909.07141 [math.CO].
10. Цзэн, Дао-Чжи (2000). «Приблизительные процедуры без зависти». Игровая практика: вклад из прикладной теории игр . Библиотека теории и принятия решений. Том 23. Springer. С. 259–271. doi :10.1007/978-1-4615-4627-6_17. ISBN 9781461546276.
11. Далл'Альо, М.; Макчерони, Ф. (2009). «Спорные земли» (PDF) . Игры и экономическое поведение . 66 : 57–77. дои : 10.1016/j.geb.2008.04.006.