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 solved in: Steven J. Brams and Alan D. Taylor, "An Envy-Free Cake Division Protocol," The Amercian Mathematical Monthly, Volume 102, Number 1, p. 9, January 1995

Another approach is in: Oleg Pikhurko, "On Envy-Free Cake Division," The Amercian Mathematical Monthly, Volume 107, Number 8, p. 736, October 2000

The problem of getting an "Equitable, Envy-free, and Efficient Cake Cutting for Two People and Its Application to Divisible Goods" is solved by Michael A. Jones, Mathematics Magazine, Vol. 75, No. 4, October 2002, p. 275.