Cutting pie is harder than slicing cake, at least if you want to do it fairly. Bizarre as that may sound, mathematicians have proven it.
Julius B. Barbanel of Union College and political scientist Steven J. Brams of New York University have long studied the classical mathematical problem of cake cutting. The question is this: Suppose you have an elaborately decorated sheet cake, with chocolate icing here, vanilla icing there, a cherry in one spot, and coconut sprinkled about. Some people may prefer particular portions of the cake. How do you divide the cake so that everyone gets a fair slice? The researchers are now asking the same question about pies.
“People started thinking of cake cutting and now pie cutting as interesting recreational issues,” says Brams. “But in fact, things like divorce settlements and border disputes could be, if not settled, ameliorated by this way of thinking.” Cake works as a metaphor for any good that can be divvied up.
Cutting a decorated sheet cake is the focus of complex, ongoing mathematics research. It might appear “simple as pie,” however, compared with the challenges of cutting a decorated pie.
The difference lies in the cutting. We slice pies into wedges, but we cut sheet cakes into rectangles.
Mathematicians simplify cake cutting by assuming that all slices are perpendicular to one particular side of a rectangular cake, with no crosswise cuts. Following that rule, there is only one way to split a rectangular cake into two equal-size pieces.
For a pie, however, there are an infinite number of ways, because there an infinite number of lines going through the center of a circle. That simple difference leads to a world of mathematical trouble.
Furthermore, mathematical analysis of cutting decorated cakes and pies assumes that the portions are not necessarily of equal size. That complicates the challenges of cutting fair sizes of cake and makes pie cutting even more complex, if not impossible.
Barbanel and Brams wanted to find a way of cutting a pie that is “envy-free,” meaning that each person is at least as happy with his own piece as he would be with anyone else’s. They also wanted to make sure the division is “efficient,” so that no other way of dividing the pie would be better for one person without becoming worse for others.
For cake, there are procedures for finding, or at least approximating, envy-free and efficient cuts for any number of people. But for pie, the situation is more difficult, the researchers found. Splitting a decorated pie between two people is not so tough, but creating fair shares for more than two people may be impossible.
For two people, the researchers found that it is possible to cut slices that are not only envy-free and efficient, but also “equitable.” For example, you might get a larger piece than I get, but I may think that I got 60 percent of the value of the pie because I got the side with all the coconut, while you think you got 60 percent of the value of the pie because you got the side with the cherry on it. Since we each think we got 60 percent, it’s “equitable.”
Although researchers know that equitable division exists, they don’t know how to produce it. They know how to cut a pie into two pieces in a way that is envy-free and efficient, but not necessarily equitable.
The method is like the classical “I cut, you choose” approach to cutting a cake: I cut the cake into two pieces that I perceive to be equal in value if not in size. Then, you choose the piece you prefer. Neither of us will envy the other, and there will be no way of increasing one person’s share without decreasing the other’s share. But it probably won’t be equitable: From my perspective, I will get half the value of the cake. However, since you get to choose between the two pieces, you may perceive your piece as greater in value.
Applying the method to pies is more complicated, because there are infinitely many ways to cut a pie into two pieces that I perceive as equal in value. If the pie had a clock face and the clock’s two hands were knives, pointing the hands to 12 and 6, for example, or to 10 and 4 would produce two equal-size pieces. But if there is a special piece of chocolate beside the 2 on the clock face, I might point the hands at, say, the 1 and the 3 if I thought a small piece of pie with the chocolate would have the same value as a far larger piece with no chocolate.
If you and I were using “I cut, you choose” to divide a pie, we could use a method that is like using knives as clock hands. First, I would position the end of one knife at the center of the pie and point the knife toward 12 o’clock. Then I would put the second knife in a position going from the center to another point on the edge, so as to produce two pieces I perceive as equal in value. Then, you would note your perceived value of each piece.
Next, I would rotate the first knife a bit, say, to one o’clock. I would again adjust the second knife to suggest two pieces that I think are of equal value. You would again note your perceived value of each piece. Once we’ve gone all the way around the pie, you’d tell me which positions of the knife gave you the piece with the most value, and I’d cut there.
In theory, we would need to do this an infinite number of times, because there are an infinite number of points on the edge of a pie. Mathematicians work with equations that represent an endless version of the “I cut, you choose” procedure.
As the player who does the “choosing,” you will most likely get a slice you think is worth more than half the value of the pie. As one who does the “cutting,” I will get a slice I think is worth exactly half. So the division isn’t equitable, even though neither player “envies” the other and it’s impossible to increase one player’s share without decreasing the other’s.
If at least four people are sharing a pie, the situation is much more challenging. The researchers show that sometimes it is impossible to cut the pie so that it’s both envy-free and efficient, much less equitable.
Oddly, for three persons, no one knows whether it’s even possible to have an envy-free, efficient division. “We worked and worked and worked at it,” says Barabanel. So far, they haven’t figured it out. “There are weird situations in math like that sometimes,” he says, where the middle dimensions are the hardest to figure out. The Poincaré Conjecture is one example.
Will pie-cutting turn out to have the same kinds of real world applications that cake cutting has? “I think it’s a bit of a stretch,” Brams says. “But I would say that if you’re trying to divide land on an island and you want people to have pieces of the shoreline, then pie cutting is better.”
And, of course, it’s a relief to learn that fair-minded mathematicians won’t have to put up with rectangular pies anymore.
To comment on this article, go to the MathTrek blog version.
