[No Caption]

Olena Shmahalo/Quanta Magazine

Save Save Save Save Save Save

Two young computer scientists have figured out how to fairly divide cake among any number of people, setting to rest a problem mathematicians have struggled with for decades. Their work has startled many researchers who believed that such a fair-division protocol was probably impossible.

Cake-cutting is a metaphor for a wide range of real-world problems that involve dividing some continuous object, whether it’s cake or, say, a tract of land, among people who value its features differently — one person yearning for chocolate frosting, for example, while another has his eye on the buttercream flowers. People have known at least since biblical times that there’s a way to divide such an object between two people so that neither person envies the other: one person cuts the cake into two slices that she values equally, and the other person gets to choose her favorite slice. In the book of Genesis, Abraham (then known as Abram) and Lot used this “I cut, you choose” procedure to divide land, with Abraham deciding where to divide and Lot choosing between Jordan and Canaan.

Around 1960, mathematicians devised an algorithm that can produce a similarly “envy-free” cake division for three players. But until now, the best they had come up with for more than three players was a procedure created in 1995 by political scientist Steven Brams of New York University and mathematician Alan Taylor of Union College in Schenectady, New York, which is guaranteed to produce an envy-free division, but it is “unbounded,” meaning that it might need to run for a million steps, or a billion, or any large number, depending on the players’ cake preferences.

Read the related Abstractions post:
All Is Not Fair in Cake-Cutting and Math

Brams and Taylor’s algorithm was hailed as a breakthrough at the time, but “the fact that it wasn’t bounded I think was a huge shortcoming,” said Ariel Procaccia, a computer scientist at Carnegie Mellon University and one of the creators of Spliddit, a free online tool that provides fair-division algorithms for tasks like dividing chores or rent among roommates.

Over the past 50 years, many mathematicians and computer scientists, including Procaccia, had convinced themselves that there was probably no bounded, envy-free algorithm for dividing cake among n players.

“This is the very problem that got me into the subject of fair division,” said Walter Stromquist, a mathematics professor at Bryn Mawr College in Pennsylvania who proved some of the seminal results on cake cutting in 1980. “I have thought all my life that I would come back to it when I had time and prove that this particular extension of the result was impossible.”

But in April, two computer scientists defied expectations by posting a paper online describing an envy-free cake-cutting algorithm whose running time depends only on the number of players, not on their individual preferences. One of the pair — 27-year-old Simon Mackenzie, a postdoctoral researcher at Carnegie Mellon — will present the pair’s findings on Oct. 10 at the 57th annual IEEE Symposium on Foundations of Computer Science, one of computer science’s pre-eminent conferences.

Lucy Reading-Ikkanda for Quanta Magazine

 

The algorithm is extraordinarily complex: Dividing a cake among n players can require as many as n^n^n^n^n^n steps and a roughly equivalent number of cuts. Even for just a handful of players, this number is greater than the number of atoms in the universe. But the researchers already have ideas for making the algorithm much simpler and faster, said the other half of the team, Haris Aziz, a 35-year-old computer scientist at the University of New South Wales and Data61, a data research group in Australia.

For the people who study the theory of fair division, this is “definitely the biggest result in decades,” Procaccia said.

Pieces of Cake

Aziz and Mackenzie’s new algorithm builds on an elegant procedure that mathematicians John Selfridge and John Conway independently came up with around 1960 for dividing a cake among three people.

If Alice, Bob and Charlie want to share a cake, the algorithm starts by having Charlie cut the cake into three slices that are equally valuable from his perspective. Alice and Bob are each asked to point to their favorite slices, and if they like different slices, we’re done — they each take their favorite, Charlie takes the remaining slice, and everyone goes home happy.

If Alice and Bob have the same favorite, then Bob is asked to trim a little cake off that slice so that what remains is equal in value to his second-favorite slice; the trimmed bit is set aside for later. Now Alice gets to choose her favorite piece from among the three slices, and then Bob gets to choose, with the requirement that if Alice didn’t choose the trimmed slice, he must take it. Charlie gets the third slice.

At this stage, none of the players envy each other. Alice is happy since she got to choose first; Bob is happy since he got one of his two equally preferred top choices; and Charlie is happy because he got one of his three original pieces, all of which are equal in his eyes.

But there’s still the trimmed bit to be divided. What makes it possible to divide this bit without creating still more trimmings, and getting into an infinite cycle of trimming and choosing, is the fact that Charlie is more than merely satisfied with the cake he has gotten so far; he would not feel cheated even if the player with the trimmed slice gets all the cake that’s waiting to be allocated, since the trimmed slice plus the trimming equals one of the original slices. Aziz and Mackenzie describe this relationship by saying that Charlie “dominates” the player who got the trimmed slice.

Now if, for example, Alice was the one who got the trimmed slice, the algorithm proceeds as follows: Bob cuts the trimmings into three pieces that he values equally, and then first Alice gets to choose a piece, then Charlie, then Bob. Everyone is happy: Alice because she got to choose first, Charlie because he gets a slice he likes better than Bob’s (and he didn’t care how much Alice took), and Bob because the three slices are equal in his view.

Brams and Taylor used the notion of domination (without calling it that) in designing their 1995 algorithm, but they couldn’t push the idea far enough to get a bounded algorithm. For the next 20 years, neither could anyone else. “I don’t think it’s for lack of trying,” Procaccia said.

Rookie Cake-Cutters

When Aziz and Mackenzie decided to tackle the problem a couple of years ago, they were comparative newcomers to the cake-cutting problem. “We did not have as much background as people who have been intensely working on it would have,” Aziz said. “Although that is mostly a disadvantage, in this case it was somewhat of an advantage, because we were not thinking in the same way.”

Aziz and Mackenzie wet their feet by studying the three-player problem from scratch, and their analysis eventually led them to find a bounded envy-free algorithm for the four-player case, which they posted online last year.

They couldn’t immediately see how to extend their algorithm to more than four players, but they dived feverishly into the problem. “After we submitted our paper for the four-agent case, we were really keen that we should try it before someone much more experienced, much more clever would generalize it to the n-agent case,” Aziz said. After about a year, their efforts succeeded.

As with the Selfridge-Conway algorithm, Aziz and Mackenzie’s complicated protocol repeatedly asks individual players to cut cake into n equal pieces, then asks other players to make trims and choose pieces of cake. But the algorithm also carries out other steps, such as periodically exchanging portions of players’ cake stashes in a carefully controlled way, with an eye toward increasing the number of domination relationships between players.

These domination relationships allow Aziz and Mackenzie to reduce the complexity of the problem: If, for example, three players dominate all the others, those three can be sent away with their slices of cake — they’ll be happy no matter who gets the remaining trimmings. Now there are fewer players to worry about, and after a bounded number of such steps, everyone has been satisfied and all the cake given out.

“Seeing, in retrospect, how complicated the algorithm is, it’s not surprising that it took a long time before somebody found one,” Procaccia said. But Aziz and Mackenzie already think that they can simplify their algorithm considerably, to one that doesn’t need the cake exchanges and takes fewer than n^n^n steps. They are currently writing up these new results, Aziz said.

Even a simpler such algorithm would be unlikely to have practical implications, Brams cautioned, since the cake portions that players receive would typically include many tiny crumbs from different parts of the cake — not a feasible approach if you’re dividing something like a tract of land.

But for mathematicians and computer scientists who study cake cutting, the new result “resets the subject,” Stromquist said.

Now that researchers know it’s possible to fairly divide cake in a bounded number of steps, the next goal, Procaccia said, is to understand the huge gulf between Aziz and Mackenzie’s upper bound and the existing lower bound on the number of cuts needed to divide a cake. Procaccia had previously proved that an envy-free cake-cutting algorithm will require at least about n2 steps — but that bound is minuscule compared to n^n^n^n^n^n or even n^n^n.

Researchers now have to figure out how to close this gap, Aziz said. “I think there can be progress in both directions.”

This article was reprinted on ScientificAmerican.com.

Save

Save

Save

Save

Save

View Reader Comments (28)

Leave a Comment

Reader CommentsLeave a Comment

  • My father was a British POW in first Stalag Luft 3 and then Colditz. When there was something like a cake or piece of fruit from the Red Cross, it would be shared between roommates. The rule was, he who cuts gets the last choice. He told me that one could spend hours working out where to cut, and the result would be a remarkably accurate division – hunger can be almost as effective as an algorithm.

  • Growing up in a family of six we worked out a practical solution to this problem long ago. Whoever cuts, picks last. The even number helped.

  • In our house, the three would get the slices they liked and the dog would get the trimmings. Job done.

  • I'm not quite sure why Bob has to cut the trim in 3 parts (step 6 of the example). May I propose a simplified approach:

    Step 2: Charlie cuts the cake into 3 slices equally valuable to him.

    Step 3: Alice and Bob identify their first chioce. At this point, Charlie picks any one of the unchosen slices and immediately Leaves the game envy-free, because all slices were equally valuable to him.

    Step 4: Bob trims his preferred slice to match his second most preferred slice.

    Step 5: skip.

    Step 6: Bob cuts the trim in TWO parts that are equal to him.

    Step 7: Alice chooses her part of the trim. Everybody is happy.

  • Flavio Fusco: What you are describing, if I understand it correctly, would not be envy-free. (By the way, you forgot to spell out one of the steps of your protocol — you never said what happens to Bob's favorite and second-favorite slices after he trims his favorite to match his second-favorite. I presume you meant to say that at that point, Alice chooses one of those two slices and Bob gets the other; then they turn their attention to the trimming.)

    The problem is that while Charlie is happy when he leaves the game, he will be envious after the trim is distributed. After all, either Alice or Bob has gotten one of Charlie's original slices *plus* a piece of trimming. Charlie will wish he had that portion, instead of the slice he got.

    That's why Charlie needs to stick around for the whole procedure and get a share of the trimmings.

  • Erica, I see your point. What I find a bit tricky to accept is that at the end Charlie may go away with *more* than his fair share of the cake (just imagine a starting situation with an homogeneous cake cut into 1/3, 1/3, 1/3: in the pictured example Charlie will take 1/3 + a bit, which is unfair, retrospectively).

    He is allowed to do that because the algorithm incorporates the idea that Charlie's happiness can change by looking at the fortunes of Alice and Bob *after* slicing the trim part, as you said.

    But the algorithm does not work the same way for Alice and Bob, because for sure at the end *they* willbe envious of Charlie, realizing that he takes home more than 1/3.

    Do I miss something…?

  • Quote from a Cake-Cutting AI: "I tried to fairly divide a cake among five people, but before I finished, the cake went rancid, all five people died of old age, and then the sun turned into a red giant and enveloped the Earth in sea of hot plasma."

  • Flavio — I think the reason you find this division "unfair" is because you have a different notion of fairness than envy-freeness in your mind — "equitability," in which the players all end up with pieces they value equally (*not* the same as envy-freeness, in which they prefer their piece to what the others got). You might enjoy reading my blog post on these different notions of fairness:
    https://www.quantamagazine.org/20161007-mathematics-fair-division/

    But I don't agree with you that Alice and Bob will end up envious of Charlie — in fact, the whole goal of the algorithm is to prevent that. It's true that Charlie ends up with a piece that *to him* is worth more than one-third of the cake. But the key idea here is that Alice and Bob value the various features of the cake differently than Charlie does (if they all valued the cake exactly equally then they could simply each take one of Charlie's original three slices, and there would be no need to deal with trimmings). Since they have different values from Charlie, Alice and Bob will be happier with the pieces they end up with than if they could trade with Charlie, even though Charlie thinks he got more than his fair share.

    This might seem counterintuitive, but if you think about it, as long as people's preferences are sufficiently different from each other, it's possible for them *all* to feel as if they got more than their fair share, and not envy each other.

  • Flavio, I think what you are missing is that A and B both passed up the chance to take Charlie's main piece in Step 5. And Alice passed up the chance to take Charlie's piece of trim in Step 7, and Step 6 establishes that Bob values all 3 trim pieces equally. So it's guaranteed that A and B both value Charlie's pairing of main piece + trim no more than their own, because they could have taken his main piece rather than their own, and they can't value his trim more than their own.

  • Looking at the illustration you provide (title picture), the main problem seems to me not that much the size of the slices, but rather the choice where to place the cuts, depending on the fruits non-equally distributed on the cake's surface.

  • Erica Klarreich makes a good point that Flavio is considering equitability. Envy-Freenesss simply requires that no one prefers another person's share even if the other person herself is extremely happy with her piece.

  • This works if everyone is reasonable and logical. Add in one irrational person and the whole thing blows up. Maybe you should just give Bob the whole cake and avoid WWIII.

  • Bernard, envy-free protocols are guaranteed to be envy-free for anyone who reports her valuation honestly irrespective how strange her valuations are. She is not envious even if all the other people act irrationally and dishonestly.

  • Thank you Erica for pointing out the difference between envy-freeness and equitability: this is something I didn't consider in my previous replies. Very interesting distinction indeed.

  • From Lemma 4.5 on page 24 of the newest version 10 of the paper on the ArXiv:

    "Since j_2 did not have a trim to the right of j_1 previously"

    Here the authors are wrongly assuming that if an agent was allocated a piece then he must have the right-most trim on that piece. This actually invalidates the entire result.

  • Re. Archer's wrong comment, if a piece has trims on it, only the player with the rightmost piece gets the piece in the sub core protocol. This is by specification of the sub core protocol.

  • John Groom – The participants can have hidden preferences, but they do need to follow some rules and be rational. Here's a (non-exhaustive) list of preferences that might make the process not envy-free:

    * To prefer different portions on Tuesdays.
    * To prefer whatever portion Bob chooses.
    * To prefer whichever portion is chosen last.
    * To prefer less cake.
    * To prefer allocations of cake that are a rational fraction of the total cake.

  • At what point do you cut your losses and submit to the law of diminishing returns? Stop overthinking things… K.I.S.S.

  • Step 1. Charlie cuts the cake into 3 slices
    Step 2. If Alice and Bob choose the same slice, ask Bob to trim off one small portion from that slice and add it to any of other 2 that he values as fair.
    Step 3. Ask Alice to pick. If she didn't pick the trimmed one, Bob has to take it.
    Step 4. Bob is the second to pick.
    Step 5. Charlie is the last to pick.
    Alice gets her first choice.
    If Alice chooses the trimmed one, Bob can choose the slice with the trimmed off portion that he values fair. If Alice didn't choose the trimmed one, he has to take it which is also fair to him.
    Charlie can get his original slice or even better.
    And best of all, there is only one trim.

  • The process of trim division describe alongside this article does not appear to guarantee an envy-free result to me. As I see it, trim distribution presents a similar problem that the original piece distribution presented.

    Considering the following scenario:

    1. Charlie cuts the cake into P1, P2 and P3.
    2. Alice and Bob identify the same desired piece, P3.
    3. Bob trims his preferred piece, P3, to match his second most preferred piece, P2.
    4. Alice now chooses the non-trimmed piece, P2.
    5. Bob must take P3.
    6. Charlie is left with P1.
    7. Bob cuts the trim into T1, T2 and T3.
    8. Alice is given first choice and she takes T1.
    9. Charlie wanted T1, but he is now left only able to choose from T2 and T3.

    From Charlie's perspective, his acquisition of P1 is equal to Alice's acquisition of P2 because he cut these pieces himself. (In fact, he would see himself as better off than Bob, because Bob's piece is already less than an equal share in his mind.) However, if in addition to the equal portions that Charlie and Alice already share, Alice receives a better piece of the trim, Charlie will be envious of her for that. The fact that Charlie got to choose before Bob does not remedy that problem.

  • @Paul G: If Bob trims his preferred piece and ends up with the trimmed piece, then Alice would cut the trim into three parts, and Bob, Charlie and Alice would choose their trim parts in that order. If Bob trims his preferred piece but Alice chooses the trimmed piece, then Bob would divide the trim into three parts, and Alice, Charlie and Bob would choose in that order. Problem solved!

  • This algorithm does not work when smaller piece is preferred over larger ones. Trimming a piece would make it more desirable, so it is impossible to trim first choice to match second choice.

    For example, a mother made a horrible cake/pie/whatever and order her children to finish it.

    gg

  • Here's a way cut into three equal parts- ( If this is correct, I can generalize to N with O(N**2) number of slices/cuts ) –
    Alice cuts cake into three equal parts C1, C2, C3
    IF Bob and Charlie both think C3 is the largest, then we do this:
    Bob takes two small trimmings T13 and T23 from C3 such that (C1+T13) = (C2+T23) = (C3 – T13 -T23)
    Then Charlie picks his choice from one of (C1+T13), (C2+T23), (C3 -T13 -T23)
    Then atleast one of (C1+T13) and (C2+T23) will remain, and Alice will pick one of them because she thinks its better than her share!
    Then Bob takes the rest.
    ELSE, Bob and Charlie take what they think is largest, and leave the one remaining for Alice.

  • Why don't we use this method for determination of electoral precincts? Unlike gerrymandering — this has the capability of angering all parties (or pleasing them) so as to be eminently fair.

Comments are closed.