Steven Brams keeps a low profile for the fairest man who ever lived. A political scientist at New York University in downtown Manhattan, he seethes with ideas for improving the world, schemes that unfold in a dozen books. Yet somehow the powers that be have managed to ignore him. Alan Taylor complements Brams. Less distracted by current events, this Union College mathematician likes to think about different kinds of infinities late into the night, occasionally losing track of time until the sky starts to brighten. A self-effacing New Englander like Brams, Taylor has an equal claim to being the fairest of them all. Working together over the past two years, Brams and Taylor have figured out an equitable way to divide the world’s goods--tangible or not--that’s mathematically guaranteed to do everyone justice. That makes them fairer even than King Solomon.
After all, even Solomonic justice had its limits. In the king’s most celebrated case, two harlots brought him a baby, each claiming to be its mother. According to the Bible (1 Kings 3:16-28), Solomon proposed cutting the baby in two, giving half to each woman. As he sent for a sword, one woman agreed that halves would be a fair division; the other withdrew her claim. She, of course, was the true mother, and Solomon gave her the child.
Solomon’s bluff was magnificent, but the problem he faced was relatively simple: one child claimed by two women. The world that Brams and Taylor and the rest of us live in produces far more complicated brain twisters. If five children, say, inherit their parents’ estate, including property, cash, heirlooms, and art; if each heir wants some of those items but has no interest in others; and if, unfortunately, different heirs want some of the same items, how should a judge divide the estate? Should each heir get a fifth of each item? Might a less obvious solution be more satisfying all around? For all his wisdom, Solomon had no formal method for deciding issues of fairness. Brams and Taylor do. With their modest but infinitely adaptable procedure, they can crank out a mutually satisfying, fair division with any number of items, any number of claims. Ergo they are the fairest ever.
Brams and Taylor published their procedure in the January 1995 American Mathematical Monthly. Their new book, to be published later this year, explains everything a layperson might need to know about fair division. It illustrates various ways to apply this new technique (and several others) to divorce settlements, inheritance squabbles, treaty negotiations, wage disputes, and many other knotty problems, including the fair distribution of bads, such as taxes and household chores. Even lawyers should love the book. Brams has talked to a few, and he actually detects enthusiasm among them for efficient conflict resolution rather than protracted litigation. In theory the world should soon be beating a path to his door. But of course life isn’t always fair in that way either.
The problem of fair division is older than Solomon--older, in fact, than recorded history. Formally stated, it goes like this. How should you divide a bundle of goods among claimants who place different values on the items involved? Is it possible for all the parties to feel they’ve taken the choicest cut? The answer, say Brams and Taylor, is yes, always.
How did they come up with such a wondrous procedure? We got lucky, Brams confesses. Mathematicians and economists had already wrestled the problem of fair division into a formal, logical structure. For decades they had racked their brains to find elegant solutions. What stopped them, says Taylor, was their own cleverness. It took an outsider like Brams to stumble into the field, suggest a simpleminded procedure--but one that required infinitely many steps--and stand back as Taylor then showed that the idea could work.
In its modern mathematical form, the problem of fair division dates from the Second World War; it originated in Poland, a country with considerable experience of unfair division. During the war, the Polish city of Lvov became a doormat for advancing and retreating armies. The Russians seized it in 1939, the Germans swept through in 1941 on their way toward Stalingrad, and in 1944 the Russians returned. All through those terrible years, the odds of survival were poor. Yet it was precisely then, in Lvov, that the Polish mathematician Hugo Steinhaus took a gaming approach to the problem of fairness.
Game theorists analyze the possible strategies that players might follow in various conflicts--wars, elections, economic rivalries--as well as in games played just for fun. Since a player’s best strategy depends on the strategies of other players, and since players constantly react to one another and change their plans, theorists find it difficult to nail down winning strategies, even for the simplest games.
The world was falling apart, and Steinhaus invented a new game. What else could he do? Many of his colleagues had fled the country during the war; those who remained were being arrested, shipped off to concentration camps, or simply shot. More than 25 Polish research mathematicians perished. Steinhaus, meanwhile, concentrated his thoughts on cake--cake as a symbol of all the goods we lust after. Is there a way to divide a cake, he wondered, so that everyone gets a demonstrably fair share?
To give the problem structure, Steinhaus made it a game. There could be any number of players. They would agree on rules for dividing the cake, and then everyone would follow those rules. The players would need a procedure, for example, to specify how to cut the cake. One player might make the first cut, another player the second cut, and so on. The players would also need a procedure for distributing the pieces. In the end, each player must get what he or she perceives as a fair share.
Perhaps Steinhaus had seen hungry families quarreling over pitifully small rations of food; perhaps he was haunted by the many partitions of Poland. Is there a way to divide central Europe, he might just as well have asked, that would end the disputes there, the perpetual formation and dissolution of nations, once and for all? Steinhaus did use examples involving land to illustrate the problem he was trying to solve. But Taylor thinks he cared most about cakes--abstract, mathematical cakes.
Whatever his true motivation, Steinhaus began with a widely accepted notion of fairness: If two persons divide a cake, each must get at least 1/2; if three persons divide, each must get at least 1/3; if n persons divide, each must get at least 1/n. Everyone gets at least 1/n because parts often add up to more than the whole, subjectively speaking.
The simplest way to see how this works is to play the game with two players. The fair procedure, probably known long before Solomon, is I cut, you choose. I can cut the cake any way I like, but I will probably cut it into two equal pieces, as far as I can tell. (If I don’t make them equal, you might take the larger piece.) After I cut, you then choose whichever piece appeals more to you--maybe you like frosting or nuts, and one piece has more. The piece you reject looks like half to me; the piece you choose may look like better than half to you. The two halves thus add up to more than the whole, not in size but in their subjective values to each of us.
This strange truth makes it possible for everyone to win. To reach a satisfying agreement, no one need impose standards on anyone else. In fact, fairness gets easier the more the players’ values clash. If I crave only frosting and you like everything but, and if we each know the other’s preferences, one of us can skew the cutting so we both get everything we want. All the frosting goes to one plate, everything else to the other. We each get 100 percent of our cake, the rest being worthless garbage as far as we’re concerned. Steinhaus was the first, says Taylor, to say that people’s having different values makes the fair-division problem easier, not harder, to solve.
So much for simple fairness. The more interesting question was this: Can each person receive the biggest piece, according to his own judgment? For a solution to stick, each player must believe he is getting not only a fair share but the best share. That way no one envies anyone else’s share. With three players, for instance, a fair share is at least 10/30. Because our values can subjectively enlarge each share, each of us might perceive our share as 11/30. But envy can still spoil our game if one of us thinks another has more than 11/30. The three of us might still come to blows, break furniture, and burn down the house.
More specifically, here’s how envy can wreck the game. The same preferences that make you value your piece of cake at 11/30 can lead you to value a neighbor’s piece at 12/30. Your neighbor may not have cheated to come out so well-off. Perhaps the first player, a tasteless dolt in your opinion, started by cutting the cake into thirds with no regard for the finer distinctions between frosting and nuts. Then your neighbor, playing by the rules, chose a piece before you did. That gives you grounds for envying the lucky glutton, even while you sneer at the cockeyed schnook who gleefully made off with the third and last piece, which looks to you like 7/30. So the paradox unfolds: we all believe we got a fair share, yet some of us envy another’s share--causing bitterness and endless strife.
In fact, an envy-free division exists in every case, for any number of players. Steinhaus proved this during the war. Through an indirect proof that is too complicated to explain here, he showed that if envy-free allocations failed to exist, then a different theorem would be false--when in fact it’s known to be true. Therefore envy-free solutions exist. There was only one catch: Steinhaus didn’t have a procedure that would actually yield such happy results. Knowing they existed was like knowing we could, in theory, reach the stars. It told us the goal was possible, but not how to get there.
And for half a century we didn’t get much closer to freedom from envy. Then Dominic Olivastro, a columnist for The Sciences, decided to review the state of the cake-cutting art for the magazine’s March/April 1992 issue. Mathematicians, he reported, had found envy-free solutions for only the easiest cases; no one had discovered a procedure that worked for any number of players. Olivastro issued a challenge. Readers are welcome to try their hand, but be warned: some of the world’s best minds have yet to find a solution.
When Brams read Olivastro’s article, he couldn’t put it down. I’ve always been interested in better ways to do things, he says. That interest gradually pulled him from his birthplace of Concord, New Hampshire, toward bigger centers of power. As an undergraduate at MIT, Brams studied math while majoring in political science. After completing a Ph.D. at Northwestern, he went to Washington, D.C., to work at the Institute for Defense Analyses, a nonprofit research organization. He was hired to study how decisions were made at one of the IDA’s biggest customers, the Department of Defense. This was in 1965, just as the Vietnam War began to escalate--which may explain why the president of the IDA suddenly canceled Brams’s study. The Department of Defense didn’t want to know about its problems, Brams says.
He quickly moved on to more fruitful employment as a professor, first at Syracuse and then beginning in 1969 at New York University. Although he was already familiar with the cake-cutting game, it wasn’t until he read Olivastro’s article that he realized cake cutting’s value as a paradigm of the kinds of problems he wanted to solve, from land division in Bosnia to the allocation of water rights in the Middle East to the parceling out of marital property in a divorce. Land, water, property--most things could be divided like cake.
Olivastro’s article gave Brams the solution for two players: I cut, you choose. Might that procedure accommodate three? Expand it to I cut, you choose, he chooses. I start by cutting the cake into three equal- looking pieces. Then you choose the piece that appeals most to you. But what if you and he have similar values? You’ll take the piece he likes best, leaving a lesser share for him. He loses. Envy wins. House burns to the ground. Try again.
Brams soon discovered a fair way to divide at least part of the cake among three players. He called them Bob, Carol, and Ted. First Bob cuts the cake into three pieces that seem equal to him. Carol then gets a chance to correct what she perceives as a defect in Bob’s vision. If she views one piece as larger than the others, she trims it to look equal to the piece she sees as second largest and sets the trimmings aside. Three pieces remain on the table: the piece Carol trimmed, and two untouched pieces cut by Bob. Ted now chooses a piece. Carol chooses next, with the proviso that she must take the piece she trimmed if Ted didn’t choose it. Finally, Bob gets the last piece.
In short, it goes like this: I cut, you trim; he chooses, you choose, I choose. Following these rules, everyone gets the largest piece, in his or her own opinion. Ted, choosing first, can’t lose. He takes the piece he likes best. Carol also can’t lose, because in her eyes she created a tie for the largest piece. If Ted chooses one, she gets the other. Finally Bob, who cut three equal pieces in his own estimation, can’t lose either. He gets one of his two original, untouched pieces--both larger, in his view, than the piece Carol trimmed, and both equal.
Brams had found an envy-free way of dividing things. Little did he know that around 1960 two mathematicians had already discovered this procedure--and more. (Olivastro hadn’t mentioned their work.) Brams’s method, you see, distributed only part of the cake--a large part, of course, but not the trimmings that Carol set aside. John Selfridge and John Conway, working independently at Northern Illinois and Cambridge universities, proceeded as Brams did and then parceled out the trimmings in an additional clever round, involving a different order of cutting and choosing. For those who want to know, here is the solution, without further explanation. Say Ted chose the piece Carol trimmed in the first round. Then Carol cuts the trimmings into three equal-looking parts in the second round, and the players choose in the following order: Ted, Bob, Carol. If Carol got the piece she trimmed in the first round, Ted cuts the trimmings in the second round, and the choosing order is Carol, Bob, Ted.
Confusing, you say? Brams thinks so, too. Fortunately, he says, I wasn’t burdened by this cleverness. After he divided part of the cake among three players, he thought, Why not just repeat the same procedure? The three players could divide the trimmings the same way they had divided the original cake, and there would be trimmings left over from the trimmings. Those leftovers could also be divided the same way, leaving yet smaller trimmings, and so on, until the remaining crumbs became so small that no one wanted to bother with them.
This idea of a potentially infinite procedure was new. Call it luck, call it pluck--call it a clunky breakthrough. Brams didn’t exactly solve the problem even for three people. He just settled for less than perfect. In real life, no one would insist on infinitely many rounds of division; it would take only a finite number to reduce the trimmings to an indivisible penny. Anyway, three-way divisions would probably end after only one round. Lawyers, real estate agents, or other consultants would pounce on the trimmings to cover their fees. The players would be lucky if they didn’t have to pony up from their own shares. Therefore trimmings don’t matter--QED.
Brams was excited. Could this be the path to world harmony? At the very least, it meant fewer mangled cakes. He went on to four players. All he needed was one round of cutting, trimming, and choosing that divided part of the cake without envy. This could then be repeated over and over again, until the greediest player’s bloodshot eyes could no longer make out the last crumb.
Unfortunately, when Brams moved on to four players, he found that his three-way strategy fell apart, just as the two-player game does when you naively expand it to three. No matter how he tried, Brams couldn’t divide even part of the cake in an envy-free way among four players. His intuition still told him that trimming the trimmings was the best way to go, but now he needed help even to get to the first round of trimmings.
Taylor got the call near the end of the winter term in 1992. Could the solution be an infinite procedure? Brams asked. It was a good question. In mathematics, Taylor says, very often the key part of solving a problem is asking the right question. Brams was asking the right question, but Taylor didn’t yet know that. First he needed to know the problem. He had never heard of the cake-cutting game. Brams hastily explained the gist of it and mentioned how some of the world’s best minds, according to Olivastro, had failed to solve it. This convinced Taylor that his chances of success were practically nil.
Taylor is a professor of mathematics at Union College in Schenectady, New York--a teeming metropolis, in his estimation. Like Brams, Taylor had once gravitated toward bigger burgs. Unlike Brams, he hadn’t particularly enjoyed the journey. In the 1970s, when he left tiny Orono, Maine, to do graduate work at Dartmouth, Taylor found the hustle and bustle of Hanover, New Hampshire, much too oppressive. He fled to a trailer by a lake, ten miles outside town. He worked quietly there on set theory, earning a Ph.D. in 1975, and then joined the faculty at Union College. In 1986 he attended a workshop for small-college faculty members, given by Brams, to learn how mathematics could clarify social problems. Never mind Taylor’s aversion to the crush of actual people. Society, as a grand abstraction, looked to him like a fascinating subject. Over the next few years, Brams and Taylor collaborated on several workshops.
Taylor pondered the cake-cutting challenge while giving a final exam in Math 57: Game Theory for the Humanities and Social Sciences. He was standing at a lectern. As his students fidgeted and sighed, Taylor’s mind drifted off to work. Before the exam was over, he had extended Brams’s method well beyond three players--all the way to infinity. Taylor had discovered the first general procedure for envy-free cake slicing. All he had needed to do was add one idea to Brams’s cut-till-you’re-exhausted procedure for three. To this day, he doesn’t know how he thought of it.
His breakthrough idea was to start the game by cutting an extra piece of cake. This was counterintuitive. With two players, the first player cuts the cake in half. With three players, the first player cuts the cake into thirds. With four, everyone thought, the first player should cut the cake into fourths.
Taylor was new to the game; he didn’t know what everyone thought. With four players, his scheme unfolded like this. First Bob divides the cake into five equal-looking pieces. He passes them to Carol, who trims two at most to create a three-way tie for largest in her eyes. She sets the trimmings aside and gives the five pieces to Ted, who trims one at most to create a two-way tie for largest in his eyes. Alice, the fourth player, now chooses the piece she likes best. Choosing proceeds in the reverse order from cutting, with the proviso that anyone who trimmed one or more pieces must take one of them if any are still available when it’s his or her turn to choose.
This procedure naively expands Brams’s winning procedure for three, with an extra piece of cake thrown in. Without the extra piece, it fails. The extra piece assures that no player gets second-best. If someone takes a piece you like before it’s your turn to choose, an equivalent piece or better always remains on the table. Work out the details if you want, or take Taylor’s word that everyone wins.
Like Brams’s procedure for three players, Taylor’s new procedure for four distributed only part of the cake. It left not only trimmings but a fifth, unchosen piece of cake. Fortunately, Brams had told Taylor not to worry about any remainders. So Taylor continued expanding the game, just as naively, from four players to five and finally to n, which means an arbitrary number of players. With each additional player, he tossed in extra pieces of cake. Everything came up envy-free. Taylor was walking on air. Angels were humming in the clouds. Bob, however, was getting fatigued.
According to a formula Brams and Taylor developed, Bob must cut the cake into at least 2n-2 + 1 pieces at the start. That comes to 5 pieces for four players, 9 pieces for five players, 17 pieces for six, and so on-- an exponential increase. Bob has to cut all these extra pieces to make sure that, when he finally gets to choose at the very end, there will be a piece left that hasn’t been either trimmed or chosen by one of the many other players. With 22 players, he’s cutting over a million pieces of cake; with 184 players--as many as there are nations in the UN--he might as well be dividing a beach sand grain by sand grain. (Maybe that’s why the UN needs the Security Council, a smaller body of fifteen nations by which most deals are actually cut.)
Still, Taylor was happy with his expansion to n players; it worked in principle. But Brams’s technique for dealing with remainders--the really infinite hacking--didn’t please him. Mathematicians don’t accept infinite procedures as true solutions. So Taylor went on to prove that a finite solution exists for any number of players. Starting with more pieces of cake than players, he found clever ways to reshuffle the order of cutting and choosing after the first round. Around 1960, Selfridge and Conway showed how to do this for three players. In their clever second round, the trimmings disappear. More players, Taylor saw, would require more rounds, but the number of rounds could always be finite.
Taylor’s ingenious, finite solution satisfied the mathematicians, and the infinite procedure first suggested by Brams--conceptually simpler and more practical--satisfied everyone else. And that was the end of a very old problem, older than Solomon, older than history. Brams and Taylor had solved it more or less on a dare, almost by accident.
Right away they wrote a letter to Dominic Olivastro at The Sciences. The letter arrived barely a month after Olivastro had issued his best minds challenge. I was shocked, Olivastro wrote later. He revealed to his readers in July the gist of what may well be a constructive proof of the problem. I say ‘may’ only because the paper has not yet been officially refereed.
Two hours had been all Taylor needed to expand the game from three to an arbitrary number of players, but several months passed before he thrashed out the details on paper and referees for American Mathematical Monthly accepted the proof. The problem of fair, envy-free division was officially solved. We were excited, says Brams, because it was a significant mathematical result. By then, however, the applications seemed even more exciting.
All his life, Brams has tinkered with rules for the games we play. He feels certain his schemes would make everything work better, not by his own standards but according to the wishes of frustrated players themselves. Several other games he and Taylor had worked on were not unlike cake cutting. Auctions and elections, in particular, distribute goods-- economic goods, or political goods such as proportional representation, or even symbolic and psychological goods. So Brams and Taylor decided to unify those old games with their new approach: the art of cake cutting applied to real life. In a few weeks they reformulated their earlier work. It’s all in the book that’s due out this fall, titled Fair Division: From Cake-Cutting to Dispute Resolution.
Throughout the book, Brams and Taylor illustrate their technique with real problems. On one page, for instance, they consider how a country might be divided, using the example of Germany after World War II. Great Britain, France, the Soviet Union, and the United States had decided to eliminate Germany as a superpower. Each would take a piece. Just as in four-player cake cutting, the Allies found it difficult to reach a satisfying, envy-free solution. Players circulated proposals for dividing Germany into four zones, and rival players offered counterproposals, with trimmings shaved off here, crumbs added there. But starting with four zones didn’t work. In the end, say Brams and Taylor, putting aside Berlin helped the Allies reach an agreement; it became a sort of fifth piece plus trimmings that they divided later.
Intuitively, it seems, movers and shakers sometimes grope their way toward mathematically respectable solutions. The problem is that, without a fair procedure, the agreement may not satisfy all players. Even now, with a fair procedure available in theory, players may still reject the game, preferring instead to gamble viciously for higher stakes. After all, anyone can do better than 1/n by eliminating an opponent or two--as seems to be happening in Bosnia.
With players who are willing, however, almost any obstacle can be overcome. In many situations, for example, the items will not come apart like a cake. A house is often the most valuable part of an estate, and everything else lumped together may not seem as valuable to any of the heirs. You can’t chop a house into pieces. You might have to sell the house, Brams admits, and divide the proceeds. Almost always, though, Brams and Taylor find comparatively satisfying ways to divide things. Often, solutions already existed for two or three players.
The dirty-work problem was one example. Household chores count as bads rather than goods, so each player wants the smallest share. As with goods, an envy-free method already existed for bads, but it worked only for two or three players. In Brams and Taylor’s version of the bad game, players don’t just trim shares; they add on as well. In a four-person cake-baking commune, for instance, Bob divides most of the chores among five lists he views as equally odious but leaves some chores on a surplus pile. Carol thinks the work on one of the lists is far too light, so she takes morning dishes from the surplus and adds it to the first list’s mopping and taking out trash--thereby creating a three-way tie, in her view, for lightest chore list. The game’s logic works the same as with goods, and everyone wins by getting what seems to him or her the easiest workload.
Somehow even two-player games, in theory the easiest, often get botched in real life, ending with one or both players feeling wronged. Divorces seem especially prone to unhappy outcomes. Spite and revenge spoil this game as badly as envy does: Bob uses the knife as a scraper, shoving all the frosting to one side of the cake, and then deliberately cuts unequal halves even in his own eyes--all the property, assets, and possessions in one share, say, with child custody in the other, but no alimony and little child support. Carol deliberately chooses the share she would rather not take, just to spite Bob, because she knows he likes frosting so much he would practically die for it, and the smaller piece has nearly all the frosting. As Taylor says, The rules allow you to behave stupidly--to hurt yourself as well as the other player.
In their forthcoming book, Brams and Taylor demonstrate how a new procedure can negotiate even these kinds of emotional minefields to produce two winners. A court settlement, on the other hand, would probably divide everything 50-50 in the eyes of a judge or a jury, producing two losers as likely as not. In Brams and Taylor’s procedure, both players in a highly emotional contest such as a divorce or a labor-management dispute get 100 points to distribute, like poker chips, among all the disputed items. If Carol really wants custody, she might put 90 points on that and distribute 10 on everything else. She and Bob rank the goods in secret. A mediator then uses those lists to figure out who gets what, according to their own stated preferences. This method of declaring one’s values, carried out in secret, doesn’t lend itself to posturing, bluffs, and threats. Instead, if done in the manner Brams and Taylor explain, it allocates the items in a way that maximizes satisfaction for all parties--with mathematical certainty.
That emotions get tangled in mathematics doesn’t discourage Brams. My next challenge, he says, will be to come up with a rational theory of emotions. He’s taken care of envy, but envy is just one emotion and just one of the seven deadly sins. Brams wants to bag them all. Many social theorists prefer not to deal with emotional thinking. Their logic is cold, not hot. If you want to do well in their games, you shouldn’t get emotional. Brams doesn’t see how such games can apply to real life. It’s not irrational, he insists, to have emotions.
Taylor is glad that envy-free math has practical uses, but that’s not the reason he plays the game. I’m interested in how it raises mathematical questions, he says. His work on the proof brought new questions to mind. Some deep mathematics, he says, separates the three- player game from the four-player game. Suddenly, with four, the complexity explodes. As everyone knows, two’s company and three’s a crowd. Something worse happens between three and four, and no one completely understands it. For once, Taylor is fascinated by small numbers. He would like to count past three and really know what is going on.
