A pair of computer scientists recently settled one of the key questions in the theory of fair division: How can you allocate cake slices among a group of people in such a way that no one envies anyone else? The new cake-cutting protocol, which takes into account information like who enjoys vanilla frosting and who prefers chocolate shavings, is guaranteed to produce an “envy-free” division after a bounded number of steps, although it may involve cutting the cake into a mind-bogglingly large number of pieces.
Yet envy-freeness is just one of several competing notions of fairness. It’s all well and good to divide a cake in a way that won’t produce envy, but you might instead want to find an “efficient” allocation, one that can’t be improved for anyone without harming someone else. Or you might aim for “equitability,” in which everyone has the same value for the slice he ends up with. A division protocol that achieves one of these notions of fairness will not necessarily achieve the others.
Take, for example, the “I cut, you choose” procedure for dividing a cake between two people: One person cuts the cake into two slices that she values equally, and the other person chooses his favorite slice. Neither person will envy the other, since the chooser got his favorite slice, and the cutter didn’t care which slice she got. But “I cut, you choose” flunks when it comes to equitability and efficiency.
The cutter, after all, will get a slice that she values at exactly 50 percent of the value of the whole cake. But to the chooser, the two slices may have very different values — perhaps one is worth 75 percent and the other 25 percent. He’ll choose the one that’s worth 75 percent to him, so he values his slice more than the cutter values hers, violating equitability.
Or suppose we have a cake that’s half chocolate and half vanilla. If Alice loves chocolate and Bob loves vanilla, efficiency would say that we should give Alice the chocolate half and Bob the vanilla half. But that efficient division is not what will emerge from “I cut, you choose.” If Alice is cutting, she’ll have to divide the cake into two pieces that each are half vanilla, half chocolate — after all, if she made an all-chocolate slice and an all-vanilla slice, she’d risk losing the entire chocolate half to Bob.
In the case of two people, there is always some division (maybe involving multiple cuts) that is simultaneously envy-free, equitable and efficient. But when more than two people divide a cake — or a stamp collection or the family business — it is sometimes impossible to produce a division that satisfies all three notions of fairness at the same time.
That means that before people can implement a fair division algorithm, they must decide which notion of fairness they want to strive for — and that’s something mathematics can’t decide for them. When children divide an inheritance, should the Chagall painting go to the child who’s an art lover, or should it be sold and the proceeds divided? Should parents leave more money to the child who is swimming in debt, or give each child an equal share?
There’s no one right answer. In each case, it’s up to the individuals involved to decide if fair’s fair.
To learn more about the new algorithm, read Erica Klarreich’s article, “How to Cut Cake Fairly and Finally Eat It Too” on QuantaMagazine.org.
Lead image: Olena Shmahalo/Quanta Magazine
