How to cut a cake

Original author: Erica Klarreich
  • Transfer

Informatics specialists have developed an algorithm for a fair pie section for any number of people.




Two young scientists, specialists in the field of computer science, have figured out how to honestly divide the cake between any number of people, solving the problem that mathematicians have been fighting for decades. Their work surprised many researchers who considered such a separation impossible in principle.

The division of the cake is a metaphor for a wide range of real-world tasks, including the division of a certain continuous object, be it a cake or a piece of land, between people who evaluate its properties differently. One likes a chocolate coating, another wants creamy flowers. From biblical times, there is a known algorithm for dividing such an object between two people, such that no one envies the other: one person divides the cake into two equal parts for it, and the other chooses one of them. In the Book of Genesis, Abraham (then known as Abram) and Lot used this method to divide the land, when Abraham invented separation, and Lot chose between Jordan and Canaan.

In the 1960s, mathematicians invented an algorithm for a similar separation of the pie “without envy” for three people. But until now, the best solution of the problem for many people was more than three procedures, established in 1995 the political scientist Stephen Brahms [Steven Brams] from New York University and mathematician Alan Taylor [Alan Taylor] from Union College. She guaranteed a “fair” carving of the cake, but with one condition - the procedure was “unlimited”, that is, the number of steps necessary for the carving could be arbitrarily large.

The Brahms-Taylor algorithm was at one time called breakthrough, but “its unboundedness, in my opinion, was a big flaw,” says Ariel Procaccia[Ariel Procaccia], a computer science specialist from Carnegie Mellon University, one of the creators of Spliddit , a free online tool for a fair division of various tasks, from household duties to renting a shared apartment.

Over the past 50 years, many mathematicians and computer scientists, including Procaccia, have convinced themselves that there is no limited fair algorithm for partitioning a cake into n pieces.

“It was this task that led me to the area of ​​fair divisions,” says Walter Stromquist.[Walter Stromquist], a professor of mathematics at Bryn Mavr College in Pennsylvania, who achieved good results in cake cutting in 1980. "All my life I thought I would return to this problem in my spare time and prove that such an extension of the result is impossible in principle" .

But, in April, two computer scientists denied these expectations by publishing an algorithm for fair cake cutting with work time, depending on the number of participants in the sharing, and not on their personal preferences. One of the scientists, 27-year-old Simon Mackenzie [Simon Mackenzie], Ph.D. from Carnegie Mellon, presented his work on October 10 at the 57th annual IEEE Symposium on Computer Science.

The algorithm is extremely complex. A section of cake between n participants may require up to nn n n n n steps, with about the same number of cuts. Even for a small number of participants, this number exceeds the number of atoms in the Universe. But researchers already have ideas for simplifying and speeding up the algorithm, according to the second team member, Haris Aziz , a 35-year-old computer scientist from the University of New South Wales, who works in the Australian data research group Data61. According to Procaccia,

specialists investigating the theory of equitable division consider this to be “definitely the best result in decades”.

Pieces of cake


The algorithm of Aziz and Mackenzie is based on an elegant procedure, independently invented by mathematicians John Selfridge [John Selfridge] and John Conway in the 1960s, allowing the cake to be divided into three.



If Alice, Bob, and Charlie (A, B, C) want to split a cake, the algorithm begins with Charlie dividing the cake into three pieces that look equal to him. Alice and Bob choose pieces that they like. If they choose different pieces, voila, everyone gets what they want.

If Alice and Bob choose one piece, then Bob cuts a small part from this piece so that the piece becomes equivalent, from his point of view, to another piece of cake - the one that Bob would choose in the second place. Cut off residue is deposited. Now Alice should choose the best piece from the remaining three, and then selects Bob - with the condition that he take the piece cut by him, if Alice does not choose it. Charlie gets the third piece.

As a result, no one envies anyone. Alice chose the first. Bob received one of two equally valuable pieces for him. Charlie received one of the three original pieces that he cut himself.

Only a small cut off residue remains. But it can be divided without first starting the algorithm and not falling into an endless cycle of circumcisions and elections, because Charlie is satisfied with his piece in any case - and even if the one who got the trimmed piece would receive all the residuals in its appendage, Charlie would not have looked dishonest, because the cut piece and the residuals in total will give a piece of cake equivalent to his piece - after all, he originally cut these pieces himself. Aziz and Mackenzie describe this position of Charlie as "dominant."

Now, if, for example, Alice got a trimmed piece, then Bob cuts the trimming into three parts, equivalent from his point of view, Alice chooses one of these pieces to herself, then chooses Charlie, then Bob. Everyone is happy: Alice chose first, Charlie gets a piece better than Bob’s (and he doesn’t care how much Alice took), and from Bob’s point of view all three pieces are equal.

Brahms and Taylor used the “dominance” property (but with a different name) to develop their 1995 algorithm, but they didn’t put their ideas into effect until a limited algorithm appeared. In the next 20 years, no one has achieved the best results. “And not because of the lack of attempts,” as Procaccia says.

Non-professional cake dividers


When Aziz and Mackenzie (AiM) decided to take on this task a couple of years ago, they were new to the cake sharing task. “We didn’t have as much experience as people who worked intensively on it,” says Aziz. “Although this is usually a drawback, in our case it was an advantage, because we thought differently.”

AiM began with a study of the task of dividing into three participants from scratch, and as a result of the analysis, they came up with a limited fair algorithm for four participants published by them last year.

They could not immediately show how to expand their algorithm to more than four participants, but they enthusiastically took up this task. “After sending the work related to the four participants, we really wanted to continue the work as quickly as possible, until someone more experienced and clever would generalize it independently to the case with n participants,” Aziz says. And about a year later, their searches were crowned with success.

Like the Selfridge-Conway algorithm, the AiM protocol constantly invites different participants to cut the cake into n equal parts, and others to make cuts and choose pieces of cake. But there are other steps in the algorithm, for example, a periodic exchange of pieces of cakes in a special way, in order to increase the number of dominant relationships between participants.

This relationship allows A & M to reduce the complexity of the task. If, say, three participants dominate the others, they can already be sent to eat their own pieces of cake - they will be satisfied no matter who gets the leftovers. After that, a smaller number of participants remain, and after a limited number of such steps, everyone is satisfied and the whole cake is divided.

“Looking back at the complexity of the algorithm, it is not surprising that its development took so much time,” says Procaccia. But AiM already believe that they can simplify the algorithm so that it does not require the exchange of pieces and takes place in just n n n steps. According to Aziz, they are already working on these results.

Brahms warns that the simpler algorithm will not have any practical use, as the pieces of cake obtained by the participants will include many small crumbs from different parts of the cake. Such an approach is not particularly useful if, for example, you divide land.

But for mathematics and computer science students studying the problem, the new result "nulls the whole topic," Stromquist says.

Now that researchers know that a cake can be divided in a limited number of steps, the next step, according to Procaccia, will be to understand the large gap between the upper limit on the number of steps according to the A & M method and the lower limit on the number of steps required for this. Procaccia has already proved earlier that the algorithm of fair cake separation cannot take place in less than n2 steps - but this number of steps is tiny compared to n n n n n and even with n n n .

Aziz says researchers now have to figure out how to narrow this gap. "I think that progress can be made in both directions."

Also popular now: