Skip to main content

Algorithm solves cake-cutting problem that has haunted mathematicians

cake cutting algorithm fruitcake
Image used with permission by copyright holder
We’ve all been there before: moving into a new apartment with housemates and trying to figure out who owes what each month. It’s easy enough if everyone gets the same identical room, but inevitably there is one person who gets the slightly larger bed, or the nice view with no road noise, or the ceiling that doesn’t leak, or the en-suite bathroom.

The same is true of a variety of other division tasks: from dividing up leftover pizza — does one slice of meat feast equal two slices of cheese? — to more serious examples like divorce settlements.

Recommended Videos

It is this type of problem that mathematicians have long investigated with the so-called ‘cake-cutting problem.’ Cake cutting is based around a scenario in which a varying amount of siblings or friends divide up a cake with multiple toppings, where everyone wants to be treated equally, but has different requirements and preferences.

Please enable Javascript to view this content

“Fair division is something a lot of real world problems rely on,” Simon Mackenzie, a postdoctoral researcher at Carnegie Mellon University, told Digital Trends. “Cake cutting is a good metaphor to think about these fairness problems. It’s also an incredibly elegant problem from a mathematical perspective.”

As Quanta Magazine notes, in the 1960s an algorithm was created that could divide up a cake between three players, without sparking any envy. But for more than three players, people have been relying on a 1995 algorithm which could conceivably run for a virtually unlimited number of steps to come up with an answer.

In a new paper, due to be shown off at next week’s 57th annual IEEE Symposium on Foundations of Computer Science, Mackenzie and colleague Haris Aziz describe a more efficient, envy-free cake cutting algorithm, capable of solving the problem in a finite number of steps. This can be anywhere between three and 203 cuts of the cake. They have previously come up with solutions to both the tree and four-person variants of the puzzle.

“Even before I started my Ph.D. and got interested in fair division, this is a problem I’d been interested in out of pure curiosity,” Mackenzie said. “What got me working on it seriously was my co-author on the paper coming to me and saying we should collaborate. He thought there were some interesting communication complexity problems in cake cutting that we could look at. That’s what got us started.”

The algorithm the pair have come up with shows a drastically reduced running time is possible — and they have plans to make it even simpler and faster. It is already being hailed by computer scientists as an impressive breakthrough, partially on the complexity of the solution alone.

“This is a problem a lot of people are surprised is doable,” Mackenzie noted. “A lot of people thought it would be totally impossible.”

While part of this is certainly most exciting from a theoretical perspective — showing that a puzzle people once thought couldn’t be done, actually can be — it also has some promising implications for future solutions to real-world fair division problems and making these systems more efficient.

And who can really get upset about making the world a fairer and more efficient place?

Luke Dormehl
Former Digital Trends Contributor
I'm a UK-based tech writer covering Cool Tech at Digital Trends. I've also written for Fast Company, Wired, the Guardian…
Turns out, it’s not that hard to do what OpenAI does for less
OpenAI's new typeface OpenAI Sans

Even as OpenAI continues clinging to its assertion that the only path to AGI lies through massive financial and energy expenditures, independent researchers are leveraging open-source technologies to match the performance of its most powerful models -- and do so at a fraction of the price.

Last Friday, a unified team from Stanford University and the University of Washington announced that they had trained a math and coding-focused large language model that performs as well as OpenAI's o1 and DeepSeek's R1 reasoning models. It cost just $50 in cloud compute credits to build. The team reportedly used an off-the-shelf base model, then distilled Google's Gemini 2.0 Flash Thinking Experimental model into it. The process of distilling AIs involves pulling the relevant information to complete a specific task from a larger AI model and transferring it to a smaller one.

Read more
New MediaTek Chromebook benchmark surfaces with impressive speed
Asus Chromebook CX14

Many SoCs are being prepared for upcoming 2025 devices, and a recent benchmark suggests that a MediaTek chipset could make Chromebooks as fast as they have ever been this year.

Referencing the GeekBench benchmark, ChromeUnboxed discovered the latest scores of the MediaTek MT8196 chip, which has been reported on for some time now. With the chip being housed on the motherboard codenamed ‘Navi,’ the benchmark shows the chip excelling in single-core and multi-core benchmarks, as well as in GPU, NPU, and some other tests run.

Read more
Chrome incognito just got even more private with this change
The Chrome browser on the Nothing Phone 2a.

Google Chrome's Incognito mode and InPrivate just became even more private, as they no longer save copied text and media to the clipboard, according to Windows Latest. The changes apply to Windows 11 and 10 users and were rolled out in 2024. However, neither Microsoft nor Google documented it.

Even though this change is not a recent feature, it's odd that neither tech giant thought it was worth mentioning. Previously, the default setting was that when a user saved text or images to the clipboard history, it was synced with Cloud Clipboard on Windows. Moreover, accessing this synced content was as simple as pressing the Windows and V keys, which poses a security risk, especially when using incognito mode.

Read more