麻豆传媒

SHARING has never been a human strong point, and working out how to divide up goods and land, benefits and hardships, can at times tax even the greatest diplomatic and legal minds. What is really needed to avoid conflict and heartache is a way to divide things between people that is proportional in the sense that everyone is satisfied that they have at least a fair share, and in which no one feels that anyone else ended up with a better deal than they did. Mathematicians call this a 鈥減roportional envy-free allocation protocol鈥�, and the good news is they have found just such a beast. As long as the land, wealth, goods or whatever else it is that everyone wants can be divided up, there is now a way to do it that keeps everyone happy.

The mathematics of sharing came into being in wartime Poland, in the city of Lvov. In 1944, as the Russian army fought to reclaim Poland from the Germans, the mathematician Hugo Steinhaus sought distraction in a puzzle. He knew about the 鈥淚 cut, you choose鈥� protocol for sharing a cake between two people, and he knew why the strategies associated with that protocol lead each player to believe that their share is at least half. The first player divides the cake into pieces which, in his view, are exactly equal. If the second player disagrees, she picks the piece she thinks is the bigger. Neither has any cause for complaint. If the first player is dissatisfied with the outcome, he should have been more careful when making the first cut; if the second player is dissatisfied, she chose the wrong piece. Neither was forced at any stage to make a choice that could be deemed unfair.

Steinhaus wondered whether you could divide a cake between three people 鈥� Arthur, Bertha and Clare, say. Maybe Arthur should cut the cake into three pieces (which he thinks are equal), and then Bertha gets to choose one, followed by Clare. But that doesn鈥檛 work. Bertha and Clare may both think that the same one of Arthur鈥檚 pieces is larger than one-third of the cake, while the other two are smaller. After Bertha chooses that piece, a dissatisfied Clare will be left with one of the smaller ones.

In the end, Steinhaus did come up with the following proportional protocol, a series of seven steps whose outcome was that each person was satisfied that they had received at least one-third of the cake. The statements in brackets are not part of the protocol; they explain why it works and comment on the strategies available to the players to ensure they get their fair share. Each strategy works on the basis that each player acts in his or her own interest, but if anyone doesn鈥檛, they will be the only ones to suffer. Say that a player thinks a piece is fair if its size is one-third (or more), unfair if they think its size is less than one-third. To 鈥減ass鈥� at some step means doing nothing. For convenience we talk about the size of pieces, but what we really mean is their relative value as judged by the player concerned. All judgments are subjective, made by the person performing the action involved.

Three-piece sweet

1. Arthur cuts the cake into three pieces (which he thinks are all fair, hence subjectively equal).

2. Bertha can either pass (if she thinks at least two pieces are fair) or label two pieces (which she thinks are unfair) as 鈥渂ad鈥�.

3. If Bertha passes, then Clare chooses a piece (which she thinks is fair). Then Bertha chooses a piece (which she thinks is fair). Finally Arthur takes the last piece.

4. If Bertha labelled two pieces as 鈥渂ad鈥�, then Clare is offered the same options as Bertha 鈥� pass, or label two pieces 鈥渂ad鈥�. She takes no notice of Bertha鈥檚 labels when choosing her own.

5. If Clare passes, then the players choose pieces in the order Bertha, Clare, Arthur (using the same strategy as in step 3).

6. Otherwise both Bertha and Clare must have labelled two pieces as 鈥渂ad鈥�, so there must be at least one piece that they both consider unfair. Arthur takes that one. (He thinks all pieces are fair, so he can鈥檛 complain.)

7. The other two pieces are re-assembled. (Clare and Bertha both think the result is at least 鈪� of the cake.) Now Clare and Bertha play cut-and-choose to share what鈥檚 left between themselves (thereby getting what they each judge to be a fair share).

One important thing to note about this protocol is that it depends entirely on the players鈥� subjective views of the cake. If the players have different opinions about different parts of the cake 鈥� say Arthur loves icing and hates the rest, while the other two are indifferent about the icing but delighted if they get to split the rest of the cake between the two of them 鈥� the division can look unfair from the outside but still leave all the players happy. In fact each can feel that their portion is worth more than one-third. Steinhaus realised that different opinions about the values of the items to be shared can help the process of division. It is actually more difficult when everyone has similar views.

But the fact that subjective valuations can differ opens up a subtle flaw in Steinhaus鈥� protocol 鈥� it鈥檚 proportional all right, but not necessarily envy-free. Imagine that Arthur cuts the cake into what for him are three equal pieces. Bertha, on the other hand, rates the pieces at ⅙, 鈪� and 陆 and Clare agrees with Bertha. If this happens, Bertha will pass, because two pieces (鈪� and 陆) are both 鈥渇air鈥� in her opinion in that neither is smaller than 鈪�. Clare chooses the piece they both think is worth 陆, and Bertha is left with the one they think is worth 鈪�. Bertha has not got less than a fair share, but she is green with envy since she sees Clare as having more.

Cut and trim

Steinhaus did not worry about the envy-free question: that came later. What concerned him was finding a protocol for proportional allocation among four or more people. This was rapidly found by Stefan Banach and B. Knaster. Suppose there are n players, and call them P1, P2, 鈥� Pn. This time say that a player thinks a piece is fair if it has size 1/n, and unfair if it is smaller. Then the Banach-Knaster protocol is:

1. P1 cuts a (fair) piece C.

2. P2 is offered a choice: pass (if he thinks C is unfair), or trim C (to create a fair piece which we continue to call C). The trimmings are set aside till later.

3. P3 is offered the same choice with the new C; then P4 is offered the same choice; and so on until every player except P1 has had the opportunity to trim C if they wish.

4. If nobody trimmed C, it goes to P1. If it was trimmed, the last player to trim it gets C. (And considers it fair.)

5. The rest of the cake, plus trimmings, is reassembled. The remaining n-1 players (who all consider that at least (n-1)/n of the original cake now remains) repeat the same procedure.

6. This continues until only two players are left. Then they play cut-and-choose.

The Banach-Knaster protocol is simpler than the Steinhaus protocol for n=3, mainly because of its clever use of the idea of trimming. But like Steinhaus鈥檚 protocol, it is not envy-free.

In the early 1960s an envy-free protocol for three players was found independently by mathematicians John Selfridge from Northern Illinois University and John Horton Conway at Cambridge. Their method circulated informally among aficionados of recreational mathematics, and eventually found its way into print in Martin Gardner鈥檚 鈥淢athematical games鈥� column in Scientific American. It goes like this:

1. Arthur cuts the cake into three (fair) pieces.

2. Bertha may either pass (if she thinks two or three pieces are tied for largest), or trim (the largest) piece (to create such a tie). Any trimmings are called 鈥渓eftovers鈥� and set aside.

3. Clare, Bertha and Arthur, in that order, choose a piece (that they think is largest or tied largest). If Bertha did not pass in step 2 then she must choose the trimmed piece unless Clare chose it first. (At this stage, the part of the cake other than the leftovers has been divided into three pieces in an envy-free manner 鈥� a 鈥減artial envy-free allocation鈥�. This takes a little checking, but it鈥檚 true.)
4. If Bertha passed at step 2 there are no leftovers and we are done. Otherwise, either Bertha or Clare took the trimmed piece. Call this person the 鈥渘on-divider鈥�, and the other one of the two the 鈥渄ivider鈥�. The divider divides the leftovers into three pieces (that she considers equal). (Arthur has an 鈥渋rrevocable advantage鈥� over the non-divider, in the following sense. The non-divider received the trimmed piece, and even if she gets all the leftovers, Arthur still thinks she has no more than a fair share, because he thought the original pieces were all fair. So however the leftovers are now divided, Arthur will not envy the non-divider.)

5. The three pieces of leftovers are chosen by the players in the order non-divider, Arthur, divider. (Each chooses the largest piece, or one tied for largest, among those available).

The non-divider chooses from the leftovers first, so has no reason to be envious. Arthur does not envy the non-divider because of his irrevocable advantage; he does not envy the divider because he chooses before she does. The divider can鈥檛 envy anybody since she was the one who divided the leftovers.

But what about an envy-free system for more than three players? It was known from a mathematical theorem 鈥� called the Liapunov convexity theorem 鈥� that for four or more players an envy-free allocation always exists, but nobody could come up with a protocol that would produce such an allocation in a finite number of steps. Enter the science writer Dominic Olivastro, who in 1992 wrote a survey of the subject for the magazine The Sciences. Steven Brams, a political scientist at New York University who has written books on game theory, read the article and was hooked. Brams had long been fascinated by political and economic problems of fair division, such as the partitioning of Germany between the Allies at the end of the Second World War. Here was the same question posed in a purely mathematical form.

Brams started by looking for an envy-free protocol for three players, not realising that Selfridge and Conway had already found one. His method amounted to the first three steps in theirs, a partial envy-free allocation. But instead of their intricate method for dividing the leftovers, Brams just used the same method all over again. That created second-order leftovers, of course, but a third application of the method dealt with them, and so on. It was an infinite protocol 鈥� it didn鈥檛 necessarily stop after a finite number of steps. But it was simple and it worked.

Taylor-made solution

However, when Brams moved on to the case of four people he got stuck, so he got in touch with his friend Alan Taylor, a mathematician at Union College in Schenectady, New York. Taylor thought about the problem while giving a final examination to his students, and solved it. His solution was surprising, as its first step was to divide the cake into five pieces 鈥� even though there were only four players. It was a curious piece of lateral thinking, and Taylor admits that he has no idea where it came from.

Here is Taylor鈥檚 partial envy-free protocol for four players:

1. Arthur cuts the cake into five pieces (which he thinks are equal).

2. Bertha trims up to two pieces, if necessary, to create a three-way tie for largest (in her opinion) and sets the trimmings aside.

3. Clare then trims one piece, if necessary, to create a two-way tie for largest (in her opinion).

4. Dennis chooses first, then Clare, then Bertha, and Arthur takes the last piece. If either Clare or Bertha trimmed a piece, they must choose a trimmed piece if it is available at their turn.

5. The trimmings and leftovers are reassembled. The whole process begins again, and is repeated until the leftovers are too small to worry about.

It is not hard to see that each player thinks their piece is at least tied for largest, so the allocation is envy-free. Moreover, the extension to n players is a relatively simple generalisation, in which the initial division is into 2^(苍鈭�2) + 1 pieces. That is, you start with 9 pieces when there are 5 players, 17 when there are 6, and so on. The number of pieces snowballs as the number of players increases, but for a smallish number of participants it is still manageable.

But even this remarkable solution fails to solve the problem fully. Selfridge and Conway鈥檚 protocol is finite. Brams鈥檚 cavalier approach to leftovers 鈥� repeat indefinitely 鈥� is infinite. So, strictly speaking, Brams and Taylor had not found a genuinely applicable protocol. This didn鈥檛 bother Brams too much. In political science there are always loose ends, and a few tiny bits of cake missing hardly mattered. But it did worry Taylor, the mathematician, and he beavered away for several months, assisted by two colleagues William Zwicker and Fred Galvin, until he found a way to rearrange the sequence of choices so that the method always stopped, with not even a tiny crumb left over.

Even for four players, the resulting protocol is extremely complex. It goes through 20 steps, one of which is a lengthy sequence of trim-and-choose decisions by various players in turn (see 鈥淭he Brams-Taylor protocol for four players鈥�). Unlike the partial allocation originally found by Taylor, it starts more conventionally with a division into four pieces. However, his idea of using many more pieces than players turns up several times, and his original five-piece protocol shows up in its entirety in a lengthy sequence in which leftovers are repeatedly subdivided. Once again, for a large number of players this can mean an unfeasibly large number of cuts. There is another layer of complexity, too: at two stages the protocol involves picking a number that is related to various players鈥� subjective estimates of the relative sizes of pieces. If the players have very different opinions this step can be relatively easy, but if their opinions differ only slightly they can end up cutting the cake into vast numbers of tiny slices. No matter what their preferences are, the number of steps is finite, but it can be very large.

While this is all entertaining stuff, Brams and Taylor see much more in it than just a recreational puzzle. Some of the most intractable human conflicts hinge on similar questions, and any solution must not just be fair, it must be seen to be fair by all involved. How can goods and chattels be divided between divorcing couples? How can company profits and possible improvements to working conditions be divided between unions, managers and shareholders? How should MPs divide their time between Parliament and outside interests? How can media ownership be allocated fairly? How can territory be divided between warring nations?

Brams and Taylor have written a book on the subject, due out in the autumn, entitled Fair Division: From Cake-Cutting to Dispute Resolution, in which they argue that mathematical insights can suggest ways to resolve conflicts. One of their examples is the division of Germany between the Allies 50 years ago. Here there were four players: Britain, France, the US and the Soviet Union. There were many attempts to achieve envy-free division, involving proposals and counterproposals, each trimming the other players鈥� suggested pieces, but they all failed to produce agreement. Finally Berlin was set aside as an extra fifth piece plus trimmings, to be divided later, and the negotiations moved ahead.

Piece in our time

There is another way to interpret this case. Berlin was not really a random leftover, like the pieces in the protocols. In fact, it was worth so much to each of the players that they all wanted to guarantee themselves a part of it. This is more like playing the dividing game with two separate hoards: Berlin and the rest of Germany. The problem could be solved only because it was possible to subdivide Berlin. If there is something that everyone wants and that can鈥檛 be split up 鈥� say a valuable racehorse 鈥� the protocols don鈥檛 work and some other method must be used. The methods pioneered by Steinhaus and perfected by Brams and Taylor have other applications too. Many games exist in a 鈥渕is猫re鈥� version, where the aim is to lose, not win. The mis猫re version of dividing economic goods is that of dividing economic 鈥渂ads鈥� such as unemployment, responsibility for pollution or responsibility for crime. In the home, it is the question of dividing chores, rather than cake.

A key feature of this approach is that players are not allowed to change their minds about the relative values of various bits of cake as the protocol proceeds. Failure to observe this discipline can lead to serious difficulties in, for example, divorce settlements. Once agreement is reached on dividing the house, one partner ups the ante on access to children. By the time that is settled, the question of the house is up in the air again. To get round this problem, Brams and Taylor suggest that the two partners should independently list their evaluations of their mutual assets, and agree in advance to stick to them. Then a mediator can follow a protocol that will lead to a fair division. They can even take the couple through the protocol to explain why it is fair. It may not always work, but it stands a fair chance of being better than the present approach, in which the lawyers get most of the cake and the divorcing couple share the leftover crumbs.

The Brams-Taylor protocol for four players

1. Bertha cuts the cake into four (fair) pieces and hands one to each player.

2. Arthur, Clare and Denis are asked in turn whether they object to this allocation (which they do if they envy another player).

3. If nobody objects, stop.

4. Otherwise, work with the first player to object. Suppose that it is Arthur. Arthur chooses a piece that he envies and calls it A; his original piece is called B. Having chosen A and B, the rest of the cake is reassembled for later consideration.

5. Arthur names a whole number p that is greater than or equal to 10. (This p is chosen to have the following curious property. Suppose that A is sub-divided, in any manner, into p pieces. Then Arthur prefers A to B, even if the 7 smallest pieces are removed. He can achieve this by taking p > 7a/(a-b) where a is his numerical estimate of the value of A, and b his evauation of B.)

6. Bertha divides each of A and B into p pieces (which she thinks are equal).

7. Arthur chooses (the smallest) three pieces of B and names them S1, S2, S3. He also either chooses (the largest) three pieces from A (if he thinks these are all strictly bigger than all the S鈥檚) and trims at most two of them (to the size of the smallest among those three); or he sudivides (the largest) one of the parts of A into three (equal) pieces. Whichever he does, he names these pieces T1, T2, T3.

8. Clare takes the six S鈥檚 and T鈥檚, and either passes (if she thinks there is already a two-way tie for largest), or she trims (the largest) one (to create such a tie).

9. Dennis, Clare, Bertha and Arthur, in that order, choose a piece from the six S鈥檚 and T鈥檚, modified as in step 8 (that they think are largest or tied largest). Clare must take the piece she trimmed, if available. Bertha must choose an S; Arthur must choose a T.
   This gives an envy-free partial allocation, with a lot of leftovers, in which Arthur thinks his piece is stictly larger than Bertha鈥檚 鈥� say by an amount x.

10. Arthur names a whole number q (chosen so that (4L/5)^q < x, where L is Arthur's evaluation of the leftovers). Naming q in advance prevents the next phase from going on forever.

11. Arthur cuts the leftovers into five pieces (a relic of the original idea of Taylor).

12. Bertha trims up to two pieces, if necessary, to create a three-way tie for largest (in her opinion) and sets the trimmings aside.

13. Clare then trims one piece, if necessary, to create a two-way tie for largest (in her opinion).

14. Denis chooses first, then Clare, then Bertha, and Arthur takes the last piece left. If either Clare or Bertha have trimmed a piece, they must choose a trimmed piece if it is available at their turn.

15. Steps 11 to 14 are repeated q-1 further times, each time working with the leftovers from the previous cycle.
    At the end of this cycle of subdivisions, we have an envy-free partial allocation in which Arthur has an irrevocable advantage over Bertha: he thinks his piece is bigger than hers plus all the leftovers. We now create a list of ordered pairs of players, the irrevocable advantage list, by writing down the pair (Arthur, Bertha). This reminds us that Arthur has an irrevocable advantage over Bertha.

16. Bertha cuts the leftovers into 12 (equal) pieces.

17. Each of the other three players declares themselves to be 鈥減ro鈥� if they think all these 12 pieces are the same size, or 鈥渃on鈥� if not.

18. If every pro has an irrevocable advantage over every con (see the list) then we give the 12 pieces to the pros, each recieving an equal number, and stop. (This is why we use 12: it is divisible by 1, 2, 3 and 4).

19. If not, we choose the first (pro-con) pair where there is no such irrevocable advantage, and return to step 4 with the pro player in the role of Arthur, the con in the role of Bertha, and the leftovers in place of the cake.

20. Repeat steps 5 to 18 until (after at most 11 further cycles) every pro-con pair is on the irrevocable advantage list: the cycle then stops at step 18. A full proof is provided in the paper by Brams and Taylor, listed at the end of the feature.