by Jonathan Kujawa
If you have a sibling you are familiar with the problem of dividing up something desirable between selfish people. For some things, like ice cream or money, your only preference is to get as much as you can. If you divide it equally, then at least nobody will be envious of anyone else. My parents used the trick of letting one of us make the divisions, but in the knowledge that the other kids would get first pick. NASA can only dream of the atomic scale cuts made by me and my siblings [1]!
But what happens if the item in question isn't all the same? If it's a cake, a corner piece with roses made of frosting might be more desirable than a piece from the center. In an inheritance, a taxidermy collection and jewelry are hardly the same. Worse, each person might have very different preferences! My brother has a huge sweet tooth. He loves frosting while I'd definitely steer clear of corner pieces. One person's mounted deer head is another person's diamond earrings.
You might guess math has useful things to say about dividing things. But we'll soon see that there are more than a few surprises, too. The first question you might ask is if it is even possible to always divide something into two equal pieces with a single straight cut. It's not too hard to see if you have a single uniform object (say a plain cake), then no matter its shape, a single, well-chosen slice with a Samurai sword will split it into two equal sized pieces.
But what if your cake is a Baked Alaska? Surely you can't make a single cut which equally splits the cake and the ice cream and the chocolate drizzled on top? The Ham Sandwich Theorem is a remarkable result which says that no matter how elaborately intertwined three objects are, it is always possible to make a single cut which separates each of the three into two equal sized pieces!
It probably comes as no surprise, but mathematicians have generalized the Ham Sandwich Theorem to arbitrary dimensions. If you have n objects in n-dimensional space, it is always possible to make a single cut which divides each of the objects into two equal pieces [2]. The theorem also is true in two dimensions (when n=2). You can always split two objects lying in a plane into two equal halves. If you empty both the salt and pepper shakers onto a tabletop, then it is always possible to draw a single straight line across the table and leave exactly half of the salt and exactly half of the pepper lying on each side of the line [3].
What if you have three or more people? To keep things simple, let's say we have three people (let's call them Anne, Boris, and Charlie) and a cake (with frosting and other delights which might make a person prefer one part of the cake over another) [4]. Let's also say we plan to make two straight cuts to divide it into three pieces:
Is it possible to do this in an envy-free way? That is, can we make the two cuts in a way so that the three people will each prefer a different piece of cake? Remarkably, the answer is yes! It is always possible to make two cuts and hand out the pieces without causing jealousy, regardless of their preferences.
How do we know this? Well, we can completely describe where the cuts happen by, from left to right, letting x be the width of the first piece, y the width of the second piece, and z the width of the third piece. The only thing we can say is that x, y, and z are all greater than zero and, if the cake has length one, then x+y+z =1. If you plot the points (x,y,z) in 3-dimensional space, then you get a triangle. Each point on that triangle corresponds to a possible cutting of the cake, and vice versa. The triangle is the "universe" of all possible cake cuttings.
We've seen this trick before. Mathematicians love nothing better than to translate a problem so that possible solutions are nothing but locations in a geometric shape. How does this help? Imagine you've divided the triangle into a bunch of smaller triangles and labeled the corners with A's, B's, and C's in a way so that each of the three outside corners has a different label and each of the smaller triangles has three different labels on its three corners:
Now, at each corner labeled by A, ask Anne if she'd prefer the 1st, 2nd, or 3rd piece (going left to right, as usual). Whatever she says, mark that corner with a 1, 2, or 3 recording her answer. Do the same for the corners labeled B by asking Boris, and the corners labeled C by asking Charlie. Sperner's Lemma guarantees there will be a small triangle with corners who has its three corners labeled by a single 1, a single 2, and a single 3. Since every corner is labeled by a different A, B, and C, as well as a different 1, 2, and 3. This means the three people each prefer a different piece.
But those corners correspond to three different choices of cuttings. If the corners are close enough, it won't matter. If your small triangles are small enough (subatomic will do nicely), Anne, Boris, and Charlie will all prefer different pieces when you cut the cake.
Incidentally, it turns out Sperner's Lemma is equivalent to the seemingly unrelated Brauer Fixed Point Theorem we ran across a few months ago.
This is only the beginning! Replacing the triangle with its higher dimensional analogue, the simplex, a similar argument using Sperner's Lemma tells us it is possible to cut a cake in an envy-free way for a group of people, regardless of how many there are or their preferences. Another variant of this problem shows it is possible to set the rents for the bedrooms of a house in such a way that each of the roommates will have a different preferred bedroom. Francis Su has a paper which nicely explains the details.
A paper from last year shows a really amazing result. It is possible to find an envy-free division of a cake, even if one person's preferences are a secret! That is, if you know the preferences of all but one of the people, it is still possible to cut the cake so no matter which the last person prefers, the pieces can be handed out in an envy-free way. I can't help but think that the members of Congress could use this method when negotiating with the President (whose preferences seem to be a secret, even to himself.).
A paper from this month shows you can also handle the situation when there are too many preferences: if you have a group of n people who each have their own preferences, it is possible to divide a cake into n-1 pieces in such a way that no matter which person is kicked out of the group, you can hand out the pieces of cake to those who remain in an envy-free way.
Another recent paper considers what happens if you have multiple cakes to divide.
Why the flurry of papers on fair division? In the fall the Mathematical Sciences Research Institute had a semester-long program for people who work at the intersection of topology, geometry, and combinatorics. Division problems live at the center of this nexus. Put a bunch of experts together (along with cake at the afternoon teas) and you're bound to get a bunch of exciting new results!
When talking about the mathematics of division, we can't end before talking about the most amazing result of all: the Banach-Tarski paradox. It is the loaves and fishes miracle of mathematics. It is possible to take a solid ball, chop it into a bunch of pieces, and reassemble the pieces into two balls which are the same size as the original! And, of course, you can repeat this many times if you'd like to turn, say, 1 golden ball into 1,000,000 golden balls as large as the original.
Of course, you can't do this in real life. It requires you cut the ball into infinite clouds of points which make sense in the world of mathematics, but can't possibly exist in the real world. Once again reality fails us!
[1] Plus, we had the Mom Oracle who could declare a division fair regardless of all evidence to the contrary.
[2] In higher dimensions, a cut is understood to be done with the higher dimensional analogue of a knife: a hyperplane.
[3] For the Ham Sandwich Theorem an "object" could be a collection of objects. So it is a-okay to consider the salt to be collectively a single object, and the pepper to collectively be the second object.
[4] For some reason, mathematicians love to cut cake!