Честная нарезка пирогов - Fair pie-cutting

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

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

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

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

Модель

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

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

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

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

Два партнера

Разделение без зависти

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

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

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

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

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

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

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

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

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

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

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

Более того, когда оценки обоих партнеров не аддитивны (поэтому ни один из них не может играть роль ротатора), подразделение PEEF не всегда существует.^[4]

Согласованное деление и взвешенное пропорциональное деление

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

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

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

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

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

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

Доказательство. На любой угол т, позволять ${ Displaystyle у (т)}$ быть углом, в котором отношение ${ Displaystyle { гидроразрыва {v_ {1} (t, y (t))} {v_ {2} (t, y (t))}} = { frac {w_ {1}} {w_ {2} }}.}$

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

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

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

Всегда существует разделение пирога между двумя партнерами, что одновременно и без зависти, и по справедливости. Однако в настоящее время не известна процедура поиска такого раздела.^[3]

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

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

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

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

Правило разделения PE истинно тогда и только тогда, когда оно диктаторское.^[4]

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

Дивизион без зависти для 3-х партнеров

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

Но есть более простой алгоритм, который использует округлость пирога.^[6][3]

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

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

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

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

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

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

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

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

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

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

внешняя ссылка

• Земельные участки в Brøndby Haveby (Дания) делятся, как кусок пирога.

Рекомендации