How do you divide a cake fairly among 'n' people?

[two_thirds]

The moment of cutting a cake or pizza can be tense, especially if you're sharing these treats with your siblings or friends. The traditional technique is the famous "you cut, I choose," which helps neutralize any bad intentions from the person cutting or the pain of whoever might end up with the smaller piece. But why not use math to help with this process? After all, nobody wants to have less cake than the other person. Maybe only in cases of dieting.

Two computer scientists, Hariz Aziz and Simon Mackenzie, researchers at the University of New South Wales, Australia, recently developed an algorithm in 2016 that can help understand the intricacies of a fair division. In short, the pair described a way to divide a cake among n people, where "n" is a variable that can represent any number.

It may seem strange, but this is an important problem because it serves as an analogy for numerous, not-so-trivial, resource allocation problems, such as land division, asset seizure, network data, and others. Many even believed that creating such a formula would likely be impossible.

One of the last advances in this problem was made in the 1960s, when an algorithm was developed for division between three agents. Decades later, other mathematicians managed to add another agent to the formula. However, the algorithm was unrestricted in its formulation, which meant that a division could have anywhere from 100 to a billion steps.

Aziz and Mackenzie's work in the field began where their predecessors left off, creating a division between four agents in 2015. The difference is that their protocol only involved between 3 and 203 cuts. Still quite a lot, but much more restricted than the previous version. Their most recent paper, however, went further, defining an algorithm that works for any number of people.

The problem is that, due to its extreme complexity, dividing a cake among N people using this method could require n^n^n^n^n^n steps. This means that if 5 people want to divide a cake fairly, the maximum number of cuts will be 5 to the power of 5, to the power of 5, to the power of 5, to the power of 5 to the power of 5. An astronomical number, in short. Therefore, this is an impractical algorithm for everyday use, but it will open doors to new discoveries in the field.

A fun introduction to the cake division problem can be seen in this video by mathematics professor Eugenia Cheng from the University of Sheffield, England.

[two_thirds]
[clear]