Одинокий разделитель - Lone divider

В одинокий разделитель процедура - это процедура для пропорциональная резка торта. Он включает в себя разнородный и делимый ресурс, такой как праздничный торт, и п партнеры с разными предпочтениями по разным частям торта. Это позволяет п людей разделить торт между ними так, чтобы каждый получил кусок стоимостью не менее 1 /п от общей стоимости согласно его собственной субъективной оценке.

Процедура была разработана Хьюго Штайнхаус для п= 3 человека.[1] Позже он был расширен Гарольд В. Кун к п> 3, используя Теорема Фробениуса-Кенига.[2] Описание кейсов п=3, п= 4 появляется в [3] :31–35 а общий случай описан в [4]:83–87.

Описание

Для удобства мы нормализуем оценки так, чтобы стоимость всего торта была равна п для всех агентов. Цель состоит в том, чтобы дать каждому агенту по фигуре не менее 1.

Шаг 1. Один произвольно выбранный игрок называется разделитель, разрезает торт на п фигуры, ценность которых в его глазах равна 1.

Шаг 2. Друг друга п-1 партнер оценивает результат п штук и говорит, какие из этих предметов он считает «приемлемыми», т. е. стоящими не менее 1.

Теперь игра продолжается в соответствии с ответами игроков на шаге 3. Сначала представим случай п= 3 и тогда общий случай.

Процедура Штейнхауза по делу п=3

Есть два случая.

  • Случай A: По крайней мере, один из неразделителей отмечает две или более фигур как приемлемые. Затем третий партнер выбирает приемлемую фигуру (по принципу ячеек у него должен быть хотя бы один); второй партнер выбирает подходящую фигуру (у него раньше было как минимум две, поэтому остается как минимум один); и, наконец, разделитель выбирает последний кусок (для разделителя допустимы все части).
  • Случай B: оба партнера отмечают только одну фигуру как приемлемую. Тогда есть хотя бы одна деталь, подходящая только для разделителя. Делитель берет этот кусок и идет домой. Эта фишка стоит меньше 1 для оставшихся двух партнеров, поэтому оставшиеся две фишки для них стоят как минимум 2. Они делят это между собой, используя разделяй и выбирай.

Порядок действий при любом п

Есть несколько способов описать общий случай; более короткое описание появляется в [5] и основан на концепции соответствие без зависти - соответствие, в котором ни один несоответствующий агент не соседствует с согласованным элементом.

Шаг 3. Построить двудольный граф г = (X + Y, E), в котором каждая вершина из Икс агент, каждая вершина в Y это кусок, и есть грань между агентом Икс и кусок у если только Икс ценности у как минимум 1.

Шаг 4. Найдите максимальную мощность соответствие без зависти в г. Обратите внимание, что разделитель примыкает ко всем п штук, так что |Nг(Икс)|= п ≥ | X | (где Nг(Икс) - множество соседей Икс в Y). Следовательно, существует непустое соответствие без зависти.

Шаг 5. Передайте каждую подобранную деталь соответствующему агенту. Обратите внимание, что каждый подобранный агент имеет значение не менее 1 и поэтому благополучно возвращается домой.

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

Смотрите также

использованная литература

  1. ^ Штейнхаус, Гюго (1948). «Проблема справедливого разделения». Econometrica. 16 (1): 101–4. JSTOR  1914289.
  2. ^ Кун, Гарольд (1967), «Об играх честного разделения», Очерки математической экономики в честь Оскара Моргенштерна, Princeton University Press, стр. 29–37, заархивировано оригинал на 2019-01-16, получено 2019-01-15
  3. ^ Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Честное разделение: от нарезки торта до разрешения споров. Издательство Кембриджского университета. ISBN  0-521-55644-9.
  4. ^ Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы резки торта: будьте честны, если можете. Натик, Массачусетс: А. К. Петерс. ISBN  978-1-56881-076-8. LCCN  97041258. ПР  2730675W.
  5. ^ Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (28.01.2019). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv:1901.09527v2. Bibcode:2019arXiv190109527A. Цитировать журнал требует | журнал = (Помогите)