The lone divider procedure is a procedure for proportional cake-cutting. It involves a heterogenous and divisible resource, such as a birthday cake, and n partners with different preferences over different parts of the cake. It allows the n people to divide the cake among them such that each person receives a piece with a value of at least 1/n of the total value according to his own subjective valuation.
The procedure was developed by Hugo Steinhaus for n = 3 people.[1] It was later extended by Harold W. Kuhn to n > 3, using the Frobenius–Konig theorem. A description of the cases n = 3, n = 4 appears in and the general case is described in.
For convenience we normalize the valuations such that the value of the entire cake is n for all agents. The goal is to give each agent a piece with a value of at least 1.
Step 1. One player chosen arbitrarily, called the divider, cuts the cake into n pieces whose value in his/her eyes is exactly 1.
Step 2. Each of the other n − 1 partners evaluates the resulting n pieces and says which of these pieces he considers "acceptable", i.e., worth at least 1.
Now the game proceeds according to the replies of the players in step 3. We present first the case n = 3 and then the general case.
There are two cases.
There are several ways to describe the general case; the shorter description appears in [2] and is based on the concept of envy-free matching – a matching in which no unmatched agent is adjacent to a matched piece.
Step 3. Construct a bipartite graph G = (X + Y, E) in which each vertex in X is an agent, each vertex in Y is a piece, and there is an edge between an agent x and a piece y iff x values y at least 1.
Step 4. Find a maximum-cardinality envy-free matching in G. Note that the divider is adjacent to all n pieces, so |NG(X)| = n ≥ |X| (where NG(X) is the set of neighbors of X in Y). Hence, a non-empty envy-free matching exists.
Step 5. Give each matched piece to its matched agent. Note that each matched agent has a value of at least 1, and thus goes home happily.
Step 6. Recursively divide the remaining cake among the remaining agents. Note that each remaining agent values each piece given away at less than 1, so he values the remaining cake at more than the number of agents, so the precondition for recursion is satisfied.
At each iteration, the algorithm asks the lone divider at most n mark queries, and each of the other agents at most n eval queries. There are at most n iterations. Therefore, the total number of queries in the Robertson-Webb query model is O(n2) per agent, and O(n3) overall. This is much more than required for last diminisher (O(n) per agent) and for Even-Paz (O(log n) per agent).