Robertson–Webb envy-free cake-cutting algorithm

The Robertson-Webb protocol is a protocol for envy-free cake-cutting. Its input is a "cake" (a heterogeneous resource) and n partners with different preferences over different portions of the cake. Its output is a division of the cake to n disjoint subsets, each subset possibly containing a large number of disconnected pieces, such that each partner believes that his subset is at least as good as any subset given to another partner.

The protocol uses a finite number of queries to the partners, but, the number of queries is unbounded.

The protocol was first published in 1997 and later in 1998.

Details

The protocol actually finds a division which is not only envy-free but also a near-exact division.

INPUTS:

• Any piece of cake X;
• Any ε>0;
• Any set of positive weights $w_{1},w_{2},...,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 (no active player prefers another piece to his own);
• The division is ε-near-exact among all players - both active and watching.

The protocol uses, as a subroutine, a near-exact division procedure.