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

редактировать

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

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

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

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

Содержание

  • 1 Модель
  • 2 Два партнера
    • 2.1 Разделение без зависти
    • 2.2 Разделение без зависти и эффективное по Парето
      • 2.2.1 Ограничения аддитивности
    • 2.3 Разделение на основе консенсуса и взвешенное пропорциональное деление
    • 2.4 Взвешенное деление без зависти
    • 2.5 Справедливое деление
    • 2.6 Правдивое деление
  • 3 Три или более партнеров
    • 3.1 Разделение без зависти для 3 партнеров
    • 3.2 Без зависти и Парето-эффективное деление
    • 3.3 Пропорциональное деление с разными правами
  • 4 Внешние ссылки
  • 5 Ссылки

Модель

Круговая диаграмма обычно моделируется как одномерный интервал [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 не всегда существует.

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

Разделение называется точным разделением (также известным как согласованное разделение ), если значение части i {\ displaystyle i}я равно точно wi {\ displaystyle w_ {i}}w_ {i} в соответствии со всеми партнерами, где wi {\ displaystyle w_ {i}}w_ {i} - предварительно заданные веса.

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

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

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

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

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

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

Функция v 1 ([t, y (t)]) {\ displaystyle v_ {1} ([t, y (t)])}{\ displaystyle v_ {1} ([t, y (t)])} является непрерывная функция от t, которая достигает максимума для некоторого t ∗ {\ displaystyle t ^ {\ ast}}t ^ \ ast . Разрежьте пирог радиальными разрезами в точках t ∗ {\ displaystyle t ^ {\ ast}}t ^ \ ast и y (t ∗) {\ displaystyle y (t ^ {\ ast})}{\ displaystyle y (t ^ {\ ast})} , что дает кусок [t ∗, y (t ∗)] {\ displaystyle [t ^ {\ ast}, y (t ^ {\ ast})]}{\ displaystyle [t ^ {\ ast}, y (t ^ {\ ast})]} к партнеру №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-х партнеров (см. справедливое разрезание торта # Взвешенное пропорциональное деление ).

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

Ссылки

Последняя правка сделана 2021-05-20 09:12:59
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте