Ariel Procaccia has thought a lot about how to cut cake over the past 15 years. That’s partly because he has three children. As a group, they’ve celebrated more than two dozen birthdays. So Procaccia knows what it’s like to stand with a knife before a tempting dessert. Sweet layers of cake. Buttercream frosting and chocolate curls. And a crowd of small, eager partygoers who will instantly spot if someone else gets a better slice.
But Procaccia is also a computer scientist at Harvard University in Cambridge, Mass. There, he studies the mathematical rules for dividing stuff up. And dessert is a handy way to think about that. It comes down to a deceptively simple question about fairness: How can you cut a cake to make sure everyone at the party is happy with what they get?
The answers reach far beyond birthday parties. For more than 75 years, mathematicians have puzzled over how to fairly divide resources. Such questions have real-world uses. How can food be divvied up between hungry communities, for example? How should roommates split up rent or chores? How can communities draw boundaries for fair voting districts.
These questions include more than math, too. They must consider what people prefer and other issues. So they become interesting to scientists, economists and legal experts.
But cake works as a stand-in for anything that can be divided, says Steven Brams. He’s a game theorist and political scientist at New York University (NYU) in New York City. Cake-cutting ideas can easily be applied to splitting up land, time or other limited resources.
Recipes for fair cake-cutting
Experts have come up with many rules, called algorithms, for how to cut a cake fairly. (Nearly all focus on rectangular cakes. The related but more recent “pie-cutting” problem addresses circular desserts or pizza.) The simplest rules show how two people can fairly share a cake: One person cuts the cake into two pieces that they believe to be equal in value. The other person chooses between them. Each eater receives a piece that they feel is at least as valuable as the other’s, if not better.
Reports of this strategy date back to ancient Greece.
In the 1940s, mathematicians started using cake-cutting as a way to study fairness. The “I cut, you choose” method works for two people. What about sharing among three or more? That has led to new challenges, such as: What is fairness, exactly — and how do you prove it?
Here’s one way to think about fairness. Maybe each person is satisfied if they feel like their slice represents a fair share of the total. For two people, a fair share would be 1/2; for three, it would be 1/3, and so on. (And for some arbitrary n number of cake eaters, a fair share would be 1/n.) If the cake is the same throughout, all the slices just need to be the same size. That’s not too hard to manage with a knife and a ruler or kitchen scale.
But what about when the cake is not all the same? Maybe it’s topped with a few icing roses or artfully placed cookies. The corner pieces may have more frosting. A maraschino cherry–lover might be happy with the smallest slice if they get the cake’s only cherry. To them, that piece is more valuable than a larger slice.
For two people, I-cut-you-choose still works with a non-uniform cake. The divider cuts the cake into two pieces they view as equal; the chooser then picks their preferred piece. But add more cake eaters, each with their own preferences, and easy solutions crumble.
More eaters, more cuts
Hugo Steinhaus was one of the first mathematicians to dive into this complexity. He worked at the University of Warsaw in Poland in the 1940s. During World War II, he saw questions about fair division of land playing out on a large and violent scale. Steinhaus came up with a modified I-cut-you-choose strategy for three players.
It came to be called the lone-divider method.
Here, someone cuts the cake. Let’s call her Alice. She cuts three pieces that she values equally (each at 1/3 of the total). Then a second person, Bob, says which of the pieces he would accept. If he approves at least two pieces, then the third person, Carla, can take any piece she wants. At least one of the remaining pieces is acceptable to Bob. So he picks next. Alice gets what’s left.
If Bob and Carla both turn down the same piece, that piece goes to Alice. She valued all pieces equally, so it still seems fair to her. The remaining two pieces are recombined and shared between Bob and Carla using I-cut-you-choose.
Steinhaus described this method in a short paper published in 1948. It was one of the first serious studies in the field of cake-cutting. And it worked for three eaters.
Do you have a science question? We can help!
Submit your question here, and we might answer it an upcoming issue of Science News Explores
In the same paper, though, he discussed an algorithm developed by two of his colleagues. This “last-diminisher” method could work for any number of cake eaters.
Here, someone cuts off a piece of cake they think is a fair share and passes it to the next person. Each other person at the party has a choice. They can pass the piece along, if they agree it’s fair or less than a fair share. Or, if they think it’s too big, they can trim it. Once everyone has had a chance to trim, or “diminish” the slice, the last person who trimmed gets the piece and exits the game.
Any bits trimmed off are added back to the remaining cake, and the process begins again with the remaining players. When only two players are left, they use I-cut-you-choose.
The last-diminisher method guarantees that everyone judges their own piece to be at least a fair share. But it’s not perfect. That’s because it doesn’t account for envy. In both the lone-divider and last-diminisher approaches, a person who gets an early slice may see a later one they wish they had instead — even though they had at first thought their piece was fair.
Last-diminisher has another flaw, too. If lots of people trim, the cake may be reduced to crumbs in later rounds. And that might feel unfair no matter how big your pile is.
Can cake cutting be free of envy?
After the lone diminisher, mathematicians continued to search for envy-free ways to divide something. In the 1960s, John Conway and John Selfridge each came up with the same idea for how three people can each feel they got a fair share, with no envy by others.
In their plan, Alice first splits the cake into three pieces. She believes each are of equal value. Then, Bob can trim one piece — at most — to create a two-way tie for the most valuable. (Any trimmings are set aside.) Carla is left to choose among the three. Then the order reverses. If Carla didn’t choose the trimmed piece, Bob takes it. Alice gets the one that remains. Then the eaters turn to the trimmings. They follow a similar process of cutting, trimming and choosing.
In 1995, another team showed how to extend this approach to any number of people. Brams at NYU worked with Alan D. Taylor of Union College in Schenectady, N.Y. Their method applied the “trimming” idea using all possible pairs of cake diners. “That was considered a breakthrough of sorts,” Brams says.
The approach still had its limits, however. There was no guarantee of how many cuts it might take. “We showed in general that you could require three cuts or 3 million cuts,” Brams says. Or even more.
The cake-cutting problem endures
The algorithms discussed so far assume that all eaters play fair. That is, all try to achieve pieces that will feel like a fair share to everyone else. But people aren’t always honest.
This is something Biaoshuai Tao recognizes. Tao is a computer scientist at Shanghai Jiao Tong University in China. And he studied what happens when you try to account for dishonest cake eaters. “If everyone knows how the cake is allocated, then I should get more if I tell the truth,” he says.
But in some cases, dishonesty can give an advantage. Say Alice and Bob are going to split a cake. If Alice knew that Bob always preferred chocolate, she might cut the cake unequally on purpose so the smaller piece contained more chocolate. Then, if Bob chose according to his preference, Alice would get the larger slice.
In a 2010 paper, Procaccia asked a curious question: Can there be a way to cut cake that guarantees honesty and fairness? More than 10 years later, the answer seems to be: no.
Tao used math to show it is impossible to cut cake in a way that promises truthfulness and fairness, with no envy. He presented this at a July 2022 meeting in Boulder, Colo. It was held by the Association for Computing Machinery Conference on Economics and Computation.
Beyond cake
Cake-cutting is easy to relate to, says Bettina Klaus. And it has lots of practical uses. At the University of Lausanne in Switzerland, Klaus studies fairness in real-world situations. Dividing things fairly “is mathematically interesting and challenging,” she says. And its complexity grows with the number of people who want to share.
One example she studies is school choice. Here, a school district has limited seats in certain schools. “In the past, schools were just assigned [to students] … without asking people what they want,” Klaus says. More recently, she notes, schools have tried to place students where they want to go (or where their parents want them to go). They also have to follow rules set by the school board. Deciding how to fairly assign those seats means balancing the priorities of these groups.
Other real-world applications show up almost everywhere you look.
Brams has used ideas from cake cutting to study fair voting procedures. (To elect their leaders, at least four scientific societies adopted an algorithm he developed. The Mathematical Association of America is one.)
In 2014, Procaccia was part of a team that designed a web-based tool called Spliddit. Based on users’ preferences, it produced mathematically fair ways to divide anything. It might be rent among roommates or even possessions among divorcees.
Even after decades of study, cake cutting defies a simple solution. Indeed, the more researchers explore it, the more there seems to be to explore.
“I’m interested in it now not only because it’s beautiful in math,” Tao says, but also because “I still believe there’s a lot to be done.”