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

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

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

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

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

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

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

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

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

Перегородки Рамзи

Предположим, торт нужно разделить между Алисой и Джорджем, Алиса имеет право на 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.

МакЭвани, Робертсон и Уэбб обобщить эту идею, используя концепцию разбиений Рамсея (названную в честь теории Рамсея ).

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

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

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

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

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

$FindMinimalRamsey(a,b)$:

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

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

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

Разрезать почти пополам

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

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

Общая идея аналогична протоколу Even-Paz : $CutNearHalves(a,b)$:

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

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

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

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

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

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

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

Алгоритмы иррациональных пособий

Если права не являются рациональными числами, методы, основанные на клонировании, не могут использоваться, поскольку знаменатель бесконечен. Шишидо и Цзэн представили алгоритм под названием mark-cut-choose , который также может обрабатывать иррациональные права, но с неограниченным количеством сокращений.

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

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

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

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

Стоимость Алисы	2	2	2	2
Ценность Джорджа	1	3	3	1

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

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

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

• Попросите каждого агента i отметить x такой, что V _i (0, x )=1/2.
• Упорядочивайте агентов в порядке возрастания их отметок, произвольно разрывая связи.
• Добавьте агентов в указанном выше порядке в P. набор Остановитесь непосредственно перед тем, как общий вес агентов в P превысит 1/2.
• называется t , а набор агентов после t называется Q. Первый агент, который не был добавлен в P , Сейчас:
  • Все агенты в 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 ): ${\text{Cuts}}(n+1)\leq \max _{1\leq k\leq n-1}(1+{\text{Cuts}}(k+1)+{\text{Cuts}}(n-k+1))$. Добавление начального условия ${\text{Cuts}}(2)=2$ дает заявленное число ${\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 (как в верхней оценке).

См. также

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

Далл'Альо и Макчерони доказал существование пропорционального разрезания пирога с различными правами, даже когда предпочтения агентов описываются неаддитивными отношениями предпочтений, при условии, что они удовлетворяют определенным аксиомам.