==> decision/division.s <==
N-Person Fair Division
Number the people from 1 to N. Person 1 cuts off a piece of the pie.
Person 2 can either diminish the size of the cut off piece or pass.
The same for persons 3 through N. The last person to touch the piece
must take it and is removed from the process. Repeat this procedure
with the remaining N - 1 people, until everyone has a piece.
References:
Luce and Raiffa, "Games and Decisions", Wiley, 1957, p. 366
Kenneth Rebman, "How To Get (At Least) A Fair Share of the Cake",
in Mathematical Plums, Ross Honsberger, ed, Dolciani Mathematical
Expostions Number 4, published by the MAA.
There is a cute result in combinatorics called the Marriage Theorem.
A village has n men and n women, such that for all 0 < k <= n and for any
set of k men there are at least k women, each of whom is in love with at least
one of the k men. All of the men are in love with all of the women :-}.
The theorem asserts that there is a way to arrange the village into n
monogamous couplings.
The Marriage Theorem can be applied to the Fair Pie-Cutting Problem.
One player cuts the pie into n pieces. Each of the players labels
some non-null subset of the pieces as acceptable to him. For reasons
given below he should "accept" each piece of size > 1/n, not just the
best piece(s). The pie-cutter is required to "accept" all of the pieces.
Given a set S of players let S' denote the set of pie-pieces
acceptable to at least one player in S. Let t be the size of the largest
set (T) of players satisfying |T| > |T'|. If there is no such set, the
Marriage Theorem can be applied directly. Since the pie-cutter accepts
every piece we know that t < n.
Choose |T| - |T'| pieces at random from outside T', glue them
together with the pieces in T' and let the players in T repeat the game
with this smaller (t/n)-size pie. This is fair since they all rejected
the other n-t pieces, so they believe this pie is larger than t/n.
The remaining n-t players can each be assigned one of the remaining
n-t pie-pieces without further ado due to the Marriage Theorem. (Otherwise
the set T above was not maximal.)
The problem of getting not just a fair solution, but an envy-free solution,
is not solved. A reference to this problem:
David Gale, "Dividing a Cake," in Mathematical Entertainments,
Mathematical Intelligencer, Vol. 15, No. 1, Winter 1993, p. 50,
contains references to work by Steven Breams and Alan Taylor.