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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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