Fair Division
This article continues my eclectic collection of recently-learned-topic reviews. Essentially, when I’m in class or work and come across a topic I find particularly difficult, counterintuitive, or just interesting, I’ll write one of these to hopefully ease the learning process for the next poor sucker who needs to learn the topic. Today, I’ll be discussing the Fair Division problem, with a particular emphasis on the subset of problems which involve continuous value functions, and on systems with only a proportional division criterion.
Just about everyone who made it through childhood had heard the fairness algorithm “I cut, you choose”, and it is a good one. Say that Alice and Bob want to split a cake. In order to ensure both get what they consider half (or more) of the cake, Alice cuts the cake into two pieces she feels are exactly equal in quality, and Bob chooses the one he prefers. In this way, Alice is guaranteed a piece of cake whose value she perceives is exactly ½ of the total value of the pieces, since she cuts the cake herself. Bob, then, gets his pick of the halves, so he’ll only pick the piece worth most to him, guaranteeing he gets at least half of his perceived value of the slices. Something amazing to note about this solution is that it doesn’t matter how you judge the value of the cake. Maybe Alice is looking for the most frosting but Bob is looking for the biggest filling layer. Either way, each can choose according to their own criteria, and so will end up with a piece they value.
Unfortunately, when you have 3 or more people (let’s say N people), the problem of fair cake division is more difficult. In this context, we’ll take “fair division” to mean a division where each of the N individuals receives a portion of the cake they consider to have at least 1/nth the total value of the slices. So, for 3 people, each person will perceive their slice as being worth at least 1/3rd the value of all the slices combined.
One naive approach goes like this: Alice, Bob, and Charlie, as before, wish to split a cake. Alice and Bob play “I cut, you choose” on the cake as a whole, then each divides their half into three pieces of equal value to them. Charlie then chooses his favorite third from each. As before, all parties are satisfied they’ve received at least their fair 1/nth of the cake. Supposing Dean now joins, and wants a quarter of the total cake, the process can be repeated, with Alice, Bob, and Charlie each dividing their pieces into fourths they see as fair, then Dwayne choosing his favorite fourth from each set. It’s not hard to see how this extends to 5, 6, 7, or more people.
The naive approach does, of course, have a big problem. The cake gets cut A LOT. Pretty soon, you’re splitting crumbs, and you’ve ruined a piece of perfect chocolate goodness. In particular, we can associate N to cuts as follows:
| N | Cuts |
|---|---|
| 2 | 1 |
| 3 | 1+2*2=5 |
| 4 | 1+1*2*2+2*3*3=23 |
| n | n!-1 |
So, our current cake-cutting algorithm is O(N!). That is a lot of cuts indeed! Let’s clean it up. I’m a particular fan of a linear solution (ie, a solution requiring N-1=O(N) cuts) that goes something like this: A mediator holds a knife over the cake, slowly moving it without changing its angle, from the left of the cake to the right. At any point, any individual may declare they wish the cake to be cut where the knife rests, taking the entire section of the cake to the left of the blade. In this way, each individual is guaranteed a piece they are satisfied with, since all but the last person declare when they feel the piece is fair. As for the last person, they get the remaining cake, and since they had not yet requested a cut, they are necessarily getting more than what they perceive as a fair minimum. This solution requires the minimum number of cuts, and has the benefit of each person’s portion consisting of a single connected slice of cake rather than whatever mishmash of trimmings provided by other methods. This method isn’t free, however. It requires all parties involved to be continuously monitoring the status of the knife and the cake, and to, at each possible moment, make a decision about whether they deem the current potential cut fair or not. This is a lot of thinking. So, we search for a discrete solution.
Our final algorithm, one requiring only n-1 cuts, as before, but this time discrete, goes as follows: Each person is given a knife to place, all parallel to one another, wherever they consider the midway point of the cake (or floor(n/2)/n for odd numbers, eg ⅖). The mediator cuts the cake between the middle knives, ensuring that for each resultant subcake, the opinion of everyone whose knife was over that subcake is that the subcake is worth more than ½ (or the fraction as before) of the total cake. This is done recursively until there are only one to two knives over each section of cake, at which point the remaining conflicting knife-holders play “I cut, you choose”, and any solitary knife-holders get their complete section. In this manner, we have established a fair cake-cutting algorithm requiring only a finite number of decisions, as opposed to the continuous algorithm before which required infinite instantaneous decisions.
I you find this topic interesting, you might want to know that in this article, we’ve been concerned with “proportional division” (the PR criterion). That is, we’re only concerned with making sure everyone gets at least their 1/n of the cake. If you want to pursue this topic further on your own, two areas of further research jump out. The first is the formalization or addition of additional criteria to the fair division problem. Envy-free (the EF criterion) is the obvious place to start. Rather than saying “Each person must get at least a subjectively fair portion”, EF guarantees “Every person will see their portion as at least as good as everyone else’s portions”. That’s a bit outside the scope of this article, but it’s certainly interesting. The other area of potential interest for those looking to deep-dive into the topic is applications of fair division to “bad cakes”. For example, splitting labor or rent, known as “envy-free chore division” or “fair division of bads”.
This article was primarily based on the talk “Halving your Cake” by Deanna Haunsperger from the Pacific Northwest MAA Chapter Meeting 2018, with some auxiliary research from miscellaneous websites and textbooks.