Lone divider
The lone divider procedure is a procedure for proportional cake-cutting.
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. 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.
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. 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. 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. === Steinhaus' procedure for the case n = 3 === There are two cases.
Case A: At least one of the non-dividers marks two or more pieces as acceptable. Then, the third partner picks an acceptable piece (by the pigeonhole principle he must have at least one); the second partner picks an acceptable piece (he had at least two before, so at least one remains); and finally the divider picks the last piece (for the divider, all pieces are acceptable).
Case B: Both other partners mark only one piece as acceptable. Then, there is at least one piece that is acceptable only for the divider. The divider takes this piece and goes home.
This piece is worth less than 1 for the remaining two partners, so the remaining two pieces are worth at least 2 for them. They divide it among them using divide and choose. 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 if 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 |N G (X)| = n ≥ |X| (where N G (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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369066524 under CC BY-SA 4.0; modifications have been made.