Your Deal is Better than my Deal
Do you know how to cut a cake? I mean, mathematically. There is a whole area of mathematics that studies cake cutting.
Mathematicians usually assume that each person has their own idea of what is the best part of the cake. Suppose three sisters are celebrating the New Year by having a cake. Anna likes only icing, Bella likes only chocolate chips, and Carol likes only pieces of walnuts mixed into the cake. Mathematicians want to cut cakes fairly. But what is fair? Fair is fair, right? Wrong. There are several different notions of fair cake division.
There is a proportionate division. In such a division every sister gets at least one-third of her value of the cake. This seems fair. Let’s see an example. Anna gets one third of the icing, Bella gets one third of the chocolate chips, and Carol gets everything else. This is a fair proportionate division. Each of the sisters believes that she got at least one-third of the cake, in their own value. But it doesn’t seem quite fair.
There is a stronger notion of fairness. It is called envy-free. In this division each sister gets at least one-third of the cake and, in addition, none of the three sisters would improve their value by swapping pieces. That means, if Anna wants only icing, not only does she get at least one-third of the icing, but also no one else gets more icing than Anna. The previous example of the proportionate division is not envy-free. Carol got two-thirds of the icing, so Anna would want to switch with her.
Let’s try a different division. Anna gets one third of the icing, Bella gets the chocolate chips and another third of the icing, and Carol gets all the walnuts and another third of the icing. Formally, this is envy-free cake cutting. But poor Anna. What do you think Anna feels when she sees the smiles of contentment on the faces of her sisters? Whoever invented the name doesn’t understand envy. Anna got one-third of the cake by her value, but the other sisters got the whole cake!
Luckily mathematicians understand this conundrum. So they invented another name for a cake division. They call a division equitable if everyone values all the pieces the same. So the division above is envy-free but not equitable. Let’s try again. Let’s give each sister one-third of all the components of the cake. This division is very good mathematically: it is proportionate, envy free, and equitable. By the way, envy-free division is always proportionate. This division seems fair. But is it a good division?
There is another term here: Pareto-efficient division means that it is impossible to make one person feel better, without making another person feel worse. All divisions above are not Pareto-efficient. Moving some icing from Carol to Anna, doesn’t decrease the value for Carol, but increases the value for Anna.
There is an even better way to divide the cake. We can give the icing to Anna, the walnuts to Bella, and the chocolate chips to Carol. This division is envy-free, equitable, and Pareto-efficient. It is perfect. Mathematicians even have a word for it. They call it a perfect division.
Mathematically this division is perfect. Unfortunately, sisters are not. I know an Anna who would still envy Bella.
Share:
James:
In the penultimate paragraph, I think walnuts and chocolate chips should be the other way around? But even then, I don’t understand why that division is “equitable”. The definition given for equitable is that “everyone values all the pieces the same”. But in the proposed division, everyone values their own piece as much as the whole cake, and puts value 0 on the other pieces.
13 June 2016, 10:48 amtanyakh:
James, you are right about the switch, I should fix that.
For the equitable division each person gets one third of the icing, walnuts and chocolate chips. Each sister values each piece the same way.
13 June 2016, 11:31 amJames:
Hi Tanya, sure, the (1/3,1/3,1/3), (1/3,1/3,1/3), (1/3,1/3,1/3) division is equitable. But in the penultimate paragraph you are talking instead about the (1,0,0), (0,1,0), (0,0,1) division, and you say “This division is envy-free, *equitable*, and Pareto-efficient”. This is the one that doesn’t seem equitable according to your definition (unless I misunderstand).
15 June 2016, 4:31 amtanyakh:
James, thanks. Two typos in on post. I will fix this.
15 June 2016, 1:01 pmSamuel:
For certain approximations of “a cake”, with a spoon, on the fly, while walking through the kitchen, when no one is looking.
21 June 2016, 8:12 pmAllison:
Hi Tanya, its Allison from Expii!
28 June 2016, 12:33 pmWe’ve been keeping up with your blog and we love what you come out with.
I’m not sure if you’re aware of the Spirit of Ramanujan Talent Initiative but Expii, a free interactive math and science website, is partnered with IFC Film: The Man Who Knew Infinity! We are searching for undiscovered math talent. We wanted to specifically reach out to you because of your passion for mathematics and your connection with your audience. Expii would love for you to share the search and your thoughts on your blog!
More info about the search can be found: http://www.expii.com/ramanujan.
Walt French:
There’s also the frictionless free-market solution: after an arbitrary initial allocation (perhaps, 1/3 of everything to each), each sister is able to swap some parts until she is happy she has gotten the best deal she can. It’s apparently important that the initial allocation be deemed as “fair,” even if it’s not the best for each sister.
Economists have a lot of experience with this, under the rubric of the Coase Theorem. (Coase apparently disclaimed credit.)
Yes, this could result in a mess of crumbs and smeared frosting…that’s and example of violating the “frictionless” clause. Only after doing this as a thought exercise, should the sisters actually cut the cake.
15 July 2016, 1:11 pm