Процедура «одиночный делящий»

Процедура «одиночный делящий» — это процедура пропорционального разрезания торта. Процедура предназначена для распределения неоднородного делимого ресурса, такого, как торт на день рождения, и предусматривает n участников дележа с различными предпочтениями для разных частей торта. Процедура позволяет для n человек поделить торт между собой так, что каждый участник получит по меньшей мере ${\tfrac {1}{n}}$ полного значения согласно его собственной (субъективной) оценке.

Процедуру разработал Гуго Штейнгауз для n=3 человек. Позднее её расширил Гарольд Кун для n>3, используя теорему Фробениуса — Кёнига. Описание случаев n=3 и n=4 приведено в статье Брамса и Тейлора, а общий случай описан в статье Робертсона и Уэбба.

Описание

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

Шаг 1. Случайным образом выбирается один игрок, который назовём делящим, и он делит торт на n кусков, каждый из которых в его/её глазах стоит ровно 1.

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

Теперь, в зависимости от ответов, игра переходит в шаг 3. Мы представим случай n=3, а затем общий случай.

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

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

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

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

Есть несколько способов описать общий случай. Наиболее короткое описание приведено в статье Сегал-Халеви и Айгера-Хорева. Оно опирается на концепцию паросочетания без зависти — паросочетания, в котором никакой не входящий в паросочетание агент не смежен куску, входящему в паросочетание.

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

Шаг 4. Находим максимальное по мощности (по числу сочетаний) паросочетание без зависти в G. Заметим, что делящий соединён со всеми n кусками, так что $|N_{G}(X)|=n\geqslant |X|$ (где $N_{G}(X)$ представляет собой множество соседей X в Y). Следовательно, непустое свободное от зависти паросочетание существует.

Шаг 5. Отдаём каждый кусок из пары соответствующему агенту (то есть из той же пары в паросочетании). Заметим, что каждый такой агент оценивает своё значение по меньшей мере в 1, так что может идти домой счастливым.

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

См. также

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