Featured Research

from universities, journals, and other organizations

Fair cake cutting gets its own algorithm

Date:
July 16, 2014
Source:
Springer
Summary:
A mathematician and a political scientist have announced an algorithm by which they show how to optimally share cake between two people efficiently, in equal pieces and in such a way that no one feels robbed.

Cutting birthday cake (stock image).
Credit: MSPhotographic / Fotolia

The next time your children quibble about who gets to eat which part of a cake, call in some experts on the art of sharing. Mathematician Julius Barbanel of Union College, and political scientist Steven Brams of New York University, both in the US, published an algorithm in Springer's The Mathematical Intelligencer by which they show how to optimally share cake between two people efficiently, in equal pieces and in such a way that no one feels robbed.

Related Articles


The cut-and-choose method to share divisible goods has been regarded as fair and envy-free since Biblical times, when Abraham divided land equally, and Lot could choose the part he wanted. But being free of envy is not the only consideration when sharing something. What happens when more than two cuts can be made, or when people prefer different, specific sections of whatever is to be divided? Barbanel and Brams believe that with a giveback procedure it is possible to make a perfect division between two people that is efficient, equitable and void of jealousy.

An objective referee (such as a Mom or a computer) is essential to the plan.. The potential cake eaters first tell the referee which parts of the delicacy they value most. In mathematical terms these are called someone's probability density functions, or pdfs. The referee then marks out the cake at all points were the pdfs of the disgruntled would-be cake eaters cross, and assigns portions. If at this point the two parties receive the same size of cake, the task is over. If not, the giveback process starts.

The party who received the larger part of the cake during the first round must give a part of it back to the other person, starting with those parts in which the ratio of their pdfs is the smallest. This goes on until the parties value their portions equally, and have the same volume of cake to eat. This method only works with a finite number of cuts if the players' pdfs are straight-lined, or are so-called piecewise linear sections.

The researchers believe the method can be used to share cake and other divisible goods such as land. In the case of beachfront property being co-owned by two developers, for example, it can help to determine who gets what strips of land to build on based on the pieces of land they value most.

"This allocation is not only equitable but also envy-free and efficient -- that is, perfect," says Barbanel.

"This approach focuses on proving the existence of efficient and envy-free divisions, not on providing algorithms to finding them," emphasizes Brams.


Story Source:

The above story is based on materials provided by Springer. Note: Materials may be edited for content and length.


Journal Reference:

  1. J.B. & Brams, S.J. .Two-Person Cake Cutting: The Optimal Number of Cuts. The Mathematical Intelligencer, July 2014 DOI: 10.1007/s00283-013-9442

Cite This Page:

Springer. "Fair cake cutting gets its own algorithm." ScienceDaily. ScienceDaily, 16 July 2014. <www.sciencedaily.com/releases/2014/07/140716165830.htm>.
Springer. (2014, July 16). Fair cake cutting gets its own algorithm. ScienceDaily. Retrieved October 31, 2014 from www.sciencedaily.com/releases/2014/07/140716165830.htm
Springer. "Fair cake cutting gets its own algorithm." ScienceDaily. www.sciencedaily.com/releases/2014/07/140716165830.htm (accessed October 31, 2014).

Share This



More Computers & Math News

Friday, October 31, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Samsung's Incredible Shrinking Smartphone Profits

Samsung's Incredible Shrinking Smartphone Profits

Reuters - Business Video Online (Oct. 30, 2014) The world's top mobile maker is under severe pressure, delivering a 60 percent drop in Q3 profit as its handset business struggles. Turning it around may not prove easy, says Reuters' Jon Gordon. Video provided by Reuters
Powered by NewsLook.com
Ban On Wearable Cameras In Movie Theaters Surprises No One

Ban On Wearable Cameras In Movie Theaters Surprises No One

Newsy (Oct. 30, 2014) The Motion Picture Association of America and the National Association of Theatre Owners now prohibit wearable cameras such as Google Glass. Video provided by Newsy
Powered by NewsLook.com
Microsoft Launches Fitness Band After Accidental Reveal

Microsoft Launches Fitness Band After Accidental Reveal

Newsy (Oct. 30, 2014) Microsoft accidentally revealed its upcoming fitness band on Wednesday, so the company went ahead and announced it. Video provided by Newsy
Powered by NewsLook.com
Mind-Controlled Prosthetic Arm Restores Amputee Dexterity

Mind-Controlled Prosthetic Arm Restores Amputee Dexterity

Reuters - Innovations Video Online (Oct. 29, 2014) A Swedish amputee who became the first person to ever receive a brain controlled prosthetic arm is able to manipulate and handle delicate objects with an unprecedented level of dexterity. The device is connected directly to his bone, nerves and muscles, giving him the ability to control it with his thoughts. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:

Strange & Offbeat Stories


Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins