Cutting a cake and hearing complaints about uneven slices is a common experience. To solve this, one can employ the mathematical principles of fair division, which is a subset of game theory.
This theory came to life in the 1940s, credited to three Polish mathematicians: Hugo Dyonizi Steinhaus, Stefan Banach, and Bronisław Knaster. Beyond cake slicing, this theory has numerous other uses.
It’s relevant in assigning tasks, conducting auctions, overseeing air traffic, distributing inheritance, managing divorce settlements, and much more. Firstly, everyone must assign a value to the item to be shared.
For uniform assets, such as cash, property, or a basic cake without toppings, the value is set based on size or amount. However, if the item is diverse, like a cake scattered with nuts and fruit, individual preferences might vary. Some might love nuts, while others might not.
Interestingly, differing opinions about which part of the cake is best can lead to more satisfactory divisions than if everyone had identical preferences. The subsequent step is to precisely define what constitutes fair distribution, leading to varied results.
If there are n participants, a division is seen as proportional if each individual believes that the value of their portion is at least 1/n. To ensure fairness, the notion of envy-free division is applied, ensuring that everyone values their own share over others’.
This division process adheres to a series of sequential steps or an algorithm. The most straightforward division method for two participants has ancient origins. The “one divides, the other chooses” method should result in both proportionate and envy-free allocations.
Recall the biblical story involving Abram, later Abraham, and his nephew, Lot? However, for three participants – say, Antonio, Beatriz, and Carolina – it gets intricate. In the 1960s, John Selfridge and John Horton Conway devised matching envy-free division methods.
Here’s the process: Antonio divides the cake into three, seeing them as equal. Beatriz then steps in. If she perceives one slice as larger, she adjusts it to match the others. But if two appear larger than the third, she leaves them.
Carolina then picks her preferred piece, guiding Beatriz’s choice next. If Beatriz previously adjusted a slice, she must select that unless Carolina has taken it. Antonio picks last. At this stage, contentment should prevail. Antonio has a piece he initially sliced and viewed as equivalent.
Beatriz has her top choice, and since Carolina selected first, she can’t feel jealous. If Beatriz adjusted a piece, the remnants need division. Carolina splits it into three. The trio then chooses in sequence, going for the largest slice.
This ensures fairness, as Beatriz chooses first, Antonio can’t envy the others given his initial equal division, and Carolina had the final say in the leftover piece’s distribution. But what about dividing among more participants?
In 1995, Steven Brams and Alan Taylor introduced a method suitable for any group size. However, the algorithm’s steps and required divisions are unpredictable, although finite. The exact number is influenced by the cake and individual preferences.
The algorithm always has additional steps beyond the cake divisions. In 2016, Haris Aziz and Simon Mackenzie proposed an envy-free technique for fixed groups, reliant on participant numbers. This method demands patience; for four people, the steps surpass the universe’s atomic count.
While this is the potential maximum, all steps might not be mandatory. Some compromise can hasten an agreement. Nonetheless, the method can benefit from enhancements. Though intricate algorithms might seem excessive for cake-cutting, they’re crucial in high-stakes scenarios.
For instance, post-World War II, the Allies divided Germany, with Berlin as the contentious extra. The city was then segmented further to ensure equitable distribution.