Prepared by:

Joseph Malkevitch
Mathematics Department
York College (CUNY)
Jamaica, NY 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

Steven Brams and Alan Taylor developed an algorithm (Adjusted Winner) which allows two people A and B (perhaps with the help of a neutral third party) to try to fairly divide a collection of valued objects between them. Of course one could take the objects and sell them at current market price and divide the proceeds from the sale equally. Here we are concerned with objects that have emotional as well as economic value so we proceed differently. An analysis of the adjusted winner method shows that typically A will get all of some of the objects, B will get all of others, and that there is one object that might have to be "cut up" and shared in some sense. (Sometimes there are ways that this can be achieved in a "clever" manner. For example, rather than cut up a painting one could have it on A's wall 5 months of the year and on B's wall 12 months of the year.) Unfortunately, we will not know in advance which of the items to be divided up will have to be "shared."

Rather than describe the algorithm involved in formal mathematical notation I will give a few examples which I hope will show how the algorithm works in practice. The basic idea is that each of A and B is given 100 points that they can distribute in any way they like as "values" or "utilities" to the objects they wish to effect a division for. The players, in essence, put in "bids" for the objects using exactly these 100 points as "currency."

We will assume that the points are assigned independently by the two people and we will assume that they will give honest assessments of the value of the objects from their point of view, without taking into account the values that they think the other person is assigning.

Our goal is to give each of the people items in such a way that they perceive that they have equal numbers of points after the division is carried out. It turns out we will be able to do this so each person gets possession of objects (and perhaps a part of one of the objects) so that in that person's view he/she got at least half of the his/her perceived value of the collection of things.

Example 1:

Table 1 below has been assembled from the input that A and B provided a neutral friend with on three items, K, L., M, which they ranked honestly and without consulting each other. The values were chosen without taking into account what their "opponent" might use as values.

 Items to divide A (Alex) B (Barbara) K 45 25 L 35 40 M 20 35

Table 1

It is possible that some items will be given the same value in points by each of the people, but in this example that does not happen.

The way the algorithm proceeds is to decide an initial assignment of the items based on the size of the numbers in each row of the table. This is done by giving the person with the larger "bid" for the item that item.

Table 2 shows the person who was assigned the given item with a star.

 Items to divide A (Alex) B (Barbara) K 45 * 25 L 35 40 * M 20 35 *

Table 2

Thus, based on Table 2, we would "give" K to Alex and L and M to Barbara. This means that Alex gets 45 points of value while Barbara gets 75 point of value. Now if these two numbers were exactly equal, then we would be done because in each person's perception they got equal amounts (See Table 7 in Appendix I where 4 items were divvied up so that each person thought they got 60 points out of 100.)

Now the intuition is that to get an equal number of points for Alex and Barbara we must transfer some item or part of some item from Barbara to Alex, so that after the transfer the total number of points for Alex and Barbara will be the same, or closer to the same. To do this, the procedure that Brams and Taylor developed requires that we list the ratio of the point values of the items "won" by the person with a larger number of points in non-decreasing order:

Ratios:

40/35 (for L)
35/20 (for M)

We pick the item at the top of this list and try to redistribute it (or a part of it) from Barbara (larger total number of points) to Alex (smaller total number of points).

Suppose we let x be the fraction of L we take from Barbara and give to Alex, with the goal that after this transfer, the number of points they each have will be equal.

We can set up this equation to try to achieve that goal, given that Alex currently has 45 points and Barbara 75:

45 + x(35) = 75 - x(40)

(Alex had 45 points and he now will have x times 35 additional points because L is worth 35 to him. Barbara has 75 points but after the transfer she will have x times 40 fewer points because she values L at 40 points.)

Solving this equation we get that:

x = 30/75 = 2/5.

Note that if we substitute 2/5 back into the equation, we get 59 on both the right and the left hand side. The two sides must be equal if we solved the equation properly.

So the assignment of objects we get is:

Alex gets K and 40 percent (2/5) of L.
Barbara gets M and 60 percent (1-2/5) of L.

As a check that they each have equal numbers of points from their own point of view, consider this computation:

K is worth 45 to Alex and 2/5 of L (worth 35 to Alex) is 14. So Alex gets 59 points.

M is worth 35 points to Barbara, and 3/5 of L (worth 40 points to Barbara) is 24. Thus, Barbara gets 59 points as well.

Note that this calculation is not identical to computing the left and right sides of the equation above.

Example 2:

Table 3 below has been assembled from the input that A and B provided a neutral friend on four items, K, L., M, N which they ranked honestly and without consulting each other. The values were chosen without taking into account what their "opponent" might use as values.

 Items to divide A B K 45 25 L 35 40 M 10 25 N 10 10

Table 3

If we proceed as above, we place stars in rows of Table 4 as shown, but what do we do with N, which is valued equally by Alex and Barbara? How about trying this experiment. First we give it to Alex and see what happens and then we give it to Barbara and see what happens!

 Items to divide A B K 45 * 25 L 15 20 * M 20 35 * N 20 20

Table 4

Case i: (N to Alex)

In this case we have rows starred as in Table 5:

 Items to divide A B K 45 * 25 L 15 20 * M 20 35 * N 20 * 20

Table 5

Alex has 65 points and Barbara has 55.

So the ratio list is:

20/20 for N
45/25 for K

Selecting the first row above we will redistribute contested item N. So let us try to divide N so that we equalize points. If x represents the part of N we take from Alex to give to Barbara, we have:

55 + x(20) = 65 - x(20)

(The new value to Barbara is on the left of the equal sign, and the new value to Alex is on the right.)

40x = 10

x = 1/4

So now Alex gets K (worth 45) and 75 percent of N (20 points) which is worth 45 + .75(20) = 60 points, while Barbara gets L (worth 20) and M worth (35) and 25 percent of N (worth 20), so she gets 20 + 35 + 5 = 60 points.

Case ii (N to Barbara)

In this case we have rows starred as in Table 6:

 Items to divide A B K 45 * 25 L 15 20 * M 20 35 * N 20 20 *

Table 6

At this stage Barbara has 75 points (she gets L, M, N) and Alex has 45 points (he gets K worth 45 points in his view).

So the table of ratios is:

20/20 (for N)
20/15 (for L)
35/20 (for M)

Selecting the first row above we will redistribute contested item N. We therefore try transferring a fraction of N from Barbara (who has 75 points) to Alex (who has 45) with the goal of equalizing the number of points after the transfer.

We get the equation:

45 + x(20) = 75 - x(20)

(The new value to Alex is on the left, and the new value to Barbara is on the right.)

40x = 30

x = 3/4

So we give Alex K (worth 45) and 75 percent of N (worth 20) which gives Alex 45 + 15 points, or 60 points. Barbara gets L (worth 20) and M worth (35) and 25 percent of N (worth 20) so she gets 20 + 35 + 5 = 60 points. So Alex and Barbara get an equal number of points.

Note that in each case we get the same allocation in the end whether we assigned the equally valued item initially to Alex or initially to Barbara, which is exactly the way we would expect it to work.

Appendix

In this example (Table 7) giving Alex items K and L and Barbara items M and N gives them each 60 points, and 2 items each.

 Items to divide A B K 28 * 10 L 32 * 30 M 30 32 * N 10 28 *

Table 7

References:

S. Brams and A. Taylor, The Win-Win Solution , W. W. Norton, New York, 1999.

S. Brams and A. Taylor, Fair Division, Cambridge U. Press, New York, 1996.