How to cut a cake so everyone is happy

Everyone has cut a cake only to have someone complain about the size of their piece. It’s a problem that can be solved by applying the mathematical theory of fair division, a branch of game theory that was born in the 1940s from the work of three Polish mathematicians: Hugo Dyonizi Steinhaus, Stefan Banach and Bronisław Knaster. Besides cutting cake, the theory of fair division has countless other applications. It can be applied to task assignment, auctions, air traffic control, inheritance distribution, divorce settlements and more.

The first step in fair division is for everyone to place a value on the property to be divided. If the asset is homogeneous, like money, land or a plain cake with no icing, the value of each piece will be determined by size or quantity. But if the asset is heterogeneous, like a cake haphazardly sprinkled with candied fruit and almonds, people may place different values on individual pieces. Everyone knows that some people love candied fruit and others hate it. Strangely enough, disagreement about the tastiest part of the cake can produce better results when it comes time to divide it up, than when everyone shares the same opinion.

The second step is to carefully define fair division, which potentially leads to different outcomes. With n number of people, a division is proportional if each person considers the value the piece received to be greater than or equal to 1/n. To make sure that no one feels slighted, we can apply the concept of envy-free division, which guarantees that no one will want somebody else’s share more than their own.

The apportioning process consists of a series of instructions to be followed step-by-step – in other words, an algorithm. The simplest form of division – when there are only two people – has been around since biblical times. In this case, the “I cut, you choose” algorithm should lead to a proportional and envy-free division. Remember the Bible story of Abram (later called Abraham) and his nephew, Lot?

But when three people are involved – let’s call them Antonio, Beatriz and Carolina – things get more complicated. In the 1960s, John Selfridge and John Horton Conway independently developed identical, envy-free division procedures. This is how it works: Antonio cuts the cake into three parts, which he considers equal. Next, Beatriz has a decision to make. If she thinks one piece is larger than the other two, she trims it to make everything equal. But if Beatriz thinks two pieces are equally larger than the third piece, she does nothing. Carolina then chooses the piece she thinks is larger and tells Beatriz to choose next, keeping in mind that if Beatriz cut one of the pieces down to size in the previous step, that’s the piece Beatriz must choose, unless Carolina has already chosen it. Antonio is the last person to choose a piece.

For now, everyone should be happy. Antonio gets to keep one of the original pieces that he cut and considered equal in size. Beatriz gets to choose the one she thinks is bigger, and since Carolina was the first person to choose, she can’t feel envious of anyone.

The only thing left to do is to divide the extra piece that Beatriz may have decided to trim from the larger piece. Now it’s Carolina’s turn to divide it into three equal pieces. Beatriz, Antonio and Carolina then choose in order, taking the piece they think is bigger. Again, this is a fair distribution because Beatriz is the first to choose, Antonio can’t envy Beatriz because he thought the three original pieces were equal anyway, nor can he envy Carolina because he chose a piece before her. Lastly, Carolina can’t envy anyone because she was the one who divided the extra piece into equal parts.

So what happens if something must be divided among more than three people? In 1995, Steven Brams and Alan Taylor developed a methodology that works for any number of people, but it has one major problem – there is no way to predetermine the number of steps in the algorithm, or even the number of divisions that will be needed. But these numbers do have finite values because the algorithm will eventually produce a result. What isn’t known is their maximum value – that depends on the nature of the cake to be cut and the preferences of those who want a piece. In fact, no matter how many cake-cuts are needed, the valuations of the cake-eaters can always be determined, since the Brams-Taylor algorithm will always have more steps than the number of cake-cuts.

In 2016, Haris Aziz and Simon Mackenzie developed an envy-free division procedure for bounded groups of people that depends only on the number of participants. The procedure requires patience because the number of steps in the algorithm and the number of cake-cuts can be formidably high. For a division between only four people, the number of steps is already higher than the total number of atoms in the universe. While this is the guaranteed maximum number of steps in the algorithm, whatever the people’s preferences may be, all the steps may not be needed. If everyone gives in a little, agreement can be reached before the universe is finished. In any case, there is still plenty of room for improving the result.

While complicated algorithms may be overkill when it comes to cutting your cake, some situations have much larger implications and fair division is paramount. For example, when the Allies split Germany into four zones after World War II, Berlin became the disputed extra piece, and the city was quickly divided into smaller zones to be shared equally.

Sign up for our weekly newsletter to get more English-language news coverage from EL PAÍS USA Edition