How To Cut Cake, According To Math

(Inside Science) -- In a new study, a pair of computer scientists has resolved a problem that has plagued mathematicians for decades: how to cut a cake so that everyone feels happy with the portion they receive.

"You do not want to feel as if somebody else got a better allocation than you," said co-author Haris Aziz, a computer scientist at the University of New South Wales and with the data research group Data61 in Australia.

In theory, the work of Aziz and co-author Simon Mackenzie could be used to mete out contested items like family art collections or even fishing rights in international waters.

Aziz studies an area of economics known as fair division, which includes researching how to divide resources so that participants are not envious of one another.

While equal portions are perhaps the obvious solution, they aren't always the answer. Different people might value some portions more or less than others. Imagine, for example, a sheet cake laden with chocolate chips and strawberries on the center but with only a sparse sprinkling of pecans on the corners.

To divide such a cake between two people in an envy-free manner, one person could cut the cake into two pieces he or she finds equally desirable and then let the other person pick a favorite. The more people participating, the more chances for envy to sneak in.

In the 1960s, researchers found that for three people, one person could cut a cake into three pieces and let two others trim their favorites so they wouldn't be jealous if they didn't get them. In 1995 political scientist Steven Brams and mathematician Alan Taylor created an algorithm for any number of participants, but it doesn't limit the number of steps, Aziz said.

Knowing roughly when algorithm will eventually stop is important because you'd never know if following its instructions would take an hour, a month, or until the end of time.

"It gives a guarantee to users," Aziz said. "Whatever you do, it's not going to take too long."

Researchers weren't sure if there was a way to promise a stopping point for more than three individuals. Then, in August 2015, Aziz and his team uploaded a paper online at arXiv.org for dividing cake in an envy-free manner among four participants.

In the new study, they decided to try changing their formula to work for any number of participants.

Their algorithm bakes down to one idea. If you value your own portion enough, then you won't care about anybody else's.

Here's how it works. First, someone cuts pieces of cake he or she finds equally desirable and presents them to the others, who identify favorite chunks and bargain until they feel almost indifferent about the division. The participants may not receive whole pieces, but they get trimmed yet highly desirable chunks.

At this point, no one is envious of anyone else's portions, but there might be leftover cake. The algorithm says to bunch leftovers together and repeat the process on a loop. You stop either when there's no more cake or a set amount of time has elapsed, which depends on the number of participants.

If the clock runs out and there are leftover crumbs, then participants start swapping portions -- and crumbs -- until there are no crumbs remaining.

The research was uploaded online in April and updated in July on arXiv.org.

"It still requires many, many, many, many operations," said Carnegie Mellon University computer scientist Ariel Procaccia, who has studied the problem but was not involved in this paper, "but it's a super exciting result" because "we can bound how much effort we need in order to get envy-freeness."

For now, Aziz said, the algorithm is only a long list of written steps. The team hasn't tried writing computer code to test it because the goal was only to show such an algorithm existed.

The algorithm has some limitations, he said. For example, divvying up a cake among 10 people could take more steps than there are atoms in the universe.

The team realized in July that if participants are willing to ignore the crumbs and stop early, then it could still beat algorithms available today.  

Here's hoping researchers will soon figure out how people can have their cake and eat it too.

Andrew Silver is a contributing writer for Inside Science. He has created interactive visualizations for Quanta Magazine and written for outlets such as Science, Physics World and Live Science. Follow him on Twitter @asilver360.

Editors' note: This story has been revised to credit additional researchers for their work and to clarify details about the Brams and Taylor algorithm.