Algorithm solves cake-cutting problem that has haunted mathematicians

cake cutting algorithm fruitcake
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.

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.

“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?

Emerging Tech

Awesome Tech You Can’t Buy Yet: 1-handed drone control, a pot that stirs itself

Check out our roundup of the best new crowdfunding projects and product announcements that hit the web this week. You may not be able to buy this stuff yet, but it sure is fun to gawk!

Feeling nostalgic? Here are the 25 best Sega Genesis games

Although the company has since fallen into obscurity, Sega was an indisputable titan throughout the '90s. That said, here are 25 best Sega Genesis games that helped define its fabled decade.

The best cheap-but-awesome PS4 game deals under $20

The PlayStation 4 has hit its stride in recent years and is now more affordable than ever. If you have a PS4 or are thinking of buying one, we’ve collected some must-have games. The best part? Each of these is just $20 or less.
Movies & TV

The best shows on Netflix, from 'The Haunting of Hill House’ to ‘The Good Place’

Looking for a new show to binge? Lucky for you, we've curated a list of the best shows on Netflix, whether you're a fan of outlandish anime, dramatic period pieces, or shows that leave you questioning what lies beyond.

These are the 5 best free antivirus apps to protect your MacBook

Malware protection is more important than ever, even if you eschew Windows in favor of Apple's desktop platform. Thankfully, protecting your machine is as easy as picking from the best free antivirus apps for Mac suites.

These laptop bags will keep your notebook secure wherever you go

Choosing the right laptop bag is no easy feat -- after all, no one likes to second-guess themselves. Here are some of the best laptop bags on the market, from backpacks to sleeves, so you can get it right the first time around.

iPhone users are finding themselves randomly locked out of their Apple ID

According to posts on Reddit and Twitter, it looks like users on Reddit and Twitter having some issues with their Apple accounts. Specifically, it seems as though users are getting randomly locked out of their Apple IDs.

These Windows 10 keyboard shortcuts will update your OG Windows skills

Windows 10 has many new features, and they come flanked with useful new keyboard shortcuts. Check out some of the new Windows 10 keyboard shortcuts to improve your user experience.

Protecting your PDF with a password isn't difficult. Just follow these steps

If you need to learn how to password protect a PDF, you have come to the right place. This guide will walk you through the process of protecting your documents step-by-step, whether you're running a MacOS or Windows machine.

Don't know what to do with all your old DVDs? Here's how to convert them to MP4

Given today's rapid technological advancements, physical discs are quickly becoming a thing of the past. Check out our guide on how to convert a DVD to MP4, so you can ditch discs for digital files.

Here’s how to install Windows on a Chromebook

If you want to push the functionality of your new Chromebook to another level, and Linux isn't really your deal, you can try installing Windows on a Chromebook. Here's how to do so, just in case you're looking to nab some Windows-only…

Edit portraits with A.I. and adjust focus in the new ON1 Photo RAW 2019 editor

ON1 Photo RAW 2019 now has a dedicated tab for portraits that automatically recognizes faces to help with retouching. The update also brings a new focus stacking tool, enhancements to layers, and improvements to local adjustments.

Your MacBook can live in the lap of luxury with this leather case

Though there are several cases which we think are best for covering up MacBooks, Twelve South's Journal case is one of the newest available, providing luxurious leather coverage for your Apple laptop.

Here's our head-to-head comparison of Pandora and Spotify

Which music streaming platform is best for you? We pit Spotify versus Pandora, two mighty streaming services with on-demand music and massive catalogs, comparing every facet of the two services to help you decide which is best.