Here is why mathematicians are so taken with cake reducing

Ariel Procaccia has thought so much about learn how to reduce cake over the past 15 years. That’s partly as a result of the Harvard pc scientist has three youngsters who amongst them have celebrated greater than two dozen birthdays. He is aware of what it’s like to face with a knife earlier than a layered masterpiece, frosted with buttercream and chocolate curls, whereas pressed on all sides by small partygoers who instinctively acknowledge when another person will get a greater slice.

But it surely’s additionally as a result of a lot of Procaccia’s work focuses on exploring the mathematical guidelines for dividing stuff up. A technique to try this is to assume abstractly about dessert. For greater than 75 years, he and different researchers attempting to formalize equity have been asking the deceptively easy query: What strategies for reducing a cake assure that everybody who reveals as much as the celebration is proud of what they get?

The solutions attain far past birthday events. Cake-cutting contemplation is a part of a sprawling mathematical subfield centered on the truthful division of assets. It has spurred a raft of algorithms informing learn how to allocate meals amongst hungry communities, learn how to break up lease or chores amongst roommates, how to attract boundaries for truthful voting districts and extra. A mathematical drawback at its coronary heart, cake reducing connects rigorous reasoning to questions of human preferences and real-world points, and so attracts not solely mathematicians, but in addition pc scientists, economists, social scientists and authorized specialists. Questions of equity (and unfairness) are decidedly common. In fact, so is dessert. “It’s this very elegant mannequin in which you’ll be able to actually distill what equity is, and purpose about it,” Procaccia says.

The cake, says Steven Brams, a sport theorist and political scientist at New York College, is a metaphor for any divisible good, like land or time or restricted assets. When cake-cutting insights are utilized to settling worldwide disputes, he says, “we’re doubtlessly serving to the world discover options.”

Specialists have give you cake-cutting algorithms — the mathematical guidelines for describing learn how to reduce a cake pretty — many occasions and in lots of guises. (The approaches nearly all the time concentrate on rectangular muffins. The associated however more moderen “pie-cutting” drawback addresses round desserts or pizza.) The best guidelines reveal learn how to pretty share a cake between two individuals: One particular person cuts the cake into two items that they consider to be equal in worth, and the opposite particular person picks first. Every eater receives a bit that they really feel is not less than as precious as the opposite’s, if not higher. Stories of this truthful division technique date again to historic Greece.

Within the Nineteen Forties, mathematicians started taking critical curiosity in a mathematical strategy to equity, utilizing cake reducing as an entry level. They began exploring learn how to pretty share amongst three individuals, since I-cut-you-choose is a two-player sport. That led to in search of methods to increase these algorithms to arbitrarily massive numbers of individuals, and to asking extra nuanced questions, like what’s equity precisely, and the way do you show it?

Cake reducing is straightforward to formulate and straightforward to narrate to, says sport theorist Bettina Klaus of the College of Lausanne in Switzerland, who research equity in real-world conditions like college alternative allocation and equal entry to housing. “However on the identical time, the issue is mathematically fascinating and difficult due to its complexity as soon as the variety of brokers to share the cake grows.”

Current years have introduced progress in figuring out the fewest variety of cuts wanted for a given variety of individuals, in addition to the utmost variety of cuts, which may get ridiculously excessive however not less than reveals that cake reducing is finite. And new variations on the query preserve rising. What for those who divide a cake for a number of teams of individuals as an alternative of people? Or, as explored in a paper printed final 12 months, what if cake eaters lie about their preferences? And what for those who’re divvying up one thing that is available in discrete, indivisible items, like unopened Halloween candies, as an alternative? By specializing in exact definitions and new eventualities, mathematicians have discovered new purposes and stored cake reducing on the forefront of investigations into equity.

“You may argue that equity, or the shortage thereof, is among the most essential issues on the planet right this moment,” says Brams, who over 4 a long time has printed tons of of works on cake reducing or equity extra typically. “And we’re trying on the theoretical foundations of equity.”

Recipes for truthful cake reducing

Documented experiments to find truthful methods to separate stuff up go means again, not less than to Hesiod’s poem Theogony, written some 2,700 years in the past. In a single story within the poem, gods and mortals clashed in Mecone, a legendary Greek metropolis. As a sacrifice to appease the gods, Prometheus, who was each a god and humankind’s best benefactor, divided a lately slaughtered ox into two piles, one containing unappealing naked bones lined with a layer of fats and the opposite containing the fascinating meat hid beneath an unappealing part of abdomen. Prometheus invited Zeus to take his choose. Zeus, seduced by the shiny fats, selected the unappetizing bones.

On this historic story, Prometheus infuses the basic I-cut-you-choose technique — the best model of cake reducing — with deception. However when I-cut-you-choose is executed in pursuit of equity, it ought to assure the satisfaction of everybody concerned.

The result is proportional, that means that every participant looks like their slice represents a justifiable share of the whole. So for 2 gamers, a participant would worth their very own slice at 1/2; for 3, a justifiable share can be 1/3. (And for some arbitrary n variety of cake eaters, a justifiable share can be 1/n.) If the cake is similar all through, proportionality is equal to all of the slices being the identical dimension.

However cake reducing isn’t an fascinating mathematical drawback if the cake is all the identical. Atypical division and a kitchen scale may readily separate a slab of uniform chocolate sponge into any variety of proportional items. The issue turns into extra difficult for those who assume that the cake is heterogeneous — if it’s erratically frosted, for instance, or consists of sections of various flavors and toppings.

A maraschino cherry–lover may select the smallest slice and really feel glad in the event that they get the cake’s solely cherry. On this case, what mathematicians name the “serendipity of disagreement” offers rise to wealthy math. Probably the most fascinating math arises when there are differing opinions.

A two-person I-cut-you-choose state of affairs nonetheless works right here. The divider divides the cake into two items of equal worth of their view and will likely be proud of both; the chooser chooses their most popular piece. However improve the variety of cake eaters, every with specific preferences, and there’s no simple answer.

Hugo Steinhaus of the College of Warsaw was one of many first mathematicians to dive into this complexity. Throughout World Conflict II, as questions of truthful division of land have been enjoying out on a big and violent scale, Steinhaus developed a modified I-cut-you-choose technique for 3 gamers. It got here to be referred to as the lone-divider methodology.

On this strategy, one particular person, let’s name her Alice, cuts the cake into three items that she values equally (every at 1/3 of the whole). Then a second particular person, Bob, signifies which of the items can be acceptable to him. If he approves not less than two items, then the third particular person, Carla, can take any piece she desires, adopted by Bob (who has not less than one acceptable piece obtainable). Alice will get the one which’s left.

But when both Bob or Carla disapprove of the identical piece, then that piece goes to Alice (who valued all items equally). The remaining two items (which Bob and Carla should worth at 2/3 or extra of the whole) are recombined and shared between Bob and Carla utilizing I-cut-you-choose.

Steinhaus described this algorithm in a brief paper printed in 1948 in Econometrica. It represented one of many first rigorous investigations within the subject of cake reducing. “The rule for the primary companion,” Steinhaus wrote, “permits him to chop the article — it could be a cake — as he pleases.”

Steinhaus’ methodology labored for less than three eaters, however in the identical paper, he reported that two colleagues had developed an algorithm that would obtain proportionality for any variety of cake eaters. The strategy is named the last-diminisher methodology, and it goes like this: One particular person cuts off a bit of cake they deem to signify a justifiable share and passes that piece alongside to the following particular person. Every remaining participant has an opportunity to both trim the cake (in the event that they assume it represents greater than a proportional share) or cross (in the event that they assume it’s proportionally truthful or lower than truthful). As soon as everybody has had an opportunity to trim, or “diminish” the slice, the final one that trimmed will get the piece and exits the sport.

The trim is then recombined with the remaining cake, and the method begins once more with the remaining gamers. When solely two gamers are left, they use I-cut-you-choose.

Brams has referred to as the last-diminisher methodology a sublime answer, and it ensures that everybody judges their very own piece to be not less than as precious as a justifiable share. But it surely’s not good as a result of it doesn’t take envy under consideration. In each the lone-divider and last-diminisher approaches, an individual who exits the sport early might find yourself coveting a bit that’s reduce later within the sport — despite the fact that they thought their piece was proportional. These algorithms aren’t what mathematicians name “envy-free,” which is one other means to consider equity.

There may be one other sensible limitation to the last-diminisher methodology: With sufficient gamers, the cake that continues to be in later rounds may find yourself damaged aside by quite a lot of slicing — and even lowered to crumbs. It’s simple to see how a partygoer may not worth that as extremely as a complete piece.

Can cake reducing be freed from envy?

For the reason that debut of the last-diminisher methodology, cake reducing has fueled a small however mighty physique of significant arithmetic.

The Sixties introduced a serious step ahead when mathematicians John Conway and John Selfridge, independently of one another, got here up with a brand new reducing algorithm for 3 individuals. In contrast to the work by Steinhaus and colleagues, the brand new recipe achieved each perceived proportionality and prevented any envy among the many recipients.

An envy-free answer, during which nobody covets one other particular person’s piece, is straightforward to attain, factors out pc scientist Haris Aziz of the College of New South Wales in Sydney. Simply throw your complete cake away. “Should you don’t give something to anyone, that’s envy-free,” he says.

But when the cake lands within the garbage bin, nobody is blissful. In Conway’s and Selfridge’s extra pleasing scheme, Alice first divides the cake into three items she believes are of equal worth. Then, Bob can trim one piece — at most — to create a two-way tie for probably the most precious. (The trimmings are put aside.) Carla is left to decide on among the many three. Then the order reverses, and if Carla didn’t select the trimmed piece, Bob takes it. Alice will get the one that continues to be. The eaters then flip to the trimmings, following the same iterative protocol of reducing, trimming and selecting.

But for many years extra, an envy-free cake-cutting answer for any arbitrary variety of eaters remained elusive. Within the late Nineteen Eighties, on his PBS tv present For All Sensible Functions: Introduction to Modern Arithmetic, mathematician Sol Garfunkel featured the unsolved cake-cutting drawback and associated questions of truthful division.

However the issue wouldn’t go unsolved for for much longer. In 1995, Brams at NYU and Alan D. Taylor of Union Faculty in Schenectady, N.Y., devised a brand new process that cuts cake for 4 individuals with nobody envying anybody else. “That was thought of a breakthrough of kinds,” Brams says. It constructed on the “trimming” strategy of Conway and Selfridge, operating the same process on all potential pairs of cake eaters. Brams and Taylor described how the process might be prolonged to any variety of individuals.

The strategy nonetheless had limitations. There was no assure of what number of cuts it would take. “We confirmed generally that you can require three cuts or 3 million cuts,” Brams says. Or many, many extra.

Just a few years later, mathematicians Jack Robertson and William Webb of Washington State College in Pullman described a helpful computation mannequin that might be used to research what number of steps, together with cuts and evaluations, are required by an algorithm. Its calculations confirmed, for instance, that no most variety of cuts might be predicted for any algorithm identified at the moment that divided cake proportionally and with out envy for any arbitrary variety of gamers.

Over the following few a long time, many mathematicians got here to wonder if an higher sure for envy-free cake reducing even existed. If not, in principle, cake reducing may go on ceaselessly. What’s extra, Procaccia says, nobody had found out the minimal, both.

Is cake reducing infinite?

Procaccia by no means really got down to research cake reducing. In 2008, he was educating a course on the mathematical foundations of synthetic intelligence. Someday, strolling residence after delivering a lecture on useful resource allocation and the Robertson-Webb mannequin, he realized how he may discover a decrease sure — a minimal variety of steps, together with cuts — for envy-free cake reducing for any variety of individuals. The decrease sure he discovered was someplace round n² steps, the place n is the variety of cake eaters.

That will result in his first paper on cake. Procaccia has a knack for giving mathematical papers catchy titles. The lower-bound paper, printed in 2009, was titled “Thou shalt covet thy neighbor’s cake.” In 2010, he coauthored one referred to as “Reality, justice, and cake reducing,” which launched the query of truthfulness — along with guaranteeing proportionality and eradicating envy. If an individual hides their preferences in the course of the reducing, somebody might find yourself with an unequal share. It’s “mathematically fascinating,” Procaccia says.

As Procaccia continued within the subject, he started considering extra about helpful algorithms that would put insights from cake reducing — and the speculation of truthful division generally — to good use. One instance: dividing lease.

The best means, after all, is to divide the whole due by the variety of inhabitants. However that ignores the “serendipity of disagreement.” One particular person may need a window, one other may choose the larger closet. In 2014, Procaccia and colleagues designed a web-based software referred to as Spliddit that collected customers’ preferences and produced mathematically truthful methods to divide something, from lease amongst roommates to possessions amongst divorcees.

The largest current breakthrough in cake reducing, Procaccia says, got here from Aziz and pc scientist Simon Mackenzie, based mostly in Sydney, who decided an higher sure on envy-free, proportional cake reducing. First, in 2015, the pair tackled the issue of learn how to share cake amongst 4 individuals. By borrowing concepts from Conway and Selfridge and from Brams and Taylor, the workforce devised an algorithm that produced an higher sure of 203 steps, which may embrace nearly as many cuts. That’s so much however not too unreasonable.

A 12 months later, the workforce prolonged the strategy to an arbitrary variety of individuals, reporting an algorithm with a finite variety of cuts for envy-free, proportional cake reducing. It was a doubtlessly astronomical variety of cuts, but it surely was finite — answering a long-standing query within the subject.

Cake reducing for n individuals, Aziz and Mackenzie reported, may require as many as n^n^n^n^n^n operations. That’s a completely unreasonable quantity. The utmost variety of steps for 5 individuals can be round 2 x 10^2,180. Which means 5 individuals reducing the cake billions of occasions per second for 100 trillion years may barely be getting began.

Nevertheless, Aziz says the algorithm may be tailored to a extra cheap, although nonetheless actually huge higher sure if the partygoers, for instance, enable for somewhat cake to be left over. And it’s nonetheless potential that mathematicians may convey that higher sure decrease sooner or later.

The cake-cutting drawback endures

Explorations into the query of learn how to pretty reduce a cake aren’t over. Impressed by Procaccia’s 2010 paper on truthfulness, pc scientist Biaoshuai Tao of Shanghai Jiao Tong College investigated what occurs once you attempt to account for dishonest cake eaters. “If everybody is aware of how the cake is allotted, then I ought to get extra if I inform the reality,” he says.

However in some circumstances, dishonesty can yield a bonus. If Alice and Bob have been to divide a cake, and Alice knew that Bob all the time most popular chocolate, she may knowingly divide the cake unequally so the smaller piece contained extra chocolate. Then Bob would select based on his choice, and Alice would get the bigger piece.

In his work, offered in July 2022 on the Affiliation for Computing Equipment Convention on Economics and Computation, in Boulder, Colo., Tao discovered that truthfulness and proportionality are incompatible, making it unimaginable to assemble a cake-cutting algorithm that strictly ensures truthfulness, proportionality and no envy.

Sensible purposes for cake reducing additionally proceed to abound. Klaus, in Lausanne, factors to high school alternative for instance.

A district with restricted seats in sure colleges has to steadiness the varsity board priorities — scores on entrance exams or geographic distribution, for instance — with the preferences of fogeys to attempt to discover a proportional answer with a good worth. “Previously, colleges have been simply assigned … with out asking individuals what they need,” Klaus says. “The college alternative comes from the truth that the preferences of the dad and mom or the children can be taken under consideration.”

And there are many different real-world purposes for questions of truthful division. Brams has used concepts from cake reducing to review truthful voting procedures. (To elect their leaders, not less than 4 scientific societies, together with the Mathematical Affiliation of America, adopted an algorithm developed by him.)

Procaccia has utilized truthful division algorithms to mannequin meals allocation. Aziz is exploring purposes starting from learn how to divvy up chores or different duties that may’t be divided to learn how to greatest schedule medical doctors’ shifts in hospitals.

Others are finding out truthful allocation of products that may’t be cleanly divided. After a divorce, as an example, former companions may come to settlement on a good break up provided that some objects are taken out of consideration. These investigations embrace approaches which are near envy-free if not mathematically good.

Even after a long time of investigation, cake reducing isn’t like a easy jigsaw puzzle with a well-defined answer. As a substitute, over time, it has developed right into a form of mathematical sandbox, a constructive playground that brings collectively summary proofs and intuitive purposes. The extra researchers discover it, the extra there may be to discover.

“I’m taken with it not solely as a result of it’s lovely in math,” Tao says, “however I nonetheless consider there’s so much to be completed.”