hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, 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.

1. Alice cuts [into what she thinks are thirds].
2. Betty trims one piece [to create a 2-way tie for largest], and sets the trimmings aside.
3. 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.
4. To deal with the trimmings, let NT cut them [into what she thinks are thirds].
5. 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.

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

References:
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
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
3.64
current
rating
Click to rate this Fun Fact...
*   Awesome! I totally dig it!
*   Fun enough to tell a friend!
*   Mildly interesting
*   Not really noteworthy
and see the most popular Facts!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!