Задача разделить пирог - это вариант честно разрезанного торта проблема, в которой ресурс, который нужно разделить, является круговым.
В качестве примера рассмотрим праздничный торт в виде диска. Пирог следует разделить между несколькими детьми так, чтобы ни один ребенок не завидовал другому ребенку (как в стандартной задаче разрезания торта), с дополнительным ограничением, заключающимся в том, что разрезы должны быть радиальными, чтобы каждый ребенок получил круговой сектор.
Возможным применением модели круговой диаграммы может быть разделение береговой линии острова на соединенные участки.
Другое возможное применение - разделение периодического времени, например разделение дневного цикла на периоды «дежурства».
Круговая диаграмма обычно моделируется как одномерный интервал [0,2π ] (или [0,1]), в котором идентифицируются две конечные точки.
Эта модель была представлена в 1985 году, а затем в 1993 году.
Каждая процедура правильного разрезания торта может также применяться к разрезанию пирога, просто игнорируя тот факт, что две конечные точки идентифицированы. Например, если процедура разрезания торта привела к делению, в котором Алиса получает [0,1 / 3], а Джордж - [1 / 3,1], то мы дадим Алисе круговой сектор в 120 градусов, а Джорджу оставшееся сектор с 240 градусами.
Разделение пирогов становится более интересным, когда мы рассматриваем вопросы эффективности, поскольку при разрезании пирогов возможно большее количество разделов.
Разделение называется без зависти (EF), если каждый партнер считает, что его фигура по крайней мере такой же ценный, как и другой предмет.
EF-деление пирога всегда можно найти с помощью разделить и выбрать : один партнер разрезает пирог на два сектора, которые он считает равными, а другой партнер выбирает сектор, который он считает лучшим. Но для пирога возможно лучшее деление.
Разделение называется Эффективным по Парето (PE), если никакое другое разделение не лучше для одного партнера и не хуже для другого.. Часто эффективность по Парето оценивается только по отношению к подмножеству всех возможных подразделений. Т.е. только деления на два смежных сектора (деления с минимальным количеством разрезов).
Разделение называется PEEF, если оно является одновременно PE и EF.
Когда оценки партнеров являются (аддитивными) показателями, следующая процедура с подвижным ножом гарантирует разделение, которое является EF и PE относительно разделений на два смежных сектора.
Один партнер (Вращатель) держит два радиальных ножа над пирогом таким образом, что, по ее мнению, два сектора пирога, определяемые этими ножами, имеют одинаковую ценность. Затем она непрерывно вращает эти ножи по всему кругу пирога, поддерживая это равное значение секторов, пока ножи не вернутся в исходное положение.
Другой партнер (Выборщик) наблюдает за этим процессом в течение всего цикла. Затем в следующем цикле он определяет позицию, которая, по его мнению, дает максимальное значение одному из двух определенных таким образом секторов. Выборщик получает этот сектор, а Ротатор - другой сектор.
Этот раздел, очевидно, является EF, так как Rotator безразличен между двумя секторами, Chooser получает лучший сектор. Это PE, потому что нет раздела, который дал бы Chooser большее значение и оставил бы значение 1/2 для Rotator.
Вышеупомянутая процедура работает, только если функция значения Rotator аддитивна, так что равные доли всегда имеют одинаковое значение 1/2. Если ее ценность не аддитивна, то деление все равно будет свободным от зависти, но не обязательно эффективным по Парето.
Более того, когда оценки обоих партнеров не аддитивны (так что ни один из них не может играть роль ротатора), разделение PEEF не всегда существует.
Разделение называется точным разделением (также известным как согласованное разделение ), если значение части равно точно
в соответствии со всеми партнерами, где
- предварительно заданные веса.
Предположим, что сумма всех весов равна 1, и значение круговой диаграммы для всех агентов также нормализовано к 1. По теореме Стромквиста-Вудолла для любого веса существует подмножество
, который представляет собой объединение не более чем
секторов, которые все партнеры значение ровно
. Для агентов
это означает, что всегда существует согласованное разделение пирога со связанными секторами: дайте агенту 1 сектор, который стоит ровно
для обоих агентов, и дать агенту 2 оставшийся сектор, который стоит
для обоих агентов (альтернативное доказательство см.).
Это можно обобщить на любое количество агентов: каждая часть, кроме последней, требует не более сокращений, поэтому общее количество требуемых сокращений составляет
.
Деление называется пропорциональным, если каждый из двух партнеров получает значение не менее 1/2. Он называется взвешенным пропорциональным (WPR), если партнер получает значение не менее
, где
- заранее заданные веса, представляющие различные права партнеров на торт. Приведенная выше процедура показывает, что в круговой диаграмме всегда существует разделение WPR со связанными частями. Это контрастирует с некруглым пирогом (интервалом), в котором WPR с соединенными частями может не существовать.
Если оценки партнеров абсолютно непрерывны по отношению друг к другу, то существует разделение WPR, которое также не требует взвешивания на зависти (WEF) и Эффективность Парето (PE), и соотношение между значениями партнеров в точности равно w 1/w2.
Доказательство . Для каждого угла t пусть будет углом, при котором отношение
Функция является непрерывная функция от t, которая достигает максимума для некоторого
. Разрежьте пирог радиальными разрезами в точках
и
, что дает кусок
к партнеру №1 и дополнение к партнеру №2. Разделение является WEF, потому что ценность каждого партнера в точности соответствует его доле. Это PE, потому что доля партнера №1 максимальна, поэтому невозможно дать партнеру №2 больше, не нанеся вреда партнеру №1.
Разделение по справедливости - это разделение, в котором субъективная ценность обоих партнеров одинакова (т.е. каждый партнер одинаково счастлив).
Всегда существует разделение пирога между двумя партнерами, которое не вызывает зависти и является справедливым. Однако в настоящее время не известна процедура для поиска такого разделения.
Когда меры ценности партнеров абсолютно непрерывны по отношению друг к другу (т.е. каждая часть, которая имеет положительное значение для одного партнера, также имеет положительное значение значение для другого партнера), то существует разделение, свободное от зависти, справедливое и эффективное по Парето. Опять же, процедура не известна.
Правило деления называется правдивым, если сообщение о функциях истинного значения является слабо доминирующей стратегией в этом правиле. То есть невозможно получить какую-либо ценность путем неверного представления оценок.
Правило разделения называется диктаторским, если оно передает весь торт одному, заранее определенному партнеру.
Правило разделения PE истинно тогда и только тогда, когда оно диктаторское.
движущиеся ножи Stromquist процедуру можно использовать для разрезания торта в одном измерении, поэтому очевидно, что ее также можно использовать для разрезания пирога.
Но есть более простой алгоритм, который использует преимущество округлости пирога.
Партнер A непрерывно вращает три радиальных ножа вокруг пирога, поддерживая то, что он / она считает 1 / 3-1 / 3-1 / 3 сектора.
Партнер B измеряет значение этих 3 секторов. Обычно все они имеют разные значения, но в какой-то момент два сектора будут иметь одинаковое значение. Зачем? Потому что после поворота на 120 градусов сектор, который раньше был самым ценным, стал менее ценным, а другой сектор стал самым ценным. Следовательно, согласно теореме о промежуточном значении, должна быть позиция в ротации, когда партнер B считает два сектора равными по наибольшему значению. В этот момент партнер B называет «стоп».
Затем партнеры выбирают сектора в порядке: C - B - A. Партнер C, конечно, не испытывает зависти, потому что он первый выбирает; у партнера B есть по крайней мере один больший сектор на выбор; а партнер А думает, что все фигуры в любом случае имеют одинаковую ценность.
Для трех партнеров существует круговая диаграмма и соответствующие меры, для которых нет распределения PEEF.
Это также верно для других чем 3 партнера. Это верно, даже если все функции значений являются аддитивными и строго положительными (т.е. каждый партнер оценивает каждый отдельный бит круговой диаграммы).
В обоих примерах используются меры, которые почти одинаковы, но с очень точными настройками. Поскольку меры почти одинаковы, легко найти распределения пирога, которые почти не вызывают зависти и почти не доминируют. Неизвестно, можно ли найти примеры, в которых расхождения намного больше.
Когда есть 3 или более партнеров с разными правами, требуется взвешенно-пропорциональное (WPR) деление. Разделение WPR со связанными частями не всегда существует.
Это аналогично результату невозможности для одномерного интервального торта и 2-х партнеров (см. справедливое разрезание торта # Взвешенное пропорциональное деление ).