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

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

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

Описание

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

Шаг 1 . Один игрок, выбранный произвольно, называемый делителем , разрезает торт на n частей, ценность которых в его/ее глазах равна ровно 1.

Шаг 2 . Каждый из остальных n − 1 партнеров оценивает полученные n кусочков и говорит, какой из этих кусочков он считает «приемлемым», т. е. ценным не менее 1.

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

Процедура Штейнгауза для случая n = 3

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

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

Процедура для любого n

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

Шаг 3 . Постройте двудольный граф G = ( X + Y , E ), в котором каждая вершина в X является агентом, каждая вершина в Y является частью, и существует ребро между агентом x и частью y тогда и только тогда, когда x имеет значение y не менее 1.

Шаг 4 . максимальной мощности Найдите паросочетание без зависти в G . Обратите внимание, что разделитель примыкает ко всем n частям, поэтому | Н _грамм ( Икс )| знак равно п ≥ | Х | (где NG ₎ ( X ) — множество соседей X в Y . Следовательно, существует непустое паросочетание без зависти.

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

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

Сложность запроса

На каждой итерации алгоритм запрашивает у единственного делителя не более n запросов на отметки , а у каждого из остальных агентов — не более n оценочных запросов. Существует не более n итераций. Следовательно, общее количество запросов в модели запросов Робертсона-Уэбба равно O( n ²) на агента и O( n ³) общий. Это намного больше, чем требуется для последнего уменьшающего (O( n ) на агента) и для Эвен-Паза (O(log n ) на агента).

См. также

Другие процедуры решения той же задачи см. в пропорциональном разрезании торта .
Одним из преимуществ одиночного разделителя является то, что его можно модифицировать для получения симметричной процедуры разрезания торта .
Ярмарка дележа: метод «одиночного разделителя» при «разрезании узла» .

Ссылки

^ Штайнхаус, Хьюго (1948). «Проблема справедливого дележа». Эконометрика . 16 (1): 101–4. JSTOR 1914289 .
^ Кун, Гарольд (1967), «Об играх справедливого дележа» , Очерки по математической экономике в честь Оскара Моргенштерна , Princeton University Press, стр. 29–37, заархивировано из оригинала 16 января 2019 г. , получено 1 января 2019 г. -15
^ Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .
^ Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .
^ Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (2022). «Сопоставления без зависти в двудольных графах и их приложения к справедливому дележу». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . дои : 10.1016/j.ins.2021.11.059 . S2CID 170079201 .

[steinhaus48-1] Штайнхаус, Хьюго (1948). «Проблема справедливого дележа». Эконометрика . 16 (1): 101–4. JSTOR 1914289 .

[2] Кун, Гарольд (1967), «Об играх справедливого дележа» , Очерки по математической экономике в честь Оскара Моргенштерна , Princeton University Press, стр. 29–37, заархивировано из оригинала 16 января 2019 г. , получено 1 января 2019 г. -15

[bt96-3] Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .

[4] Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .

[5] Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (2022). «Сопоставления без зависти в двудольных графах и их приложения к справедливому дележу». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . дои : 10.1016/j.ins.2021.11.059 . S2CID 170079201 .

[1]

[2]

[3]

[4]

[5]