let them eat cake

On my niece Kathryn's first birthday, she experienced cake for the very first time. Having lived primarily on breast milk and pureed baby food up until then, she had no idea the kind of succulent sweetness that was in store when the round, chocolate-frosted concoction was placed before her, a single candle burning in the center. She learned fast, though: when that first taste of frosting touched her lips, a look of awed wonder spread across her cherubic toddler face. Then she literally buried her face in the remaining cake to wallow in this newfound gastronomic delight -- to the horror of her mother, who had neglected to explain that birthday cakes are meant to be shared by the entire family. (I could post photos, but I've embarrassed my niece -- who is now 14 -- quite enough for one day.)

Children, needless to say, are not big on sharing; my nieces and lone nephew are no exception.  It was a cruel blow when they learned they must share, and they responded as all kids do: by becoming experts in measuring down to the last crumb exactly how big (or small) a given slice of cake might be. Every parent has had to deal with the pained cry: "But his piece is bigger than my piece!" And no amount of rational  explanation will convince said child otherwise, or assuage their sense of being deeply wronged or slighted. 

I was surprised to learn this past week that kids might have a point: it can be quite difficult to divide a cake perfectly evenly, particularly if size is not the only variable. In fact, it's a well-known, knotty mathematical conundrum, with some practical implications extending beyond negotiating childish disputes over equitable division of cake. In a paper to be published in the December 2006 issue of Notices of the American Mathematical Society, Steve Brams (New York University), Michael Jones (Montclair State University) and Christiam Klamler (University of Graz, Austria) uses mathematics to suggest a new strategic method for the equitable division of delicious cake. (The men specialize in political science, mathematics and economics, respectively -- a truly interdisciplinary collaboration.) 

A pdf of the full paper is available at a non-public Website, which I don't feel comfortable linking to here; it is supposed to be non-public, after all, and we try to respect boundaries here at Cocktail Party Physics. Try contacting the American Institute of Physics Public Information office if you want more details. I'll just provide a brief outline of their argument here.

To wit: if a cake must be evenly divided between two (clearly gluttonous) people, the most common method since time in memorial is the "you cut, I choose" approach. Let's say, for example, that Jen-Luc Piquant must share her after-dinner cake with her Cyber buddy, Kimba. How can she ensure she gets her fair share (especially since Kimba -- a.k.a., the Human Hoover -- already devoured the lion's share of the preceding meal)? Deploying the "cut and choose" method, she cuts the cake and Kimba gets to choose the piece he most prefers. This gives her great incentive to cut the cake as evenly as possible, knowing that he will most likely choose the biggest piece for himself. Or will he?

As with most things in life, it's rarely that simple. The primary advantage to the cut-and-choose approach is that it is "envy free": neither person envies the other's slice because they each know they have received at least half of the cake. But Brams et al. point out that this assumes both parties have identical values -- that is, they are both angling for the largest slice of cake they can get in the negotiation. But values are highly subjective: what if Kimba actually values the slice with more (or less) frosting, or Jen-Luc would be willing to opt for a smaller slice provided she gets the marzipan rose decoration? Or what if the cake has half chocolate, half vanilla icing, and Kimba vastly prefers the chocolate? In those cases, equitability is not so easily defined.

Brams and his cohorts propose an alternate cake-cutting method, which they call "Surplus Procedure" (SP). Using SP, Jen-Luc can cut the cake in such a way that the value she places on her piece is approximately the same as the value Kimba places on his piece -- possibly with the result that both might feel they are making out like a bandit and getting 65% of their heart's desire. It all comes down to perceived value.

Of course, it gets a bit more complicated if the cake must be divided between three people: say, Jen-Luc, Kimba, and La Belle Chanteuse (whose real-world alter ego goes by Peri). For that problem, Brams & Company devised an extention of SP, called "Equitability Procedure" (EP) which ensures that everyone gets, say, 40% of what they want, based on their respective values. Beyond three people, though, the likelihood of achieving both equitability and envy-freeness becomes much less likely. (I should probably note that the actual conundrum is achieving equitable division with the least number of cuts: say, a two-person/one-cut, or three-person/two-cut strategy. Beyond four "players," apparently, there is no known procedure that will result in an envy-free division of a cake unless an unbounded number of cuts is allowed.)

Among the other practical applications of the SP method: fair division of land. if Jen-Luc values waterfront property and Kimba values land at the edge of a forest, the SP method will yield a solution that lets them divide the land in such a way that both will ultimately place the same value on their respective parcels of land. "We're proposing a new, more scientific approach to dispute resolution," Brams says in the official press release for the upcoming paper. "Even if it is not directly applicable, the reasoning that goes into fair-division algorithms is valuable. It shows how mathematics can contribute to making dispute resolution more rigorous and precise."

Brams knows of whence he speaks: he's the co-author (with Alan D. Taylor) of The Win-Win Solution: Guaranteeing Fair Shares to Everybody, which describes a broad range of contexts where fair-division algorithms can be applied. It's not just about birthday cake: the Camp David peace accords and the divorce of Donald and Ivana Trump are among the more notable examples. New York University has actually patented one of Brams' algorithms (the "adjusted winner" algorithm). Patents: they're not just for computer algorithms anymore!

The cake-cutting method appears to be a subfield of game theory, a branch of applied mathematics and economics devoted to the study of situations in which "players" choose different actions in an attempt to maximize their returns. Survivor adopts something of a game theory approach, although expertise in that does not guarantee a win; the primary attribute one needs, judging from the various seasons, is to be a manipulative sociopath. (Interestingly, both SP and EP are "strategy proof," according to Brams. The players can't manipulate the procedures to their advantage.) The most famous example is the "Prisoner's Dilemma," in which two partners in crime have been arrested and placed in separate cells, and offered the chance to confess the crime. There's an extensive matrix of expected payoffs, depending on each scenario each player might choose. It's too complicated to explain in depth in a single post, but you can read more about game theory here, and a bit about its long, colorful history here.

So the next time you're at a party, and it comes time for the cutting of cake, think about divvying things up in terms of "envy-freedom" and "equitability' -- just for giggles. If the subjective values of the partygoers all rest primarily on the size, it'll be vital to divide the cake into perfectly equal slices. To make your job easier, Kitchen Fantasy offers an eight-slice cake and pie divider, which promises to create perfectly equal 10-3/4 inch slices of cake every time -- for only $19.99. It could be the answer to all your cake-dividing woes... at least if they only involve eight party guests.

 

Comments

[JScarry]

Just one nit: it's "immemorial" not in "in memorial". This would actually be an interesting topic to write about. You see these homophone-like substitutions all the time on Slashdot. One would think that they would occur frequently for words that are used predominantly in speech as opposed to writing. In speech you'd be more likely to have mispronunciations based on how the word looks on paper.
And an aside, I don't think any method of distribution would stop my nieces and nephews from arguing. I think they do it not because they want the object but more as a way of challenging and maintaining pecking order.

[Blake Stacey]

"In memorial" might qualify as an eggcorn:

http://itre.cis.upenn.edu/~myl/languagelog/archives/000018.html

[LucysGranddaughter]

You write: "can cut the cake in such a way that the value she places on her piece is approximately the same as the value Kimba places on his piece -- possibly with the result that both might feel they are making out like a bandit and getting 65% of their heart's desire. It all comes down to perceived value."

In order for this to work in real-world disputes like land settlements, then, wouldn't the different parties have to value the land for different reasons? In the cake example, one person could like the chocolate part, another the vanilla. But for land, doesn't everybody want the fertile areas? the waterfronts? And how are these "perceived values" actually defined and measured in the real-world situations?

[Jennifer Ouellette]

Yes, exactly --but you're not quite correct in saying that "everybody" wants the same thing when it comes to land. It depends on what they plan to use it for, among other variables -- who cares if its fertile if you're looking to open city dump? Or maybe someone has a health condition, or fear of water, that makes them prefer inland areas. The point in both examples is not that everyone gets everything they want, but through a long process of negotations, based on what each party values most, everyone can come away thinking they got, if not the perfect deal, at least a fair or better deal.

You should check out the full article; it goes into all this stuff in depth, far more detail than one can include in a humble blog post.

[wonderstruck]

On that cake cutter thing: depending the "stength" of the cake material to stand upright and withstand pressure applicaed while cutting(esepecially for later cuts), it must be possible to turn the cutter by a small angle and cut and hence obtain n*8 number of equal slices (provided one can guage what that right fractional turn is). And then you will probably have someone who wants just a small slice anyway and they ill bail you out, when you dont manage to turn just right.

[Calvin]

I find it extremely ironic that in one paragraph we read about the childishness of not sharing and in the very next paragraph we read about this whizzy cool new paper on how to share equitably ... but the authors aren't sharing it.

Or is it just me.