I work on the mathematics of sharing resources, which has led me to consider emotions such as envy, behaviour such as risk-taking and the best way to cut a cake.
Like, I suspect, many women, my wife enjoys eating dessert but not ordering it. I therefore dutifully order what I think she’ll like, cut it in half and invite her to choose a piece.
This is a sure-fire recipe for marital accord. Indeed, many mathematicians, economists, political scientists and others have studied this protocol and would agree. The protocol is known as the “cut-and-choose” procedure. I cut. You choose.
Cut-and-choose
Cut-and-choose is not limited to the dining table – it dates back to antiquity. It appears nearly 3,000 years ago in Hesiod’s poem Theogeny where Prometheus divides a cow and Zeus selects the part he prefers.
In more recent times, cut-and-choose has been enshrined in the UN’s 1982 Convention of the Law of the Sea where it was proposed as a mechanism to resolve disputes when dividing the seabed for mining.
To study the division of cake, cows and the seabed in a more formal way, various mathematical models have been developed. As with all models, these need to make a number of simplifying assumptions.
One typical assumption is that the people employing the cut-and-choose method are risk-averse. They won’t adopt a risky strategy that may give them less cake than a more conservative strategy.
With such assumptions in place, we can then prove what properties cake cutting procedures have and don’t have. For instance, cut-and-choose is envy free.
You won’t envy the cake I have, otherwise you would have taken this piece. And I won’t envy the piece you have, as the only risk-averse strategy is for me to cut the cake into two parts that I value equally.
On the other hand, the cutting of the cake is not totally equitable since the player who chooses can get cake that has more than half the total value for them.
With two players, it’s hard to do better than cut-and-choose. But I should record that my wife argues with me about this.
She believes it favours the second player since the first player inevitably can’t divide the cake perfectly and the second player can capitalise on this. This is the sort of assumption ignored in our mathematical models.
My wife might prefer the moving-knife procedure which doesn’t favour either player. A knife is moved over the cake, and either player calls “cut” when they are happy with the slice.
Again, this will divide the cake in such a way that neither player will envy the other (else they would have called “cut” themselves).
Three’s a crowd
Unfortunately, moving beyond two players increases the complexity of cutting cake significantly.
With two players, we needed just one cut to get to an envy free state. With three players, a complex series of five cuts of the cake might be needed. Of course, only two cuts are needed to get three slices.
The other three cuts are needed to remove any envy. And with four players, the problem explodes in our face.
An infinite number of cuts may be required to get to a situation where no one envies another’s cake. I’m sure there’s some moral here about too many cake cutters spoiling the dessert.
There are many interesting extensions of the problem. One such extension is to indivisible goods.
Suppose you have a bag of toys to divide between two children. How do you divide them fairly? As a twin myself, I know that the best solution is to ensure you buy two of everything.
It’s much more difficult when your great aunt gives you one Zhu Zhu pet, one Bratz doll and three Silly Bandz bracelets to share.
Online
More recently, I have been studying a version of the problem applicable to online settings. In such problems, not all players may be available all of the time. Consider, for instance, allocating time on a large telescope.
Astronomers will have different preferences for when to use the telescope depending on what objects are visible, the position of the sun, etcetera. How do we design a web-based reservation system so that astronomers can choose observation times that is fair to all?
We don’t want to insist all astronomers log in at the same time to decide an allocation. And we might have to start allocating time on the telescope now, before everyone has expressed their preferences. We can view this as a cake-cutting problem where the cake is made up of the time slots for observations.
The online nature of such cake-cutting problems poses some interesting new challenges.
How can we ensure that late-arriving players don’t envy cake already given to earlier players? The bad news is that we cannot now achieve even a simple property like envy freeness.
No procedure can guarantee situations where players don’t envy one another. But more relaxed properties are possible, such as not envying cake allocated whilst you are participating in the cutting of the cake.
Ham sandwich
There’s a brilliantly named piece of mathematics due to Arthur H. Stone and [John Tukey](http://www.morris.umn.edu/~sungurea/introstat/history/w98/Tukey.html, the Ham Sandwich Theorem which proves we can always cut a three-layered cake perfectly with a single cut.
Suppose we have three objects. Let’s call them “the top slice of bread”, “the ham filling” and “the bottom slice of bread”. Or if you prefer “the top layer” of the cake, “the middle layer” and “the bottom layer”.
The ham sandwich theorem proves a single slice can always perfectly bisect the three objects. Actually, the ham sandwich theorem works in any number of dimensions: any n objects in n-dimensional space can be simultaneously bisected by a single (n − 1) dimensional hyperplane.
So, in the case of the three-layered cake, n = 3, and the three-layered cake can be bisected (or cut) using a single, two-dimensional “hyperplane”. Such as, say, a knife.
Who would have thought that cutting cake would lead to higher dimensions of mathematics by way of a ham sandwich?
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Toby Walsh*