# Fair cake cutting gets its own algorithm

##### July 16, 2014, Springer

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.

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.

Explore further: Researchers develop 'envy-free' algorithm for settling disputes

More information: Barbanel, J.B. & Brams, S.J. (2014).Two-Person Cake Cutting: The Optimal Number of Cuts, The Mathematical Intelligencer. DOI: 10.1007/s00283-013-9442

## Related Stories

#### Researchers develop 'envy-free' algorithm for settling disputes

February 3, 2014

Whether it's season tickets to Green Bay Packers' games or silver place settings, divorce and inheritance have bred protracted disputes over the assignment of belongings. But, now, a trio of researchers has found a method ...

#### Cutting a round cake with knife, elastic bands and principles

June 19, 2014

(Phys.org) —There is a good way and a bad way to cut cake. Ask Alex Bellos the author of The Grapes of Math: How Life Reflects Numbers and Numbers Reflect Life. Bellos talks about scientific principles governing a better ...

#### Photo + fragrance of chocolate cake = more chocolate cakes sold

February 11, 2014

Fashion magazines come pre-loaded with scratch-and-sniff panels for perfume and aftershave, but what about advertisements for foods like chocolate chip cookies and fresh-baked bread? According to a new study in the Journal ...

#### Rewards programs: When do consumers compare experience over value?

October 22, 2012

Consumers are often less satisfied when they buy or receive products that are easily counted because this makes them focus on value instead of experience, according to a new study in the Journal of Consumer Research.

#### The great industrial bake-off

May 10, 2013

Not everyone can rustle up a Victoria sponge, lemon drizzle cake or a jam roly-poly, so shop-bought cakes remain a mainstay of high tea for many a household. Thankfully, quality control on food production lines continues ...

#### U of T food engineers help set world record

May 12, 2011

Graduate students from the University of Toronto's Department of Chemical Engineering and Applied Chemistry’s food engineering laboratory helped to set the Guinness Book of World Record May 10 for largest ice cream cake ...

## Recommended for you

#### An algorithm for refugee resettlement could boost employment and integration

January 18, 2018

The global refugee crisis has ignited debate in nearly every country that has seen an influx of refugees and asylum seekers. In most countries, the conversation surrounding refugees has tended to focus on whether or not they ...

#### Crowds within crowd found to outperform 'wisdom of the crowd'

January 18, 2018

A team of researchers affiliated with institutions in Argentina, the U.S. and Germany has found that there is a way to improve on the "wisdom of the crowd"—separate the people in a given crowd into smaller groups and let ...

#### Study sheds new light on ancient human-turkey relationship

January 17, 2018

For the first time, research has uncovered the origins of the earliest domestic turkeys in ancient Mexico. The study also suggests turkeys weren't only prized for their meat—with demand for the birds soaring with the Mayans ...

#### Court software may be no more accurate than web survey takers in predicting criminal risk

January 17, 2018

A widely-used computer software tool may be no more accurate or fair at predicting repeat criminal behavior than people with no criminal justice experience, according to a Dartmouth College study.

#### Want people to work together? Familiarity, ability to pick partners could be key

January 16, 2018

The key to getting people to work together effectively could be giving them the flexibility to choose their collaborators and the comfort of working with established contacts, new research suggests.

#### Ancient DNA results end 4,000-year-old Egyptian mummy mystery

January 16, 2018

Using 'next generation' DNA sequencing scientists have found that the famous 'Two Brothers' mummies of the Manchester Museum have different fathers so are, in fact, half-brothers.

Adjust slider to filter visible comments by rank

Jul 16, 2014
This comment has been removed by a moderator.
##### exBrit
not rated yet Jul 16, 2014
Life need not be this complex. The simple rule that we applied with our kids on all delicacies requiring division prior to consumption is as follows:
'The person who does the cutting is the last to choose their piece.'
Works perfectly with minimal discussion and zero maths.
##### Lukaz
not rated yet Jul 16, 2014
Life need not be this complex. The simple rule that we applied with our kids on all delicacies requiring division prior to consumption is as follows:
'The person who does the cutting is the last to choose their piece.'
Works perfectly with minimal discussion and zero maths.

This rule is why neither my fiancé nor I ever want to be the one to plate our meals...
##### antialias_physorg
5 / 5 (1) Jul 17, 2014
'The person who does the cutting is the last to choose their piece.'

That's what they refer to in the article when they mention the "cut -and-choose" approach. It works under some assumptions (homogeneous and infinitely divisible material) but not all.
Especially it doesn't always work when you have not equally divisible sets (think of the various pieces in pirate loot or of land with various quality measures.)

Cutting cake everyone has the same pdf (the bigger the better). So cut-and-choose works.
But as soon as you go to inhomogeneous structures things get difficult (e.g. a pizza with pepperoni, where some will favor a smaller slice if it contains more peppreoni - but the cutting person only cuts according to size you will not get a jealousy free division)
##### Expiorer
1 / 5 (1) Jul 17, 2014
it is a bit trickier (but solvable) with 3 parties
##### antialias_physorg
5 / 5 (2) Jul 17, 2014
Not entirely. Think of making divisions where the worth of a heap is contingent on which other divisions you get.
E.g. you divide into heaps some of which contain electronic equipment and some of which contain batteries. As long as you get at least one heap containing a battery the electronic equipment has a certain worth to you. If you get no such heap then the worth drops to zero.

Game theory is pretty tricky sometimes.
##### Captain Stumpy
5 / 5 (1) Jul 17, 2014
But as soon as you go to inhomogeneous structures things get difficult (e.g. a pizza with pepperoni, where some will favor a smaller slice if it contains more peppreoni - but the cutting person only cuts according to size you will not get a jealousy free division)
@AA_P
just a thought here... this is working on the assumption of certain cultures, correct?
IOW - this assumes that every person will want a piece, and that every person will argue for a piece in situations of disparity or inequality?

can this be used in a culture where it is more-or-less the responsibility of ONE (or a type) to take care of or support another (or type)?

This is just my curiosity talking here: from a cultural lens perspective.

I figure you are more up on game theory than I am.
##### antialias_physorg
5 / 5 (2) Jul 17, 2014
Well, if there are people who do not want a piece you can always reduce the problem by simply excluding these people (as they will not be jealous no matter what happens)

The invention of money in lieu of a barter system is actually already an application of game theory (via money inhomogeneous heaps of goods can be divided into a homogeneous mass of money which then can be divided)

can this be used in a culture where it is more-or-less the responsibility of ONE (or a type) to take care of or support another (or type)?

The application of this is laws (e.g. when you get additional welfare money because you are a parent as opposed to being a single).
In effect ALL of law is an application of game theory (at least the idea of what laws should do - if not the actual practice)
Jul 17, 2014
This comment has been removed by a moderator.
##### antialias_physorg
5 / 5 (2) Jul 17, 2014
Note that the division via money is not perfect, as the amount of money is not the same as the value of money
(10 Euros for a poor person is much more valuable than 10 Euros for a billionair - simply ask each what they would do in exchange for 10 Euros.)
Even with same valuation there is a difference between money now and money later (e.g. due to inflation) which adds another factor: WHEN you choose your slice.
##### jahbless
not rated yet Jul 19, 2014
The size (volume) of a slice cake is not the same as the (subjective, idiosyncratic) value of that slice, either. The procedure outlined in the article does not require this to be the case, however.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more