splitting cakes with francis su

The classical question "How can we cut a cake fairly?" has been around since antiquity, but what happens when mathematicians and economists focus on the situation? Is there always a way to divide things fairly? Join Harvey Mudd Professor of Mathematics Francis Su as he shares envy-free (and tasty!) solutions to this very human problem.

That was the message on the poster, and it gave as good an introduction to Professor Su's talk as you're going to find. It sounds frivolous, but anyone who has been to a children's birthday party knows that splitting a cake fairly -- or at least in a way that is perceived as fair by a roomful of children -- is not an easy task. "He got a bigger piece!" "She got the flower!" "I didn't get enough icing!" You get the idea...

It's an interesting subject at the intersection of economics and mathematics. So when Sharon asked me to go with her to Mo Math (technically, the National Museum of Mathematics) for a presentation on the topic -- well, great!

Su started with the well known "You cut, I choose" method of splitting a cake (actually, pretty much anything) between two people. One of the people splits the object in two, and the other chooses which piece she wants. From there, he went on to the situation with three people, and then higher numbers. Of course, along the way he had to define fairness. In order to adress the topic with mathematical rigor, it's necessary to have precision in one's definitions. He specified several definitions of a "fair" division:

• Envy free: Each person believes he got the biggest piece
• Proportional: Each person believes he got 1/N (where N is the number of people)*
• Equitable: Each person thinks he got exactly the same percentage of the total as each other person thinks he got.
• Efficient: A division that is not dominated by another. For these purposes, a division is said to dominate another if it is at least as good for each player.**

Su hit that sweet spot, balancing mathematical rigor (or, at least the hint of it) and accessibility for the educated layman. The children in the audience seemed to stay interested, as did the adults, many of whom, had mathematical backgrounds.  For the simpler splits, he explained the methodology in detail. So he continued from the simple "You cut, I choose." For more than two people, he described the "Dubins-Spanier Moving Knife Procedure." But at some point he stopped trying to describe methods in detail, and just explained that solutions exist, but may involve very large numbers of steps.***

It was also interesting getting a flavor of the thinking that leads to the solutions. Su explained and demonstrated Sperner's Lemma, which is at the intersection of topology and combinatorics. And at another point he talked about how he got interested in the cake-splitting problem -- trying to figure out how much rent each person should pay in a shared house where rooms differ in desirability.

Now, if only I weren't dieting -- there was free cake. Su used it to demonstrate the Dubins-Spanier moving knife procedure.

*I describe this by saying that each person thinks he got his fair share.
**We weren't precise to the point of indicating whether the exact definition of "dominate" is written so that all divisions dominate themselves or none do.
***This year, Aziz and McKenzie proved the existence of a method for an envy-free division for n people, but it can take up to n^(n^(n^(n^(n^n)))) steps.