Честная нарезка пирога

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

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

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

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

Модель

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

Эта модель была представлена ​​в 1985 году, а затем в 1993 году.

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

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

Два партнера

Подразделение без зависти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Правдивое разделение

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

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

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

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

Процедура 1 из ( n +1) для n партнеров

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

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

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

Но есть более простой алгоритм, использующий закругленность круга.

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

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

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

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

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

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

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

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

Когда есть 3 или более партнера с разными правами, необходимо взвешенно-пропорциональное разделение (WPR). Подразделение WPR со связанными между собой частями не всегда существует.

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

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

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