You want to cut a cake fairly? Take a knife, count the people at the party, cut the slices and hand them out. Even if the pieces are a bit uneven, who cares? What person above the age of 10 would have the nerve to stop a party and complain that his slice wasn't as big as someone else's? Welcome to the field of fair division. It is full of incipient party poopers: mathematicians, economists, political scientists and mediators who care deeply about cake-cutting, down to the frosting and rosettes.
The field doesn't end with cake. It extends to heirs fighting over their inheritance, ex-spouses haggling over property in a divorce, children shirking chores, pirates splitting their loot, warring parties partitioning land and companies merging.
You would think this kind of thing would have been boiled down to a science by now. Splitting booty, after all, is as old as the Bible. In “The Win-Win Solution: Guaranteeing Fair Shares to Everybody,” Steven J. Brams and Alan D. Taylor recount one of the earliest documented cases of the algorithm (or step-by-step method) for splitting known as “I cut, you choose.” Lot and Abraham are arguing over grazing land. Abraham cuts the land into north and south with this proposal: “Let us separate: If you go north, I will go south; and if you go south, I will go north.” And Lot chooses. The problem of fair division is thousands of years old, but the mathematical theory is still young, according to “Cake-Cutting Algorithms: Be Fair if You Can,” a book by Jack Robertson and William Webb that surveys the known methods of cake cutting. These include moving-knife algorithms (somebody shouts “Stop!” when he thinks a knife that's moving across a cake is hovering over his fair share), dirty-work modifications (for dividing up things nobody wants) and divide-and-conquer algorithms.
The formal theory of fair division began in the 1940's, when three Polish mathematicians — Hugo Steinhaus, Stefan Banach and Bronislaw Knaster — came up with a brilliant question: What happens when it's not two people fighting over a cake, but three? This stumped the world for 20 years. “They realized that it got complicated quite quickly,” said Mr. Taylor, the Marie Louise Bailey Professor of Mathematics at Union College. They found a way to cut the cake proportionally, so that every person would feel that he or she got at least one-third of the cake. But they couldn't insure that one of the cake-eaters would not want to swap his or her piece of cake for someone else's.
This was the problem: Say Tom, Dick and Ann set out to cut a cake into thirds. Tom might cut a slice that he thinks is at least one-third of the cake and then watch as the rest of the cake is split so that Dick gets a bigger piece than his and Ann a smaller one. Tom might feel that he got his proportional share but still envy Dick. The slice would be, in the lingo of fair division, “proportional” but not “envy-free.” It was not until 1960 that two mathematicians, John H. Conway and John L. Selfridge, found a way to guarantee envy-freeness (and proportionality) for three people. (All envy-free solutions are proportional.) Their method also guaranteed crumbs.
Tom cuts the cake into what he thinks are three equal slices. Then Dick sizes up the situation. If he doesn't think the slices are even, he trims the largest slice until he thinks it's same size as the next largest slice. Then the slices are claimed in this order: first Ann, then Dick (who must take the piece he trimmed if Ann didn't take it), then Tom. The problem is what to do with the trimmings. Should they be divided in the same manner? And when do trimmings become worthless crumbs? A variant of the trimming procedure was used after World War II, according to “The Win-Win Solution.” When the Allies partitioned Germany into zones, Berlin was viewed as too valuable a piece to hand over to the Soviet Union even though it was in the Soviet zone. Thus Berlin became the trimmings, leftovers to be further divided.
In the 1990's, Mr. Taylor and Mr. Brams came up with an envy-free way to divide cake among — yes — four people. And if you can cut a cake for four people in an envy-free way, Mr. Taylor says, you can do it for millions. When Mr. Taylor was asked if he could explain it, he said, “Whoa! Not easily.”
Basically it involves cutting extra slices. As the number of cake-eaters increases, the number of slices you have to cut increases exponentially. For four cake-eaters, cut five slices; for five eaters, nine slices; for six, 17 slices; for 22 eaters, more than a million. The trimmings and additional slices are distributed later in an even more complicated way. For all the muss, these algorithms don't always produce satisfied customers. Say one person likes frosting and cake, but another person finds frosting nauseating. If a cake is divided with equal parts frosting and cake for all, the frosting-hater will see that the person who likes both cake and frosting is happier. The frosting-hater doesn't want the other person's slice; he wants that person's happiness with his slice.
That is, there is more to a truly great cut than envy-freeness and proportionality. There's the gloating quotient. If you really want to be fair, you have to insure that no one feels happier with his slice than anyone else. (This is called an “equitable” distribution.) And if you want to dole out the maximum amount of happiness, you should also make sure no other division would make things better for one party without making it worse for another. (This is called an “efficient” division.)
Oddly enough, the more people disagree about what's tasty in a cake, the easier it is to make everyone happy. If one person adores frosting but not cake and the other loves cake but not frosting, you can make both happy by giving one frosting, the other the cake.
The question is how to produce wonderful cuts where some tastes overlap and others don't. The first step is to stop talking about cake. Instead of looking at a single item, like a cake, look at piles of things, like property in a divorce.
In “The Win-Win Solution,” Mr. Brams and Mr. Taylor describe their new algorithm to help two parties — countries, divorces, siblings, companies — divide in a way that's envy-free (and thus proportional), equitable and efficient. It is called adjusted winner, or A.W., and the authors have already patented it, just to avoid getting into a little property dispute of their own. (As far as the authors know, this is the first patent for a method of resolving disputes.)
This is how A.W. works. Two parties list all the items and issues to be divided. Each one gets 100 points to spend on the things listed, spending the most points on those things the player values most. Each player wins (at least temporarily) the items that he has placed more points on than his opponent. Then the adjustments begin. Both players add up the number of points they have spent for the things they have got. If one party has more, they start transferring items back and forth (and sometimes dividing them or cashing them in for money) until their point totals are identical.
“Generally, it pays to be honest about what your valuations are” when using this algorithm, said Mr. Brams, a professor of politics at New York University. And of course it also pays to keep your valuations a secret from your opponent. Otherwise he could spite you by, say, putting just one more point on something he knows you want.
“The more different the preferences, the more both gain,” Mr. Brams says. Applying the A.W. method to Donald and Ivana Trump's divorce, Mr. Brams and Mr. Taylor calculated that both would have won nearly 75 percent of what they wanted because their preferences were so different. She wanted the Connecticut estate and the Trump Plaza apartment. He wanted the Palm Beach mansion and the Trump Tower triplex. If A.W. had been applied to the Camp David peace talks, Egypt and Israel would have each gotten about 65 percent of what they wanted.
That sounds wonderful, but fittingly for a field that deals with disputes, there is some dispute about whether A.W. really promotes harmony. Roger Fisher, who wrote “Getting to Yes: Negotiating Agreement Without Giving In” with William Ury, is troubled. “A point system,” he said, “takes the articles in conflict as fixed, and that's not necessarily good for any relationship.” In mediation, he says, “emotional needs are often more important than material wants.”
For example, in a diplomatic dispute, perhaps one country wants an apology rather than land in a diplomatic dispute. In an estate settlement, maybe one person wants the summer house only for July and another person wants mother's dress only for her wedding. Mr. Taylor said that it doesn't matter what is being divided up — apologies, sovereignty or wearing mother's dress for a day — as long as everything is put on the list.
Mr. Fisher still has doubts. He said that a point system can help heirs divide antiques but doesn't produce creative solutions for complicated political conflicts. “Apologizing and showing respect, tolerance, understanding and openness to the ideas of others,” he said, “are not units to which partisans can easily assign mathematical points.” The adversarial and secretive nature of the method can work against peace too. In negotiation, it's better to ''play with the cards face up,” to make all your wants clearly known, he said. “The biggest concern is to eliminate the idea that your partner in negotiation is your enemy.” “Most of the world is not made better by dividing things,” Mr. Fisher says. All the secretiveness and jockeying is okay if the parties are going to “live on different planets,” he says. But it's no way to produce harmony and end war. “God bless them if they can find a mathematical solution for that.” Cake, anyone?
Read More