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 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.