Treebeard's Homepage : Stumpers

# Treebeard's Stumper Answer21 March 2003

A Real Piece of Cake

We have our annual Dunn Middle School "Piece of Cake" bike ride today! Here's a stumper about that real piece of cake that one student carried along for a treat. It's an interesting cake with an odd shape and frosting and sprinkles and a single strawberry on top. Two bikers can always share it fairly using the ancient method that "one cuts, and the other chooses." Each will then have their fair share, or at least they'll only have themselves to blame. But there were three (maybe more) bikers eager to share this cake. Is there always a fair way to divide it so no one feels cheated?

 Here's one way to divide a cake: chop it up into pieces and grab! There's no math or method, and there's no guarantee that anyone thinks it's fair.

We were scheduled to have our annual DMS "Piece of Cake" bike ride today, but we postponed it for two weeks because of the wind. *Sigh* After strong winds all week that brought down many trees locally, Friday turned out to be the perfect day.

I meant to bring along a real piece of cake and get a photo of a few kids trying to divide it. That will have to wait. But imagine that slightly squished cake to realize that this is not the simple math problem of dividing a regular solid into thirds!

Here's a "moving knife" strategy for dividing a cake between three people. One person moves the knife across the cake, and all three agree to say "stop" when they think the knife marks off one-third of the whole. The first person to shout gets the piece, and the other two divide the rest using the ancient "one cuts, the other choses" method. Similar fair division problems can be much more challenging. Maybe one person likes frosting, and the other doesn't. Half of a boat (or a baby) isn't worth half as much as the whole! Estate and property settlements are especially difficult.

Notes:

With a round cake and a single round strawberry in a random location, I'm sure there is always a geometrical way of dividing both with two straight cuts into pieces so that everyone gets an equal fair share. I'm sure the picture on the right is not right, but it gives the idea. (The magenta looks too small, I'm not sure about the other two.)

Is that always possible with an irregular shape as well? Can each person also each get a fair share of the frosting? If there are two strawberries in random places, it gets really complicated, even with multiple slices. If one person likes strawberries but not frosting, and the other two prefer frosting, then geometry doesn't help, and it gets gnarley! It helps to know what part of the cake each person prefers, but "moving knife" and "one cuts, the other choses" methods don't consider that.

One solution would be to dump the cake into a blender and turn it into a smoothie. Each person gets exactly one-third, no problem. I reckon that's fair, and envy-free, and it might even be tasty. But it's not the best solution for anyone because it reduces the value of everyone's share!

What about a divorce or estate settlement that involves several properties, boats and cars, stocks and bonds, computers and a comic book collection? Again, we could "make a smoothie" by selling everything on the open market and converting it all to cash. Cash is easy to divide among any number of people, but no one would be happy and value would be lost.

Math problems can usually be answered, but it takes genius to pose a new question that no one saw as a math problem before. This "fair division" problem is ancient, but the math problem dates back only to the 1940s. See chapter 3 of Hugo Steinhaus' wonderful Mathematical Snapshots (Oxford, 1950+).

The real challenge is not just to find a fair division, but to find a method or algorithm by which each party (no matter how many) will always think that:

• Each person gets their own fair share, eg each of three people dividing a cake should feel they have (at least) one-third of the total as they each value it.

• Each person has no envy of anyone else's share, because they fairly selected their own share that they judged to be worth at least one-third of the total.

• Each person has an equitable share compared to everyone else. You may think you got your one-third fair share, but if the next person thinks they got half of the total value, you might hold resentment that could sour the deal.

• It's an efficient and optimal division, so all agree there's no better settlement that would make everyone happier.

I keep thinking of exceptions as I write this. I have no easy answer to this stumper, but the math challenge has been taken up by Steven Brams and Alan Taylor with their patented "adjusted winner" algorithm. They explain the method in their recent books Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge, 1996) and The Win/Win Solution: Guaranteeing Fair Shares to Everyone (Norton, 2000).