An Encore BlogHad a chance to take ten of my students down to the Center for Mathematical Sciences in Cambridge one night a while back to hear a lecture by Richard Weber of Queen’s College. He is the one in the right on the picture during his appearance on the British TV game show, Who Wants to be a Millionaire. He also happens to be the Churchill Professor of Mathematics for Operational Research. His primary work is in problems in communications and systems, and the mathematics of optimization, algorithms, probability and game theory.
On this particular night, he was talking about “The Disputed Garment Problem”, an ancient problem involving the concept of fair division. It seems a simple idea. We all think we know when the division is un-fair, and if we picked an honest, unbiased third person to make the division, it would seem that a fair result would follow, and yet, it seldom does. If you ask people to describe the rules that a fair division would entail, most people can come up with several rules, what a mathematician would call the axiom set, and probably agree with each other. But then when you make a decision consistent with those rules, the same people will scratch their heads and say, “Wait, that’s not fair.” What is even more scary is that often they can make five or six rules, and you find out that it is Impossible to meet all those rules.
So let’s look at a simple example. The Babylonian Talmud is a compilation of the ancient laws from an oral tradition set down during the first five centuries after Christ. They serve as the basis of Jewish religious, criminal and civil law. In one of the problems the Talmud offers: Two people dispute the possession over a garment. One claims that he should get half, the other claims all of it. The solution of the Talmud is that the first gets ¼, and the other gets ¾ .
The Talmud is a terse document, (sort of like 19th century math books). It tells you what to do, but not why. In this case however, the reasoning seems somewhat clear. Since half the garment is not in dispute, it should go to the one who claims the whole. The other half, claimed by both, shall be shared equally, giving the 3:1 split.
Given that beginning, a more interesting problem involves sharing by three wives in what is called the marriage contract problem: A man has three wives whose marriage contracts specify that in the case of his death they receive 100, 200 and 300 units respectively. But when he dies he leaves less than a sufficient amount to cover the 600 debt. How should the estate be divided.
The answers the Talmud gives for different amounts is surprising, and somewhat confusing. If the man leaves an estate of 100 units, the three wives will divide it equally (see below). If the estate has a value of 300 the wives divide it proportional to their claim, each getting ½ the amount they were promised. But what is happening in the case with 200 remaining? The question for the reader is, what will be the division of an estate with 400 remaining? (I will give the answer later, but don’t cheat, try to work it out. And additional clues will come if you are really stuck…. I was)
Estate..wife 1...wife 2....wife 3
100.....33 1/3...33 1/3....33 1/3
200.....50 ......75........75
300.....50 ......100......150
Ok, so which of those seem like a fair division to you, and which do you think most people would agree with. With your answer tucked away, here's a similar problem with a different twist. Three people want to build a runway for their private planes. For Pilot A, the cost of a runway for his plane would be 100 units. For Pilot B, with a bigger plane and therefore a longer runway needed, the cost would be 200 units. And Pilot C, needing an even longer runway, would have to pay 300 units. If they form a coalition, they can build one runway big enough for all three for the 300 units. How should the share the costs?
Should they pay 100 units each? Probably not, the first guy would see no advantage to the coalition. What about each paying half of what they would pay for their separate runways? If that sounds fair, then look again at the marriage contract problem above for an estate of 300; are these really the same problem? The numbers are all the same. The only difference is that in one case they are sharing a debt of 600 units and paying a combined 300, and in the earlier case they had a combined credit of 600 and sharing a combined payout of 300. Is fair in one case the same as fair in the other case?
The good professor provided another alternative to the airplane problem, using a method called the Shapley value, named for Lloyd Stowell Shapley, from UCLA. The method is founded on objection and counter-objection of each party being balanced. But an easier way to understand the value is to take every possible permutation (different orders of the pilots) and how much each would pay if they joined the coalition in each order. For instance if they joined in the order 3,2,1, the large plane pilot would have to pay for the whole runway, the other two would pay nothing. Here is a list of ALL the possible orders and the amount each pays:
Order.......Pilot 1...Pilot 2...Pilot 3
1,2,3.......100.......100.......100
1,3,2.......100 .......0 .......200
2,1,3 ....... 0.......200.......100
2,3,1 ....... 0.......200.......100
3,1,2 ....... 0.......0.......300
3,2,1....... 0 ......0.......300
Now if you add up all the possible amounts, the six ways add up to 1800 dollars. Since pilot one pays 200 of the 1800, his share of 300 should be 1/9 of the 300 units, or 33.33 units. Pilot 2 should bay 5/18 of the 300 or 83.33 units, and the last pilot should pay 11/18 of the 300, or 183.33 units. Now that’s what I'd like for public service, good progressive taxation… make the rich guys carry the burden.
I expressed my dislike for the three wives solution on the night. I explained that if my bank went bankrupt and offered me 10 cents on the dollar, and paid another guy 50 cents on the dollar because he had more money, I would be screaming like a stuck pig. But if fair on one problem is fair on the other, then I’m REALLY not liking the rich guy getting 61 percent of his money back, and the little guy gets 33 % return.
Ok, so I’m going to make it a little more complicated in a minute, but I want to go back to the case of the three wives in the Talmud. If the rule is consistent, then any two wives should get the same amount they would get if there were only two of them and the estate was the sum of what they shared and the division was by the disputed garment solution. Ummm, let me try again. In the case for 300 in the estate, wife 1 and wife 2 get a total of 150 units, and their claim is for 100 and 200. If we use the logic of the disputed garment, then since wife 1 only claims 100 units, wife 2 should get the 50 extra right off, and they should share the remaining 100 equally giving a solution for the two of 50, 100… ok, that works, and if you check the other two possible groupings (wives 1 and 3 and wives 2 and 3) it also works out. So maybe this is the Talmudic approach. Can you find the solution for 400 units in the estate now?
For over 1500 years scholars studied the Talmud and couldn’t find a rule to explain the determination of values that was more specific than the general rule I just gave. Then Robert Aumann, a professor at the Hebrew University of Jerusalem, showed that the solutions were the ones you would get by using the Nucleolus for the coalitional game (I will spare the general reader the several pages of equations with subscripts and other assorted devices of mathematical torture that explain Nucleolus, but if you are, like me, one who shouts “Show me the Math”, you may find an extended description
here. .)
Now, if you STILL haven’t figured out how much each person gets with the division of an estate of 400 units, here is a physical method that, remarkably, gives the solution for any amount less than the 600 units promised the three wives.
Imagine the image shows six interconnected tanks. The two tanks on the left hold fifty units of liquid each and represent the share of wife 1. The second set has two tanks of 100 units each, and represent the second wife's promised 200 units, and the third set of two each hold 150 units, to represent the 300 units of wife three. Now we pour an amount of liquid equal to the value of the estate into the top three tanks, divided equally between them. Behold, what is left when the connection across the bottom is allowed to do its thing, is the Talmudic solution. The solution above shows the answer for the division of an estate of 100 units. Here is the one for 300 units to help you see the physical solution method.
Now admit it, even if your not a math/science person, even if you don’t think the solution is fair, that’s a pretty cute trick… ahh go on, admit it.
Ok, if you STILL don't have the answer for 400, the division is 50, 125, 225....