Subscribe to our RSS feed
or
follow us on Twitter.

From theFun Factfiles, here is a Fun Fact at the Advanced level:

Envy-free Cake Division

Figure 1

Say you and a friend wish to share a cake.
What is a "fair" way to split it?
Probably you know this solution:
one cuts, the other chooses.
This is called a fair division algorithm,
because by playing a good strategy,
each player can guarantee she gets at least
50 percent of the cake in her own measure.
See if you can reason why.

Now, what about for 3 people? Is there an
algorithm that guarantees each person what she feels
is the largest piece? Such a
division is called an envy-free division.
Here is a procedure due
to Selfridge and Conway. We mark strategies [in brackets].
Suppose the players are named Alice, Betty, Chuck.

Alice cuts [into what she thinks are thirds].

Betty trims one piece
[to create a 2-way tie for largest], and sets
the trimmings aside.

Let Chuck pick a piece, then Betty, then Alice.
Require Betty to take a trimmed piece if Charlie
does not.
Call the person who tooked the trimmed piece T,
and the other (of Betty and Chuck) NT.

To deal with the trimmings, let
NT cut them [into what she thinks are thirds].

Let players pick pieces in this order:
T, Alice, then NT.

Presentation Suggestions:
Be sure you follow the argument before you present it,
because it can be confusing! Draw pictures.

The Math Behind the Fact:
It is a good exercise to verify why each person is
envy-free by the end of the procedure.
The key observation is that for the trimmings,
Alice has an "irrevocable advantage"
with respect to T, since Alice will never envy T even
if T gets all the trimmings. Thus Alice can pick after T,
and this allows the procedure to terminate in a
finite number of steps.
For 4 or more players, there is an envy-free
solution that is very complex, and can take arbitrarily
long to resolve. See the references.

There are other notions of fairness besides
envy-freeness. Proportional fairness is weaker;
it only demands each person gets what she feels is
at least 1/N of the cake. You might enjoy figuring out
an N-person proportional procedure.

Questions of fairness are considered by mathematicians and economists
in the subject of game theory.

How to Cite this Page:
Su, Francis E., et al. "Envy-free Cake Division."
Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.

S.J. Brams and A.D. Taylor,
Fair Division: from cake-cutting to dispute-resolution,
Cambridge, 1996.
J. Robertson and W. Webb, Cake-cutting Algorithms, AK Peters, 1998.

Keywords: social science, cake cutting, game theory
Subjects: combinatorics, other
Level: Advanced
Fun Fact suggested by: Francis Su
Suggestions? Use this form.