A Fair Division Problem has a set of N players ( P1, P2, . . . , PN) and a set of goods S. We wish to divide S into N shares ( s1, s2, . . . , sN) so that each player gets a fair share of S. A fair share is a share that, in the opinion of the player receiving it, is worth 1/N of the total value of S. We will assume that any player is capable of deciding whether his share is fair; that is, we assume that any player is capable of assigning unambiguous values to S and to various parts of S.
A Fair Division Scheme is a systematic procedure for solving a fair division problem. It must have the following properties.
A fair division scheme does not gaurantee that each player will get a fair share; it gaurantees only that he/she can get a fair share if he/she plays rationally.
Fair division problems can be classified three ways depending on the nature of the set of goods S.
We will consider six different fair division schemes in all, four of which are schemes for solving continuous fair division problems and two of which are schemes for solving discrete fair division problems.
We first consider the Divider-Chooser Method. Alice and Bob win a half- pepperoni half-anchovie pizza. Bob likes both anchovies and pepperoni equally well, and he considers the value of the pizza to be $8. (They are free to assign whatever value they choose to the pizza since they did not have to pay for it.) Since Alice, on the other hand, cannot stand anchovies, she considers the entire value of the pizza to be in the pepperoni half with the anchovie halve worth nothing! She assigns a value of only $5 to the pizza since half of it is worthless. Notice here that in order to comply with the rules for solving this problem by a fair division scheme, Bob must be unaware that Alice hates anchovies.
Suppose that (perhaps by coin toss) Bob becomes the divider and Alice the chooser. Bob then (behaving rationally) cuts the pizza exactly in half in such a way that one half is exactly one-fourth pepperoni and and three-fourths anchovie. (There are other ways to divide the pizza "rationally" since Bob does not know about Alice's aversion to anchovies. He only has to make sure each piece is the same size.) Now Alice has an easy choice--she picks the half that is three-fourths pepperoni and only one fourth anchovies. In her value system it is worth $3.75, which is far more than half of the total value of the pizza (by her values); she obviously has a fair share. Bob gets the other half worth $4 (to him), which is exactly half the total value which he placed at $8; clearly he also has a fair share. Not only did each get a fair share (or more) but they did it all by themselves without any outside intervention; this is what we mean when we say an fair division scheme must be internal.
"But wait," you say. "If Bob had ended up with all the anchovies and Alice all the pepperoni, Alice would have been better off, and Bob would have been just as well off!" This is as irrelevant as it is true. A fair division scheme is required only to give a fair division and not the best division.
It is interesting to consider to consider what might have happened with Alice the divider and Bob the chooser. Alice could rationally divide the pizza up in many ways although the way Bob did it would certainly not be one of them! In order to insure her share was fair, she would have to divide the pizza in such a way that each share had exactly half of the pepperoni part of the pizza; otherwise, she could end up with less than a fair share. Notice that there is no rational reason for her to divide the pizza exactly in half; since the anchovie part has no value to her, it would be "rational" to cut out one-fourth of the pizza, making sure it was all pepperoni. In that case Bob would almost certainly choose the big part, which would be worth $6 to him, more than a fair share. That would leave Alice with $2.50 worth (Remember that the anchovie part is worthless in her value system.), which is a fair share.
Notice that in each of these examples, the divider came out with a fair share while the chooser came out with more than a fair share. To be really fair, we need to pick our chooser randomly.
This is just an extension of the Divider-Chooser Method to more than two players. Again we must pick our divider randomly. This fair division scheme requires three steps.
Although we have described the process for three players, we can easily extend it to more players if needed.
This is another three step process, and again we can extend it to more than three players. After a chooser and two dividers are chosen at random, they proceed as follows.
As an example, we will let Don, Dora, and Cal divide a pizza, which they agree is worth $18 (since each was willing to put up $6). Again, they get a half-anchovie half-pepperoni pizza. They will use the Lone Chooser Method, and by flipping coins with odd person out, Cal becomes the chooser leaving Don and Dora the dividers. When Don and Dora flip again to see who is chooser in Step 1, Dora wins. As is usually the case, each player has a different value system.
Here is what the pizza looks like to the three players.
Don must make the first cut, and since he has no preference between pepperoni and anchovies, all he needs to do is split the pizza into two equal-sized pieces. Suppose he cuts so that one piece is one-third pepperoni and two-thirds anchovies. In his value system, each piece has identical value. Now Dora must choose between these two pieces. Here is what they look like to Dora.
It is pretty obvious to Dora which is the better deal--the $10.50 worth of pizza is clearly preferable to the $7.50 piece. The next step is for Don and Dora each to cut their pieces into thirds. Again, it does not make much difference to Don how to go about it except that each piece should be the same size. The most straightforward way for him to do this is to leave one entirely anchovie piece and two entirely pepperoni pieces. Each of these is the same size and each is 1/6 of the original pizza. It is somewhat more complicated for Dora; she needs to make each piece worth $3.50. One way to do that is to put the $1.50 worth of pepperoni pizza with $2 worth of anchovie pizza and then split equally what is left of the anchovie part. Two dollars worth of the anchovie part is is 2/9, and since Dora's anchovie part is 1/3 of the original pizza, the part that remains attached to the pepperoni is 2/27 of the original pizza. Since Dora's pepperoni part was originally 1/6 of the pizza, that makes the mixed piece 13/54 of the original, somewhat bigger than 1/6. That makes the two anchovie pieces (after she splits what was left) 7/54 of the original pizza.
And finally it is time for Cal to choose one piece from Don's three pieces and one from Dora's three pieces. Since Don's pieces are all the same size and two of them are pepperoni, Cal takes a pepperoni piece from Don. Since only one of Dora's pieces has any pepperoni at all, that one is obviously Cal's choice of what she has to offer. Now let us look at what everybody ended up with.
|Share||18/54 P and 4/54 A||9/54 P and 9/54 A||no P and 14/54 A|
|Value to Cal||$12.00||$6.00||$0.00|
|Value to Don||$7.33||$6.00||$4.67|
|Value to Dora||$5.00||$6.00||$7.00|
Notice that both Cal and Dora feel that they got more than a fair share ($6 worth) and that Cal, being the lone chooser, did best of all (by his estimation). Also notice the Don, who had to divide twice, got only a fair share, and if he looks around after the division, he will think that Cal got a better deal than he did.
We emphasize again that getting a fair share is all a fair division scheme promises to deliver; it does not promise the best share. We also point out that things would have come out different (but still fair) had the initial coin tosses come out different.
In this method everybody is both a divider and a chooser. The method makes sense only for division problems in which S is something more complicated than a pizza; the example in your textbook describes five shipwrecked sailers who decide to divide up the tropical island they landed on. The value systems of the five are complex enough so that it is virtually impossible to describe them: perhaps one person values a sheltered cove while another favors a plot with some high ground while still another favors a plot that is scenically uninteresting but has some source of food. Be sure to work through the example (Example 7).
The method is easy to apply but somewhat difficult to describe. We start by randomly assigning an order to the N players. The P1 is really the only one who has to do anything; he claims a certain piece of S. If P2 thinks P1 was too greedy, he can jump P1's claim by removing part of it (diminishing) and returning it. If on the other hand P2 thinks P1 was too timid and did not stake a big enough claim, he can simply do nothing and let P3 go next. After everyone has played or passed, whoever was the "last diminisher" takes his claim and leaves the game.
The next step is just to repeat what we just finished but with one less player. If we continue this process, we will eventually have only two players left who can finish the process by the divider-chooser method.
So why does this produce fair shares? If P1 gets left with his initial claim (because everybody else passes), then he got what he was identifying as a fair share. Nobody else can take it away from him without "diminishing" it: P2's diminishing it should make it appear less than a fair share to P1 (unless he was being too greedy initially), which would make the remainder of S appear to contain potentially more than a fair share (a situation he should be happy with). The same argument applies to everbody else as well. Note that the pieces removed by a diminisher can be arbitrarily small, a situation that immediately penalizes even the slightest bit of greed.
Next we consider discrete fair division problems. The method of sealed bids is an old and much used method; probably every lawyer who has ever served as executor/executrix of an estate is (or should be) familiar with the method. This method can be described as a three step process.
If the method of sealed bids seems too good to be true, it is because of human nature and not because of any mathematical flaw in the method. Here is a list of "problems" that can arise with the method.
We illustrate the method of sealed bids with an example. The players are Al, Ben, Cal, Don, and Ed who are splitting up an inheritance comprising a house, a vacation cottage, two cars (a BMW and a Saab), a yacht, and two valuable paintings (a Miro and a Klee). The brothers agree beforehand that any ties for high bid will be resolved with a coin toss. The following table shows the results of the bidding step.
Next we continue to step 2, the allocation. Each item goes to the highest bidder, so Al gets the BMW, the Saab, and the Miro. Those items total $149,000, which is $13,200 more than Al's assessment of a fair share, $135,800, so Al has to pay $13,200 back to the estate. We can allocate to the others in the same way; the table below shows how it all works out.
|Player||Items Received||Value||+ ( - ) Cash|
|Al||BMW, Saab, Miro||$149,000||($13,200)|
What is amazing is that after everyone gets his fair share, there is $91,700 left over. This would be a very nice fee for the executor, but the brothers really did not need an executor since the process is internal. So everyone gets an extra $18,340 over and above what each one considers a fair share! Notice that none of this works so neatly if one of the players who has to pay the estate does not have enough the money.
This method gets around the problem of having to come up with money, but it will not work at all for the estate in the last example. There must, however, be a relatively large number of items in S for it to be decisive. We start the process by stringing out all the items in S in a long line. Like the method of sealed bids, this method also comprises three steps.
Be sure to work through the example (Example 10.) in your textbook. From the pictures in the example, you can see easily that every player gets a fair share. Following is another example of using the method of markers.
Alice, Beth, and Carol want to divide what is left of a can of mixed nuts. There are 6 cashews, 9 pecan halves, and 3 walnut halves to be divided. The women's value systems are as follows.
If the nuts are lined up as shown below, where would each woman, playing rationally, place her markers?
P P W C P C P P P W W C P C P P C C ^ ^ B B ^ ^ C C ^ ^ A A
All Alice cares about is getting a walnut in each group. What is marked in the figure above is only one way she can rationally play. (Her first marker can be anywhere between the first two walnuts.)
If Beth counts walnuts as two and pecans as 1, then the nuts have a value of fifteen, a fair share of which is five. She therefore counts walnuts twice and pecans once until she has counted to five and places a marker. Then she continues counting to ten and places her other marker.
Finally, Carol counts cashews twice and pecans and walnuts once, so the total is twenty-four in her value system. Each of her segments should be worth eight, which you can verify easily with a little counting.
Now for the division. Alice's marker is leftmost, so she gets two pecans, a walnut, and a cashew. She is satisfied with this take since it contains one-third of the total value (to her) of S. We give her her nuts, remove her markers, and send her home happy (or at least satisfied).
The first marker in the second group of markers belongs to Beth, so she gets everything back to her first marker. Her take is a walnut, a cashew, and two pecans, which she considers a fair share. Notice that there is a pecan left over.
Finally, Carol gets every thing to the right of her last marker--three cashews and two pecans, which is a fair share in her value system. Here we have lots of leftovers--a walnut, a cashew, and a pecan. That makes the total of the leftovers a walnut, a cashew, and two pecans after everybody has received what she considers a fair share! These leftovers can be distributed randomly as a bonus.