## Fair Division Problems and Fair Division Schemes

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.

• It is decisive.
• It is internal.
• It assumes the players are ignorant of each other.
• It assumes the players behave rationally.

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.

• Continuous. The set S can be divided infinitely many ways. Examples are large sums of money, cakes, and kegs of beer.

• Discrete. The set comprises indivisible objects (or objects that are not easily divisible). Examples are houses, boats, valuable paintings, pieces of hard candy, etc.

• Mixed. The set contains both continuous and descrete components. Most inheritances would fall into this catagory.

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.

• For Solving Continuous Fair Division Problems

• The Divider-Chooser Method

• The Lone Divider Method

• The Lone Chooser Method

• The Last Diminisher Method

• For Solving Discrete Fair Division Problems

• The Method of Sealed Bids

• The Method of Markers

### The Divider-Chooser Method

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.

### The Lone Divider Method

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.

• Step 1. Division--The divider slices the pizza into three pieces. This division is rational only if each piece has equal value to the divider.

• Step 2. Declarations--Each chooser declares which pieces he or she considers acceptable (a fair share, in other words).

• Step 3. Distribution--What happens here depends on the declarations.

• Case 1. One chooser declares more than one piece acceptable. Then the other chooser gets her or his chosen piece, the chooser of more than one piece gets her or his other choice, and the divider gets what was left. (Note that everyone gets a fair share.)

• Case 2. Both choosers declare just one piece, and they are different. The distribution is obvious in this case.

• Case 3. Both choosers declare just one piece, and it is the same piece. Here we give the divider one of the two undeclared pieces (randomly selected). Then we put the remaining two pieces back together and apply the divider-chooser method. Again everyone gets a fair share.

Although we have described the process for three players, we can easily extend it to more players if needed.

### The Lone Chooser Method

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.

• Step 1. First Division--The two dividers split the pizza by the divider-chooser method.

• Step 2. Second Division--Each divider now divides his part into three parts he considers equal.

• Step 3. Selection--The chooser picks one piece from each divider, and each divider keeps whatever he has left. Again, we have fair shares for everybody.

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.

• Cal can't stand anchovies.

• Don likes anchovies and pepperoni equally well.

• Dora likes anchovies three times as much as pepperoni.

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.

Player Cal Don Dora
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.

### The Last Diminisher Method

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.

### The Method of Sealed Bids

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.

• Step 1. Bidding. Each player produces a sealed bid in which he or she attaches a dollar value to each item in S. A player's fair share is 1/N of his total assessment.

• Step 2. Allocation. Each item in S goes to the highest bidder for that item. If her/his assessed value of the items received exceeds her/his fair share, she/he must pay the difference. If the assessed value of the items received falls short of a fair share, then she/he is paid out of money that others have had to pay.

• Step 3. Dividing the Surplus There is almost always a surplus of cash that is divided equally among the players.

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.

• Problem 1. Cash Flow. Each player must have enough money so that he can make good on all her bids that happen to be the high. Note that there is nothing to prevent one player from getting everything! Of course in that case, she had better have plenty of cash to pay off the others. This problem limits the usefulness of the method of sealed bids even for the scrupulously honest.

• Problem 2. "Priceless Items." No player can be absolutely insistent on getting some favorite item. Everyone has to be willing to accept some amount of money as a substitute for any item.

• Problem 3. Players Know Each Other. Suppose Lucy honestly thinks an item is worth \$1000 but knows that Linus thinks the same item is worth \$2000. What is to keep Lucy from inflating her bid to \$1995, knowing that she will not get the item? This can be a serious problem in estate divisions since the players are likely to know each other well.

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.

Item Al Ben Cal Don Ed
House \$200,000 \$215,000 \$195,000 \$175,000 \$205,000
Cottage \$60,000 \$49,000 \$62,500 \$59,500 \$55,000
BMW \$29,000 \$24,500 \$25,000 \$27,500 \$27,500
Saab \$25,000 \$19,000 \$22,500 \$24,500 \$19,500
Yacht \$120,000 \$125,000 \$119,000 \$129,000 \$132,500
Miro \$95,000 \$89,000 \$50,000 \$75,000 \$65,000
Klee \$150,000 \$135,000 \$99,000 \$179,000 \$149,000
TOTAL \$679,000 \$656,500 \$573,000 \$669,500 \$653,500
FAIR SHARE \$135,800 \$131,300 \$114,600 \$133,900 \$130,700

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)
Ben House \$215,000 (\$83,700)
Cal Cottage \$62,500 \$52,100
Don Klee \$179,000 (\$45,100)
Ed Yacht \$149,000 (\$1,800)
SURPLUS \$91,700

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.

### The Method of Markers

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.

• Step 1. Bidding. Each player secretly divides the line of items into N segments, each of which she considers a fair share. This is easily done by positioning markers.

• Step 2. Allocation. Find the leftmost marker in the line, give the player whose marker it is everything to the left of it, and remove the rest of her markers. Then find the first marker in the second group of markers, give the player whose marker it is every thing between it and her first marker, and remove the rest of her markers. Continue the process until everybody has her fair share.

• Step 3. Dividing the Surplus. Again there will usually be some leftovers, and these can be distributed by chance. If there are many leftovers, we can even use the method of markers again.

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.

• Alice does not care at all about pecans of cashews but loves walnuts.

• Beth Likes walnuts twice as much as pecans and really does not care for cashews.

• Carol likes all the nuts but likes cashews twice as much as the others.

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.