Пропорциональная резка торта с разными правами - Proportional cake-cutting with different entitlements

в ярмарка разрезания торта Проблема, партнеры часто имеют разные права. Например, ресурс может принадлежать двум акционерам, таким образом, Алиса владеет 8/13, а Джордж - 5/13. Это приводит к критерию взвешенная пропорциональность (WPR): есть несколько весов ${ displaystyle w_ {i}}$ в сумме до 1, и каждый партнер ${ 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}}$ шт.

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

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

Ramsey перегородки

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

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

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

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

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

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

Этот пример можно обобщить, используя концепцию Ramsey перегородки (назван в честь Теория Рамсея ).^[1]^:36–41^[2]

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

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

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

Если

{ displaystyle p_ {1}

, и

{ 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 а, б-а}

.

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

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

Закажите входы так, чтобы ${ displaystyle a$ .
От себя ${ displaystyle a}$ .
Если ${ displaystyle a = b-a = 1}$ , затем нажмите ${ displaystyle 1,1,1}$ и закончить.
Если ${ Displaystyle б-а neq 1}$ , тогда ${ displaystyle FindMinimalRamsey (а, б-а)}$ .

Как только минимальный раздел Рамсея найден, его можно использовать для поиска подразделения WPR, уважающего права.

Алгоритм требует как минимум ${ Displaystyle журнал _ { phi} мин (а, б)}$ порезы, где ${ 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, и оставшийся пирог можно разделить с помощью вырезать и выбрать.

Общая идея похожа на Протокол Even-Paz:^[1]^:42–44 ${ displaystyle CutNearHalves (a, b)}$ :

Закажите входы так, чтобы ${ displaystyle a$ . Предположим, Алиса имеет право ${ displaystyle b / (a + b)}$ и Джордж имеет право ${ Displaystyle а / (а + Ь)}$ .
Попросите Джорджа разрезать торт почти на половинки, то есть:
- если ${ displaystyle a + b}$ даже тогда Джордж разрезает торт на два равных в его глазах;
- если ${ displaystyle a + b}$ странно, то Джордж разрезает торт на две части, коэффициент оценки которых равен ${ Displaystyle (а + b-1) / 2: (а + b + 1) / 2}$ в его глазах.
По крайней мере, одна из фигур стоит для Алисы не меньше стоимости, заявленной Джорджем; отдай этот кусок Алисе.
Предположим, что кусок, взятый Алисой, имеет ценность ${ displaystyle c / (a + b)}$ , где ${ Displaystyle с в {(а + б-1) / 2, (а + б) / 2, (а + б + 1) / 2)}$ . Вызов ${ displaystyle CutNearHalves (b, a-c)}$ .

Алгоритм сокращения почти половин требует не более ${ Displaystyle журнал _ {2} мин (а, б)}$ разрезает, поэтому он всегда более эффективен, чем алгоритм разбиения Рамсея.

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

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

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

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

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

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

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

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

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

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

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

Ценность Алисы	2	2	2	2
Значение Георгия	1	3	3	1

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

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

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

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

использованная литература

^ ^а ^б ^c ^d Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы резки торта: будьте честны, если можете. Натик, Массачусетс: А. К. Петерс. ISBN 978-1-56881-076-8. LCCN 97041258. ПР 2730675W.
^ МакЭвани, Кевин; Робертсон, Джек; Уэбб, Уильям (1992). «Рамсеевские разбиения целых чисел и справедливые деления». Комбинаторика. 12 (2): 193. Дои:10.1007 / bf01204722.
^ Чех, Агнес; Флейнер, Тамаш (01.06.2020). «Сложность разрезания торта с неравными долями». ACM-транзакции на алгоритмах. 16 (3): 29:1–29:21. Дои:10.1145/3380742. ISSN 1549-6325.
^ ^а ^б Шишидо, Харунор; Цзэн, Дао-Чжи (1999). «Отметить-выбрать-вырезать алгоритмы для справедливого и строго справедливого разделения». Групповое решение и переговоры. 8 (2): 125–137. Дои:10.1023 / а: 1008620404353. ISSN 0926-2644.
^ Чех, Агнес; Флейнер, Тамаш (2018), «Сложность разрезания торта с неравными долями», Алгоритмическая теория игр, Springer International Publishing, стр. 19–30, arXiv:1709.03152, Дои:10.1007/978-3-319-99660-8_3, ISBN 9783319996592
^ Brams, S.J .; Jones, M. A .; Кламлер, К. (2007). «Пропорциональная нарезка пирогов». Международный журнал теории игр. 36 (3–4): 353. Дои:10.1007 / s00182-007-0108-z.
^ Обратите внимание, что существует связное деление, в котором отношения между значениями партнеров равны 3: 1 - дайте Алисе два крайних левых фрагмента и 8/11 третьего фрагмента (значение 4 + 16/11 = 60/11) и дайте Джордж оставшиеся 3/11 и крайний правый срез (значение 1 + 9/11 = 20/11). Однако этот раздел не является WPR, поскольку ни один партнер не получает свою долю.
^ Сегал-Халеви, Эрель (14.03.2018). «Резка торта с разными правами: сколько нужно отрезов?». Журнал математического анализа и приложений. 480: 123382. arXiv:1803.05470. Дои:10.1016 / j.jmaa.2019.123382.
^ Экипаж, Логан; Нараянан, Бхаргав; Спиркл, Софи (16 сентября 2019). «Непропорциональное разделение». arXiv:1909.07141 [math.CO ].
^ Цзэн, Дао-Чжи (2000). «Примерные процедуры без зависти». Игровая практика: материалы из прикладной теории игр. Библиотека теории и решений. 23. Springer. С. 259–271. Дои:10.1007/978-1-4615-4627-6_17. ISBN 9781461546276.

[rw98-1] а ^б ^c ^d Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы резки торта: будьте честны, если можете. Натик, Массачусетс: А. К. Петерс. ISBN 978-1-56881-076-8. LCCN 97041258. ПР 2730675W.

[2] МакЭвани, Кевин; Робертсон, Джек; Уэбб, Уильям (1992). «Рамсеевские разбиения целых чисел и справедливые деления». Комбинаторика. 12 (2): 193. Дои:10.1007 / bf01204722.

[3] Чех, Агнес; Флейнер, Тамаш (01.06.2020). «Сложность разрезания торта с неравными долями». ACM-транзакции на алгоритмах. 16 (3): 29:1–29:21. Дои:10.1145/3380742. ISSN 1549-6325.

[:0-4] а ^б Шишидо, Харунор; Цзэн, Дао-Чжи (1999). «Отметить-выбрать-вырезать алгоритмы для справедливого и строго справедливого разделения». Групповое решение и переговоры. 8 (2): 125–137. Дои:10.1023 / а: 1008620404353. ISSN 0926-2644.

[:1-5] Чех, Агнес; Флейнер, Тамаш (2018), «Сложность разрезания торта с неравными долями», Алгоритмическая теория игр, Springer International Publishing, стр. 19–30, arXiv:1709.03152, Дои:10.1007/978-3-319-99660-8_3, ISBN 9783319996592

[6] Brams, S.J .; Jones, M. A .; Кламлер, К. (2007). «Пропорциональная нарезка пирогов». Международный журнал теории игр. 36 (3–4): 353. Дои:10.1007 / s00182-007-0108-z.

[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. Дои:10.1016 / j.jmaa.2019.123382.

[9] Экипаж, Логан; Нараянан, Бхаргав; Спиркл, Софи (16 сентября 2019). «Непропорциональное разделение». arXiv:1909.07141 [math.CO ].

[10] Цзэн, Дао-Чжи (2000). «Примерные процедуры без зависти». Игровая практика: материалы из прикладной теории игр. Библиотека теории и решений. 23. Springer. С. 259–271. Дои:10.1007/978-1-4615-4627-6_17. ISBN 9781461546276.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]