 |
 |
|
||
 |
||||
|
||||
|
Your Half's Bigger Than My Half! Scientific American, 1998 A big man and a small man were sitting in the
restaurant car of a train, and both ordered fish. When the waiter
brought the food, there was one big fish and one small one. The big
man, served first, promptly took the big fish; the small man
complained that this was extremely impolite.
The simplest case involves just two people, who wish to share a cake so that each is satisfied that they have a fair share. 'Fair' here means 'more than half by my valuation', and the recipients may disagree on the value of any given bit of cake. For example, Alice may like cherries while Bob prefers icing. One of the more curious insights that has emerged from the theory of cake cutting is that it is easier to divide the cake when the recipients disagree on what parts of it are worth. You can see this makes sense here, because we can give Bob the icing and Alice the cherries and we're well on the way to satisfying both of them. If they both wanted icing, the problem would be harder. Not that it's terribly hard when there are two players. The solution 'Alice cuts, Bob chooses' has been traced back 2800 years! Both players find this fair in the sense that they have no right to complain about the end result. If Alice dislikes the piece that Bob leaves, it's her own fault for not being more careful to make equal cuts (according to her valuation). If Bob doesn't like his piece, he made the wrong choice. The whole area began to get interesting when people looked at what happens with three players. Robertson and Webb approach this variant by analysing a plausible but incorrect answer, which goes like this. Tom, Dick and Harry want to divide a cake so that each is satisfied he's got at least one third of it, according to his own private valuation. In all such matters, by the way, the cake is assumed to be infinitely divisible, although much of the theory works if the cake has valuable 'atoms' — single points to which at least one recipient attaches a non-zero value. For simplicity, though, I'll assume there are no atoms. OK, what about this algorithm?
It's clear that Harry will be satisfied, because he has first pick. Tom is also satisfied, for slightly more complex reasons. If Harry picks X, then Tom can pick whichever of Y and Z he considers more valuable (or either if they are equal in his eyes). Since he thinks they are worth 2/3 in total, he must think at least one of them is worth 1/3. On the other hand, if Harry chooses Y or Z, then Tom can choose X. However, Dick may not be so happy with the result. If he disagrees with Tom about the first cut, then he might think W is worth less than 1/3, meaning that the only piece that will satisfy him is X. But Harry could choose Y, say, and Tom X, so Dick has to take Z — which he doesn't want. The first solution to fair three-person division was given in 1944 by Hugo Steinhaus, one of a group of Polish mathematicians who met regularly in a café in Lvov. His method involves a technique called 'trimming'.
That's one answer — I'll leave it to you to verify the logic. Basically, anyone who isn't satisfied with what he gets must have made a bad choice, or a poorly judged cut, at an earlier stage, in which case he has only himself to blame. In 1961 Leonard Dubins and Edwin Spanier proposed a rather different solution involving a moving knife. Sit the cake on a table, and arrange for a knife to move smoothly and gradually across it, starting completely to its left. At a given instant, let L be the part to the left of the knife. Tom, Dick, and Harry are all told to shout 'Stop!' as soon as the value of L, in their opinion, becomes 1/3. The first to shout gets L, and the other two divide the rest either by 'I cut you choose' or by moving the knife again and shouting as soon as the perceived value reaches 1/2. (What should they do if two players shout simultaneously? Think about it.) The great feature of this method is that it extends readily to n recipients. Move the knife across, and tell everyone to shout as soon as L reaches 1/n in their estimation. The first person to shout gets L, and the remaining n-1 players repeat the process on the remaining cake, only of course they now shout when the perceived value reaches 1/(n-1)... and so on. I must say that I'm never terribly happy with moving-knife algorithms — I think because of the time-lag involved in the players' reactions. The best way to get round this quibble is to move the knife slowly. Very slowly. Let's call the first kind of answer a 'fixed knife' algorithm, the second a 'moving knife' algorithm. There is a fixed knife algorithm for three-person division that also extends readily to n people. Tom is sitting on his own, staring at 'his' cake, when Dick shows up and asks for a share. So Tom cuts what he thinks are halves and Dick chooses a piece. Before they can eat anything, Harry arrives and demands a fair share too. Tom and Dick independently cut their pieces into three parts, each of which they consider to be of equal value. Harry chooses one of Tom's pieces and one of Dick's. It's not hard to see why this 'successive pairs' algorithm works, and the extension to any number of people is relatively straightforward. The trimming method can also be extended to n people by offering everyone round the table a chance to trim a piece if they are willing to accept the result, and insisting that they do if nobody else wants to trim it further. When the number of people is large, the successive pairs algorithm require a very large number of cuts. Which method requires the fewest cuts? The moving knife method uses n-1 cuts to get its n pieces, and that's as small as you can get. But the fixed knife methods don't succumb as readily. With n people, a generalisation of the trimming algorithm uses (n^2-n)/2 cuts. The successive pairs algorithm uses n!-1, where n! = n(n-1)(n-2) \dots 3 \cdot 2 \cdot 1 is the factorial. This is bigger than the number of cuts used in the trimming algorithm (except when n = 2). However, trimming is not the best method. The more efficient 'divide and conquer' algorithm works roughly like this: try to divide the cake using one cut so that roughly half the people would be happy to have a fair share of one piece, while the rest would be happy to have a fair share of the other piece. Then repeat the same idea on the two separate subcakes. The number of cuts needed here is about n \log_2{n}. The exact formula is n^k - 2^k + 1 where k is the unique integer such that 2^k-1 < n \leq 2^k. It is conjectured that this is about as good as you can get. These ideas could eventually go beyond mere recreation. There are many situations in real life where it is important to divide assets in a manner that seems fair to all recipients. Negotiations over territory and commercial interests are examples. In principle the kind of method that solves the cake-cutting problem can be applied to such situations. Indeed when for administrative purposes Germany was divided among The Allies (USA, Britain, France) and Russia, the first attempt created leftovers (Berlin) and then Berlin had to be divided as a separate step, so negotiators intuitively apply similar methods. Something rather similar is causing problems in Israeli-Palestinian relations right now, with Jerusalem as the main 'leftovers' and the West Bank as another bone of contention. Might the mathematics of fair allocation assist the negotiations? It would be nice to think we lived in a world that was sufficiently rational for such an approach, but politics seldom works that way. In particular, people's valuations of things tend to change after tentative agreements have been reached, in which case what we've just discussed won't work. Still, it could be worth giving rational methods a try. |