View source for Robertson–Webb envy-free cake-cutting algorithm

The '''Robertson–Webb protocol''' is a protocol for [[envy-free cake-cutting]] which is also [[near-exact]]. It has the following properties:
* It works for any number (''n'') of partners.
* It works for any set of weights representing different entitlements of the partners.
* The pieces are not necessarily connected, i.e. each partner might receive a collection of small "crumbs".
* The number of queries is finite but unbounded – it is not known in advance how many queries will be needed.

The protocol was developed by [[Jack Robertson (mathematician)|Jack M. Robertson]] and [[William Albert Webb|William A. Webb]]. It was first published in 1997<ref name=journal>{{cite journal|last1=Robertson|first1=Jack M.|last2=Webb|first2=William A.|title=Near exact and envy free cake division|journal=Ars Combinatoria|date=1997|volume=45|pages=97–108}}</ref> and later in 1998.<ref name="book">{{Cite Robertson Webb 1998}}</ref>{{rp|128–133}}

== Problem definition ==
A cake ''C'' has to be divided among ''n'' agents. Each agent ''i'' has:

* A value-measure ''V<sub>i</sub>'' on subsets of ''C'';
* A weight ''w<sub>i</sub>'' representing the fraction of ''C'' to which the agent is entitled.

The sum of all ''w<sub>i</sub>'' is 1. If all agents have the same rights, then ''w<sub>i</sub>'' = 1/''n'' for all ''i'', but in general the weights may be different.

It is required to partition ''C'' into ''n'' subsets, not necessarily connected, such that, for every two agents ''i'' and ''h'':<blockquote><math>V_i(X_i) / w_i \geq V_i(X_h) / w_h</math></blockquote>So ''i'' does not envy ''j'' when taking their different entitlements into account.<ref name=":0">Robertson and Webb do not state this definition explicitly, but it follows from equations (10.1), (10.2), (10.3), (10.4) and the text following them in page 131. In our notation, these equations imply:

<math display="block">\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}</math></ref>

== Details ==
The main difficulty in designing an envy-free procedure for ''n''&nbsp;>&nbsp;2 agents is that the problem is not "divisible". I.e., if we divide half of the cake among ''n''/2 agents in an envy-free manner, we cannot just let the other ''n''/2 agents divide the other half in the same manner, because this might cause the first group of ''n''/2 agents to be envious (e.g., it is possible that A and B both believe they got 1/2 of their half which is 1/4 of the entire cake; C and D also believe the same way; but, A believes that C actually got the entire half while D got nothing, so A envies C).

The Robertson–Webb protocol addresses this difficulty by requiring that the division is not only envy-free but also near-exact. The recursive part of the protocol is the following subroutine.

=== Inputs ===
* Any piece of cake ''X'';
* Any ε > 0;
* ''n'' players, ''A''<sub>1</sub>, …, ''A''<sub>''n''</sub>;
* ''m ≤ n'' players which are identified as "active players", ''A''<sub>1</sub>, …, ''A''<sub>''m''</sub> (the other ''n''&nbsp;−&nbsp;''m'' players are identified as "watching players");
* Any set of ''m'' positive weights ''w''<sub>1</sub>, …, ''w''<sub>''m''</sub>;

=== Output ===
A partition of ''X'' to pieces ''X''<sub>1</sub>, …, ''X''<sub>''m''</sub>, assigned to the ''m'' active players, such that:
* For every active player ''i'' and every other player ''h'' (active or watching):<blockquote><math>V_i(X_i) / w_i \geq V_i(X_h) / w_h</math></blockquote>So agent ''i'' does not envy agent ''h'' when taking their different entitlements into account.<ref name=":0" />
* The division is ε-near-exact with the given weights among all ''n'' players – both active and watching.

=== Procedure ===
''Note: the presentation here is informal and simplified. A more accurate presentation is given in the book.<ref name=book />''

Use a [[near-exact division procedure]] on ''X'' and get a partition which all ''n'' players view as ε-near-exact with weights ''w''<sub>1</sub>, …, ''w''<sub>''m''</sub>.

Let one of the active players (e.g. ''A''<sub>1</sub>) cut the pieces such that the division is exact for him, i.e. for every ''j'': ''V''<sub>1</sub>(''X''<sub>''j''</sub>)/''V''<sub>1</sub>(''X'') = ''w''<sub>''j''</sub>.

If all other active players agree with the cutter, then just give piece ''X''<sub>''i''</sub> to active player ''A''<sub>''i''</sub>. This division is envy-free among the active players, so we are done.

Otherwise, there is some piece ''P'' on which there is disagreement among the active players. By cutting ''P'' to smaller pieces if necessary, we may bound the disagreement such that all players agree that: ''V''(''P'')/''V''(''X'') < ε.

Split the active players to two camps: the "optimists" who think that ''P'' is more valuable, and the "pessimists" who think that ''P'' is less valuable. Let δ be the difference between the values, such that for every optimist ''i'' and every pessimist ''j'': ''V''<sub>''i''</sub>(''P'')/''V''<sub>''i''</sub>(''X'')&nbsp;–&nbsp;''V''<sub>''j''</sub>(''P'')/''V''<sub>''j''</sub>(''X'')&nbsp;>&nbsp;''δ''.

Divide the remaining cake, ''X''&nbsp;−&nbsp;''P'', into pieces ''Q'' and ''R'', such that the division is near-exact among all ''n'' players.

Assign ''P''&nbsp;∪&nbsp;''Q'' to the optimists. Because they believe that ''P'' is valuable, they necessarily believe that ''P''&nbsp;∪&nbsp;''Q'' is sufficiently valuable to more than cover their due share.

Assign ''R'' to the pessimists. Because they believe that ''P'' is less valuable, they necessarily believe that the remainder, ''R'', is sufficiently valuable to more than cover ''their'' due share.

At this point we have partitioned the active players to two camps, each collectively claiming complementary portions of the cake and each camp is more than satisfied with their collective portion.

It remains to divide each portion of the cake to the players in its camp. This is done by two recursive applications of [[#Procedure|the procedure]]:
* Recursively partition ''P''&nbsp;∪&nbsp;''Q'' among the optimists (i.e. the optimists are active and all other players are only watching).
* Recursively partition ''R'' among the pessimists.

In both applications, the near-exactness factor should be at most δ. Because the resulting partition is ''δ''-near-exact among all ''n'' players, the partition among the optimists doesn't cause envy among the pessimists and vice versa. Thus the over-all division is both envy-free and near-exact.

== See also ==
* [[Brams–Taylor protocol]] – another envy-free protocol with disconnected pieces and finite unbounded runtime. Does not guarantee near-exactness.
* [[Simmons–Su protocols]] – envy-free protocol which guarantees connected pieces but the runtime might be infinite. Does not guarantee near-exactness.
*[[Robertson–Webb query model]]

== References ==
{{Reflist}}

{{DEFAULTSORT:Robertson-Webb protocol}}
[[Category:Fair division protocols]]
[[Category:Cake-cutting]]