The lone divider procedure is a procedure for

proportional cake-cutting A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/''n'' of t ...

. 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 Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Unive ...

for ''n'' = 3 people. It was later extended by

Harold W. Kuhn Harold William Kuhn (July 29, 1925 – July 2, 2014) was an American mathematician who studied game theory. He won the 1980 John von Neumann Theory Prize along with David Gale and Albert W. Tucker. A former Professor Emeritus of Mathematics ...

to ''n'' > 3, using th
Frobenius–Konig theorem
A description of the cases ''n'' = 3, ''n'' = 4 appears in and the general case is described in.

Description

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.

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 In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...

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 Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have differe ...

The procedure for any ''n''

There are several ways to describe the general case; the shorter description appears in and is based on the concept of

envy-free matching In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch his "thing" with that of another person. This term has been used in se ...

– a matching in which no unmatched agent is adjacent to a matched piece. Step 3. Construct a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

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

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.

Query complexity

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(''n''²) per agent, and O(''n''³) overall. This is much more than required for

last diminisher A last is a mechanical form shaped like a human foot. It is used by shoemakers and cordwainers in the manufacture and repair of shoes. Lasts typically come in pairs and have been made from various materials, including hardwoods, cast iron, an ...

(O(''n'') per agent) and for Even-Paz (O(log ''n'') per agent).

References

{{reflist Fair division protocols Division (mathematics) Number theory Cake-cutting

Description

Steinhaus' procedure for the case ''n'' = 3

The procedure for any ''n''

Query complexity

See also

References