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.