Алгоритм разрезания торта без зависти Робертсона-Уэбба

Протокол Робертсона-Уэбба — это протокол для разрезания торта без зависти , который также является почти точным . Он обладает следующими свойствами:

Работает для любого количества ( n ) партнеров.
Он работает для любого набора весов, представляющих различные права партнеров.
Детали не обязательно связаны между собой, то есть каждый партнер может получить набор маленьких «крошек».
Число запросов конечно, но не ограничено — заранее неизвестно, сколько запросов потребуется.

Протокол был разработан Джеком М. Робертсоном и Уильямом А. Уэббом. Впервые он был опубликован в 1997 году ^[1] , а затем в 1998 году. ^[2]^{: 128–133}

Определение проблемы

Торт C должен быть разделен между n агентами. Каждый агент i имеет:

Мера ценности V _i на подмножествах C ;
Вес w _i представляет собой долю C, на которую имеет право агент.

Сумма всех w _i равна 1. Если все агенты имеют одинаковые права, то w _i = 1/ n для всех i , но в общем случае веса могут быть разными.

Требуется разбить C на n подмножеств, не обязательно связанных, так, чтобы для каждых двух агентов i и h :

$V_{i}(X_{i})/w_{i}\geq V_{i}(X_{h})/w_{h}$

Поэтому i не завидует j, если принять во внимание их различные права. ^[3]

Подробности

Основная сложность в разработке процедуры, свободной от зависти, для n > 2 агентов заключается в том, что проблема не является «делимой». То есть, если мы разделим половину торта между n / 2 агентами без зависти, мы не можем просто позволить другим n / 2 агентам разделить другую половину таким же образом, потому что это может вызвать зависть у первой группы из n / 2 агентов (например, возможно, что A и B оба считают, что они получили 1/2 своей половины, что составляет 1/4 всего торта; C и D также считают так же; но A считает, что C на самом деле получил всю половину, а D не получил ничего, поэтому A завидует C).

Протокол Робертсона-Уэбба решает эту проблему, требуя, чтобы деление было не только свободным от зависти, но и почти точным. Рекурсивная часть протокола — это следующая подпрограмма.

Входы

Любой кусок торта X ;
Любое ε > 0;
n игроков, A ₁ , …, A _n ;
m ≤ n игроков, которые идентифицируются как «активные игроки», A ₁ , …, A _m (остальные n − m игроков идентифицируются как «наблюдающие игроки»);
Любой набор из m положительных весов w ₁ , …, w _m ;

Выход

Разбиение X на части X ₁ , …, X _m , назначенные m активным игрокам, таким образом, что:

Для каждого активного игрока i и каждого другого игрока h (активного или наблюдающего):
$V_{i}(X_{i})/w_{i}\geq V_{i}(X_{h})/w_{h}$
Таким образом, агент i не завидует агенту h, если принять во внимание их различные права. ^[3]
Деление является ε-почти точным с заданными весами среди всех n игроков – как активных, так и наблюдающих.

Процедура

Примечание: изложение здесь неформальное и упрощенное. Более точное изложение дано в книге. ^[2]

Используйте почти точную процедуру деления на X и получите разбиение, которое все n игроков рассматривают как ε-почти точное с весами w ₁ , …, w _m .

Пусть один из активных игроков (например, A ₁ ) разрежет куски так, чтобы деление было точным для него, т.е. для каждого j : V ₁ ( X _j )/ V ₁ ( X ) = w _j .

Если все остальные активные игроки согласны с резцом, то просто отдайте часть X _i активному игроку A _i . Этот раздел свободен от зависти среди активных игроков, поэтому мы закончили.

В противном случае есть некоторая часть P , по которой между активными игроками есть разногласия. Разрезая P на более мелкие части, если необходимо, мы можем ограничить разногласия таким образом, что все игроки согласятся, что: V ( P )/ V ( X ) < ε.

Разделим активных игроков на два лагеря: «оптимистов», которые считают, что P более ценен, и «пессимистов», которые считают, что P менее ценен. Пусть δ будет разницей между значениями, такой, что для каждого оптимиста i и каждого пессимиста j : V _i ( P )/ V _i ( X ) – V _j ( P )/ V _j ( X ) > δ .

Разделим оставшийся торт, X − P , на куски Q и R так, чтобы деление было почти точным между всеми n игроками.

Назначьте оптимистам P ∪ Q. Поскольку они верят, что P ценно, они обязательно верят, что P ∪ Q достаточно ценно, чтобы покрыть их долю.

Назначьте пессимистам R. Поскольку они считают, что P менее ценен, они обязательно верят, что остаток, R , достаточно ценен, чтобы покрыть их причитающуюся долю.

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

Остается разделить каждую часть торта между игроками своего лагеря. Это делается двумя рекурсивными применениями процедуры:

Рекурсивно разделим P ∪ Q среди оптимистов (т.е. оптимисты активны, а все остальные игроки только наблюдают).
Рекурсивно распределим R среди пессимистов.

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

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

Протокол Брамса–Тейлора – еще один протокол без зависти с несвязанными частями и конечным неограниченным временем выполнения. Не гарантирует почти точность.
Протоколы Симмонса–Су — протокол без зависти, гарантирующий связность частей, но время выполнения может быть бесконечным. Не гарантирует почти точную точность.
Модель запроса Робертсона-Уэбба

Ссылки

^ Робертсон, Джек М.; Уэбб, Уильям А. (1997). «Почти точное и свободное от зависти деление торта». Ars Combinatoria . 45 : 97–108.
^ ab Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
^ ab Робертсон и Уэбб не формулируют это определение явно, но оно следует из уравнений (10.1), (10.2), (10.3), (10.4) и текста, следующего за ними на странице 131. В наших обозначениях эти уравнения подразумевают: ${\begin{align}V_{i}(X_{i})\geq w_{i}V_{i}(X)\\V_{i}(X_{h})\leq w_{h}V_{i}(X)\\V_{h}(X_{h})\geq w_{h}V_{h}(X)\\V_{h}(X_{i})\leq w_{i}V_{h}(X)\end{align}}$