Date: Fri, 1 Jul 2005 13:59:50 +0000
Mime-Version: 1.0 (Produced by PhpWiki 1.3.11p1)
Content-Type: application/x-phpwiki;
  pagename=Division%20Solution;
  flags="";
  author=68.163.237.20;
  version=1;
  lastmodified=1120226390;
  author_id=68.163.237.20;
  hits=422;
  charset=iso-8859-1
Content-Transfer-Encoding: binary

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.