Протокол Робертсона — Уэбба

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

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

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

Детали

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

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

Вход

Любой кусок торта X;
Любое $\varepsilon >0$ ;
n участников, $A_{1},\dots ,A_{n}$ ;
m<n участников, которые принимаются «активными игроками», $A_{1},\dots ,A_{m}$ (остальные $n-m$ участников принимаются «наблюдателями»);
Любое множество из m положительных весов $w_{1},\dots ,w_{m}$ ;

Выход

Разбиение X на части $X_{1},\dots ,X_{m}$ , назначаемые m активным игрокам так, что

В разбиении отсутствует зависть для заданных весов среди m активных участников. То есть для любой пары активных игроков $A_{i}$ и $A_{j}$ игрок $A_{i}$ верит, что ценность его куска $X_{i}$ , делённая на ценность другого куска $X_{j}$ , не меньше величины ${\tfrac {w_{i}}{w_{j}}}$ .
Разбиение почти $\varepsilon$ -точно для заданных весов среди всех n игроков, как активных, так и неактивных.

Процедура

Замечание: описание процедуры здесь не является формальным и упрощено. Более точное описание дано в книге Робертсона и Уэбба^[2].

Используем процедуру почти точного дележа для X и получаем разрезание, которое все n игроков видят как почти $\varepsilon$ -точное с весами $w_{1},\dots w_{m}$ .

Пусть один из активных игроков (пусть это будет $A_{1}$ ) режет куски так, что разбиение точно для него, то есть для любого $j:{\tfrac {V_{1}(X_{j})}{V_{1}(X)}}=w_{j}$ .

Если все другие игроки соглашаются с таким разрезанием, то просто отдаём кусок $X_{i}$ активному игроку $A_{i}$ . В этом разбиении не будет зависти, так что мы получили желаемое.

В противном случае есть некий кусок P, о котором есть разногласие среди активных игроков. Путём разрезания P на более мелкие куски, если необходимо, мы можем ограничить разногласие так, что все игроки согласятся, что ${\tfrac {V(P)}{V(X)}}<\varepsilon$ .

Разобьём активных игроков на два лагеря: «оптимистов», считающих, что P ценнее, и «пессимистов», считающих, что P менее ценен. Пусть $\delta$ будет такой разностью между оценками, так что для любого оптимиста i и любого пессимиста j выполняется ${\tfrac {V_{i}(P)}{V_{i}(X)}}-{\tfrac {V_{j}(P)}{V_{j}(X)}}>\delta$ .

Разобьём остаток торта $X-P$ на куски Q и R, так, что разбиение будет почти точным для всех n игроков.

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

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

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

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

Рекурсивно делим часть $P\cup Q$ среди оптимистов (то есть оптимисты активны, остальные лишь наблюдают).
Рекурсивно делим часть R среди пессимистов.

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

См. также

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

Примечания

↑ Robertson, Webb, 1997, с. 97–108.
↑ ¹ ² Robertson, Webb, 1998, с. 128–133.

Литература

Jack M. Robertson, William A. Webb. Near exact and envy free cake division // Ars Combinatoria. — 1997. — Т. 45.
Jack Robertson, William Webb. Cake-Cutting Algorithms: Be Fair If You Can.. — Natick, Massachusetts: A. K. Peters, 1998. — ISBN 978-1-56881-076-8.

[_49fb79011f0e332f-1] Robertson, Webb, 1997, с. 97–108.

[_f9627c041d37a8c5-2] ¹ ² Robertson, Webb, 1998, с. 128–133.

[1]

[2]