previous page: 149 decision/allais.p
page up: Puzzles FAQ
next page: 151 decision/dowry.p

150 decision/division.p


This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

150 decision/division.p

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.


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.

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.


Continue to:

previous page: 149 decision/allais.p
page up: Puzzles FAQ
next page: 151 decision/dowry.p