Robertson–Webb envy-free cake-cutting algorithm

The Robertson-Webb protocol is a protocol for envy-free fair cake-cutting with the following properties:

• It works for any number (n) of 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 resulting division is not only envy-free but also near-exact.

The protocol was developed by Jack Robertson and William Webb. It was first published in 1997 and later in 1998.

Details

The main difficulty in designing an envy-free procedure for n>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;
• Any set of positive weights w₁, ..., w_n;
• "Active players", A₁, ..., A_n;
• "Watching players", B₁, ..., B_m;

OUTPUT: A partition of X to pieces X₁, ..., X_n, assigned to the n active players, such that:

• The division is envy-free for the active players with the given weights. I.e., for every two active players A_i and A_j, player A_i believes that the value of his piece X_i divided by the value of the other piece X_j is at least w_i / w_j.
• The division is ε-near-exact among all players - both active and watching - with the given weights.

PROCEDURE:

If n=1 (and w₁=1), then just give the entire cake to the single active player, A₁, and return.

Use a near-exact division procedure to produce a partition X₁, ..., X_n, which all players (both active and watching) view as ε-near-exact with weights w₁, ..., w_n.

Let one of the active players (A₁) cut the pieces such that the division is exact for him, i.e. for every j: V₁(X_j)=w_j V₁(X).

If all other active players agree with the cutter, then the division is also envy-free among the active players, and 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) < ε/4.

Order the active players in a decreasing order of their V(P)/V(X). Since there is disagreement, there is at least one location where sequence is strictly decreasing, i.e., there is a smallest k such that, the value of P for player k is strictly more than its value for player k+1.

Divide the remaining cake, X-P, into pieces Q and R in a near-exact manner;

Have the first k active players share P