There comes a point in every person’s life where they have to learn how to share fairly. Admittedly some people seem to ignore this point, sailing on through life gleefully seizing more than would be justified, but we’re willing to bet that the situation of having to divide up a resource (for example some food or a list of chores) into parts that everybody is happy with is pretty much universal.
If there are just two people who want to split the resource, then there is a simple method to ensure that it is divided fairly. This concept (called the “I cut, you choose” method) is so old that it’s even mentioned in the Bible. As the name suggests, the method involves one person splitting the resource into what they consider to be equal halves, and then the other person picking which (if any) of the pieces they think is worth more. The person who chooses is bound to be happy, and the person who cut can’t complain since they were supposed to divide the resource into equal pieces. The solution for two people, then, is so simple that it doesn’t seem like mathematics at all. However, the problem becomes significantly harder once you start to include more people — so difficult, in fact, that a completely ‘satisfactory’ answer for an arbitrary number of sharers was not found until 2016…
Envy, cake and ham sandwiches
One of the main issues that makes the sharing problem so difficult is the “deadly sin” of envy. To make our discussion more concrete, we’ll use a specific example of a resource to be divided up. The problem was first seriously considered in a mathematical way by Hugo Steinhaus, when he was living in occupied Poland during the second world war. Steinhaus chose a cake as his example resource, and suggested that we try to cut it fairly between three people; call them Alex, Belgin and Chris.
Let’s have a look and see what can go wrong. For example, suppose that Alex is tasked with dividing the cake, and that he really likes chocolate buttons. He should choose to split the cake so that each piece has an equal amount of buttons. That way he’ll be happy whichever one he ends up with. On the other hand, Alex doesn’t care about icing and it just so happens that the way that he splits the cake has 60% of the icing on one slice, 40% on another and none on the third piece. Now suppose that Belgin and Chris both really like icing. If Chris takes the piece with more icing then Belgin will be left feeling envious of him, even though her piece has more than 1/3 of what she wants (the icing)!
Alex (who cut the cake) only cares about chocolate buttons. Belgin and Chris both like icing, and both get more than 1/3 of it, but one of them is always bound to be unhappy.
In summary: both Belgin and Chris have more than 1/3 of what they want (the icing), Alex has 1/3 of what he wants (the chocolate buttons) but we are still left with an unsatisfactory answer — the division is not envy-free. As Steinhaus pointed out, the problem is that different people can ascribe different values to each piece, and things are actually harder when people agree on what is valuable (the issue was caused by both Belgin and Chris liking icing). Thus, any algorithm for dividing the cake should take into account this possible difference in valuation. Although Steinhaus wasn’t able to find such an algorithm, he did manage to prove that an envy-free division of the cake can always be found, whatever the number of players. This result is now popularly known as the ham sandwich theorem.
Keeping trim
The first algorithm for $n$-player confectionery satisfaction came about in the early 1990s. After reading about the problem in a magazine, political scientist Steven Brams had a fantastic hunch. He called upon his mathematician friend Alan Taylor to help him formalise his intuition, and together they produced a procedure that worked for any number of players. The story of their solution is quite extraordinary, and excellently re-told in this article in Discover magazine.
Key to Brams’ and Taylor’s solution is the idea of trimming, where a player can cut a larger piece down to size so that they think the overall division is fairer. Much of the cake can then be allocated without envy, and the players can get to work on the (now smaller) trimmings. The problem with their algorithm is that there was no bound on the running time. Although it is always guaranteed to finish, the number of steps needed depends on how the players evaluate the different parts of the cake and can in fact be arbitrarily large. By which time the cake might be stale, or the participants might have resorted to more primitive methods. What we want is an algorithm that stops in a number of steps depending only on the number of players.
If Belgin trims some of Chris’s piece, most of the cake can be divided in a way that makes everybody happy. The trimmings can then be dealt with in a similar manner.
When we don’t know how long it’ll take for an algorithm to finish, we say that it is unbounded. And for a while, most mathematicians thought this was the best we could get. In his 2006 book “How to cut a cake, and other mathematical conundrums”, Ian Stewart remarks that bounded schemes “probably don’t exist.”
Breaking boundaries
All of this changed in 2016, when two young computer scientists—Haris Aziz and Simon Mackenzie—published a paper online that gave a bounded, envy-free algorithm for $n$ players. The pair were newcomers to the field of cake-cutting, and first devised a new approach to the three-person problem, which had previously been solved (independently) by John Selfridge and John Conway (who also invented the Game of Life, now available in T shirt form!) around 1960.
Aziz and Mackenzie say in their paper that “At the heart of our protocol is the idea of domination’’. It would be too difficult to explain their general $n$-person algorithm here, so instead we will focus on the three-person case. In order to more fully appreciate the role domination plays in their new algorithm, we will compare it to that of Selfridge and Conway. If we call the three players A, B and C, the Selfridge-Conway protocol proceeds as follows.
1. A cuts the cake into what they perceive to be 3 equal pieces.
2. B then trims the largest piece so that it is now the same size as the second largest. The trimmings, if there are any, are put aside for now to be divided later.
3. The three remaining pieces are chosen in the order C, B, A, with the caveat that B must choose the piece she trimmed if C didn’t already take that one.
- At this stage, let X be the player who chose the piece that was trimmed by B in step 2 and Y be whichever of C or B is not X.
4. Y cuts the trimmings into three equal pieces which are chosen in the order X, A, Y.
Now everyone believes they have at least 1/3 of the cake and furthermore, no-one would want to swap with anyone else. Let’s take a minute to check that this is in fact the case. C got his first choice in step 3 and either cut or chose first in step 4. Similarly, B also got one of their (joint) first choice in step 3 and either cut or chose first in step 4 so is happy with that part too. A doesn’t want to swap with Y because they are happy with step 3 (since A cut) and they chose before Y in step 4. A certainly don’t want to swap with X because X took the trimmed piece. According to A, this would only be worth a 1/3 when combined with all the trimmings. So A is happy not to swap even if X were given all the trimmings.
Alex won’t want to swap with Belgin, because he cut the first round then chose before her in the second. But he also won’t want to swap with Chris, because no matter how Belgin cuts the trimmings, Chris can’t have more buttons than Alex (and that’s all Alex wants).
Mmm… domination…
This relationship between A and X is what is called domination. It was easy to see that A didn’t want to swap with X because we didn’t have to take into account what happened to the trimmings at all. To be precise, we say A dominates X if, having divided some of the cake in an envy-free way, A wouldn’t want to swap with X even if X were given all the remaining cake. The new Aziz-Mackenzie 3-person protocol is similar to the Selfridge-Conway one but makes more use of the domination concept.
Both Belgin and Chris mark their favourite piece so that it’s worth the same as the second best. Belgin would take everything covered by the red line, and Chris everything covered by the blue.
1. A cuts the cake into what they perceive to be 3 equal pieces.
– If C and B disagree about which is the largest piece then everyone can get their first choice, else go to step 2.
2. C and B both put trim marks on the largest piece showing where they would cut to make it equal to their second most preferred piece.
- Let X be whoever would trim the most off and Y be whichever of C or B is not X. Label the piece between the two trim marks R1.
3. This largest piece is cut at the mark made by Y and given to X. Call this P1. Y then gets first choice of the two remaining main pieces and A gets the one that’s left.
- In the example on the left, we would give the ‘blue’ piece to Belgin, which we note is more than she wanted, and Chris takes the ‘full’ piece with the icing but no orange. Neither Belgin nor Chris is envious of the other and, since she took the trimmed piece, Alex dominates Belgin. It will always be the case that A dominates X.
4. A now cuts the trimmings into three equal pieces.
– If C and B disagree about which is the largest piece of the trimmings then everyone can get their first choice trimmings and the whole cake is now divided.
5. C and B both put trim marks on the largest piece of trimmings showing where they would cut to make it equal to their second most preferred piece. Label the piece between the two trim marks R2.
- There are two cases to consider. If Y would now trim more than X go to 6a and if X would again trim more than Y, go to step 6b.
6a. Y is given the trimmed piece up to the mark made by X. X then gets first choice of the two remaining pieces and A gets the one that’s left.
Suppose Chris trims more than Belgin (step 6a). We give him the red piece, her the next-best ‘full’ piece of trimmings and again neither Chris nor Belgin can complain. Alex now dominates Chris as well as Belgin.
Suppose Belgin trims more than Chris again (6b). Give Belgin the blue piece, and Chris the second-best ‘full piece’.
- Notice that A still dominates X but now A also dominates Y. This means that X and Y can simply put the remaining cake together and do the old you-cut-I-choose to split it between themselves. Done. In the example above, Belgin took the first trimmed piece and Chris took the trimmed piece of trimmings (!) so Alex dominates both of them, and it doesn’t matter how they share out the final portion.
6b. X is given the trimmed piece up to the mark made by Y. Call this P2. Y gets first choice of the two remaining pieces and A gets the one that’s left. X is asked to choose whether they prefer R1 or R2. If they prefer R1 they swap P2 with the piece Y chose at this stage and if they prefer R2 they swap P1 with the piece Y got in stage 3.
With this division, Alex does not dominate Chris because it is possible to divide the ‘trimmings of the trimmings’ so that Chris has more buttons than Alex. Chris needs to swap a piece with Belgin.
- Notice that after this swap, A now dominates both X and Y. This is because X and Y both now have pieces that were trimmed and A cut both times. So we can again finish in the same way by splitting the remaining cake between A and B using you-cut-I-choose. In the example above we would basically be asking Belgin which piece she got the best deal on, and then get her to swap the other one with Chris. Belgin won’t mind the swap, because she always got more than she asked for, and Chris won’t mind either because he thinks that his and Belgin’s pieces are the same size.
6b is slightly more involved than 6a because we had to swap (or permute) some cake to get it so that A dominated both X and Y. Although the new algorithm is trickier than the Selfridge-Conway classic, by teasing out the key ideas of domination and permutation Aziz and Mackenzie were on their way to developing the first bounded, envy-free, solution to the $n$-person problem. The algorithm gets much more complicated—the number of cuts when there are $n$ players might be as large as $n^{n^{n^{n^{n^{n}}}}}$—when more people are involved but as Aziz and Mackenzie say themselves, “both the ideas of domination and permutation will feature prominently in our protocol for four agents.” The four-person algorithm presented in that paper makes use of three sub-algorithms. One of these aims to assign some of the cake in a way that is envy-free. One they call “Permutation Protocol for 4 Agents” and the other they call “Post Double Domination Protocol for 4 Agents”. You can read about the details in their papers:
https://arxiv.org/pdf/1508.05143.pdf
https://arxiv.org/pdf/1604.03655.pdf
More from Chalkdust
In conversation with Clifford Cocks
We chat to the crypto chief about inventing RSA... but not being able to tell anyone
Unknown pleasures: pulsars and the first data revolution
The scientific story behind the cover of Joy Division's treasured debut
In conversation with Matt Parker
Interviewing Matt was a mistake
Balancing the equation
Reviewing the Royal Institution's first Black History Month event.
Black Mathematician Month 2018
We look back at last year's Black Mathematician Month, and give a preview of what to expect this October.
Closing the Gap
A review of Vicky Neale's new book about the quest to understand prime numbers.