N-Person Fair Division
decision/division
Problem
N-Person Fair Division If two people want to divide a pie but do not trust each other, they can still ensure that each gets a fair share by using the technique that one person cuts and the other person chooses. Generalize this technique to more than two people. Take care to ensure that no one can be cheated by a coalition of the others.
Show solution
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.