What is the fairest way to cut your Christmas cake?

That’s Maths: Scientists continue to try to crack the code of ‘envy-free’ cutting

Cake cutting may sound limited, but it is important for many practical problems. Photograph: iStock/Getty Images

Cake cutting may sound limited, but it is important for many practical problems. Photograph: iStock/Getty Images

 

As Christmas approaches, the question of fair sharing comes into focus. Readers can rejoice that there has been a recent breakthrough in cake-cutting theory. Cake cutting may sound limited, but it is important for many practical problems. A cake is a metaphor for a parcel of land to be divided, broadcast frequencies to be allocated, divorce settlements, chores to be done by flatmates, border resolutions or any other valuable or scarce resource to be shared.

A key requirement of fair division is that everyone should be happy after the share-out; no one should feel that they have done worse than the others. This condition is known as envy-free sharing. In this case, every partner feels that their share is at least as good as any other share, according to their own subjective evaluation. When the cake is cut and served, Jack has no reason to grumble that Jill’s piece is bigger or better. Things get trickier when the cake is unevenly iced or the cherries are all on one side.

The Moving Knife

There is a fascinating method of cake-cutting called the moving knife procedure. Suppose there are five people for dinner and the cake is perfectly round and uniform. Anne makes a cut from centre to edge and, keeping the knife-point at the centre, moves it slowly round through a growing angle. As the sector grows, anyone is free to shout “cut”. Let’s suppose Bob calls, and takes the piece. He must be satisfied with it, as he made the call. The others have no grounds for complaint, since they were free to call “cut” and did not do so.

Now Anne continues to move the knife until another cut is called; she can call herself if she does not want to be forced to take the last piece. The procedure continues until only the fifth piece remains. If the person getting this feels cheated, tough luck: he or she was free to call “cut” at any time and chose not to.

I Cut, You Choose

The moving knife method is fair, but it is not envy-free. When the pieces are compared after division, someone may well complain that another piece is better than theirs. With only two partners, an envy-free solution has been known since biblical times, the method known as “I cut, you choose”. In the Book of Genesis, when Abraham and Lot came to the land of Canaan, Abraham divided it into a western and an eastern part, and invited Lot to choose. Lot chose the eastern part, which included Sodom and Gomorrah, and Abraham was left to take the western part.

There are more than 30 recent papers under the heading “envy-free cake cutting” on the scientific repository arXiv

When there are three or more partners, the problem becomes much more challenging. Recently, an envy-free algorithm has been found that works for any number of people. In 2016, computer scientists Haris Aziz and Simon Mackenzie presented a talk at a symposium on the foundations of computer science: A discrete and bounded envy-free cake cutting protocol for any number of agents.

The new method is of theoretical interest since it guarantees envy-freeness. While elementary in principle, it is too complex to describe here. Moreover, even for four people, it may require a huge number of cuts and is quite impractical. The problem continues to attract attention of researchers: there are more than 30 recent papers under the heading “envy-free cake cutting” on the scientific repository arXiv.

Perhaps the most practical way to maintain harmony over the festive season is to cut the cake, number the pieces and draw lots to determine who gets what. Happy Christmas.

Peter Lynch is emeritus professor at the School of Mathematics & Statistics, University College Dublin. He blogs at thatsmaths.com.

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
GO BACK
Error Image
The account details entered are not currently associated with an Irish Times subscription. Please subscribe to sign in to comment.
Comment Sign In

Forgot password?
The Irish Times Logo
Thank you
You should receive instructions for resetting your password. When you have reset your password, you can Sign In.
The Irish Times Logo
Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.
Screen Name Selection

Hello

Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
Forgot Password
Please enter your email address so we can send you a link to reset your password.

Sign In

Your Comments
We reserve the right to remove any content at any time from this Community, including without limitation if it violates the Community Standards. We ask that you report content that you in good faith believe violates the above rules by clicking the Flag link next to the offending comment or by filling out this form. New comments are only accepted for 3 days from the date of publication.