Section7.2The Adjusted Winner Procedure for Fair Division
Suppose you share an apartment with a friend. You have bought several appliances together, like a microwave oven, a coffee maker, and a vacuum cleaner. At the end of the year, you must somehow divide up these items, which are worth more to you than the tiny amount of money you could get by selling them. How do you divide the items? If one of you suggests a split of items, how do you decide if the division is fair?
It is easy to divide a cakejust have one person cut and the other choose. A cake is a continuous quantity, so it can be divided anywhere; and because all pieces of a given size are virtually identical, it is easy to see if you are getting a fair share. Fair division problem involving unequal discrete items are much harder. Examples like this occur in many settings. A married couple getting divorced have to divide their property but do not wish to sell everything. Two roommates have to divide up a list of chores. Two real estate partners decide to divide their business and have to allocate the property between them. Fair division issues of this sort are contentious and frequently result in hard feelings or end up being decided in court, where the principle (with license for exaggeration) is that found in Benjamin Franklin's poem, The Benefit of Going to Law: A shell for him, a shell for thee; the middle is the lawyer's fee.
The adjusted winner procedure is a mathematical attempt to achieve a fair
division of unequal discrete items between two entities, referred to in mathematical terms as players.
As an example, consider a hypothetical divorce settlement between Caesar and Cleopatra, in which the valuable property consists of the port of Alexandria, a palace, a legion of soldiers, and an exotic poison collection. The players place different values on each item, so it seems reasonable that a division could be achieved that is envy-free, which means that neither player would want to trade their share with the other. A more ambitious goal is to produce a division that is equitable, meaning that each player is equally satisfied with his/her share. We'll have to define this term more carefully in the context of a given method.
SubsectionSteps of the Adjusted Winner Procedure
The adjusted winner procedure is one way to guarantee a division that is envy-free, and (if an item can be subdivided) at least close to equitable. It is conducted via a sequence of 6 steps:
SubsubsectionStep 1
Each player uses whatever means (s)he wishes to assign values to each item so that the total is 100 points. In the example, let's say Cleopatra places a value of 40 points on the legion of soldiers and 20 points on each of the other items. Caesar is not interested in the poison collection, so he chooses scores of 50 for the legion, 30 for the port, 20 for the palace, and 0 for the poisons.
| Score for | Score for | |
| Item | Caesar | Cleopatra |
| Port of Alexandria | 30 | 20 |
| Palace | 20 | 20 |
| Legion of soldiers | 50 | 40 |
| Exotic poisons | 0 | 20 |
SubsubsectionStep 2
Arbitrarily select one of the players as Player 1
. Compute a value ratio for each item as the quotient of player 1's score divided by player 2's score. In the example, with Caesar as player 1, the ratios are 1.5 for the port, 1.0 for the palace, 1.25 for the legion, and 0 for the poison collection.
| Score for | Score for | Ratio | |
| Item | Caesar | Cleopatra | Caesar Cleo |
| Port of Alexandria | 30 | 20 | 1.50 |
| Palace | 20 | 20 | 1.00 |
| Legion of soldiers | 50 | 40 | 1.25 |
| Exotic poisons | 0 | 20 | 0.00 |
SubsubsectionStep 3
Arrange the items by order of value ratios. In the example, the port is first, followed by the legion, the palace, and the poisons. If there is a tie, those items can be ranked in either order, but one order may turn out to be more convenient in step 6, so the procedure should be done both ways.
| Score for | Score for | Ratio | |
| Item | Caesar | Cleopatra | Caesar Cleo |
| Port of Alexandria | 30 | 20 | 1.50 |
| Legion of soldiers | 50 | 40 | 1.25 |
| Palace | 20 | 20 | 1.00 |
| Exotic poisons | 0 | 20 | 0.00 |
SubsubsectionStep 4
Assign the item with highest value ratio to player 1 and the item with lowest value ratio to player 2. Thus, Caesar gets the port and Cleopatra the poisons. At this point, Caesar has 30 points and Cleopatra 20. Notice, however, that Cleopatra judges Caesar's initial item to be worth only 20 points, while Caesar judges Cleopatra's first item to be worth 0. This is why the item with highest ratio goes to player 1 and the one with the lowest ratio goes to player 2.
| Score for | Score for | Ratio | Points for | Points for | |
| Item | Caesar | Cleopatra | Caesar Cleo | Caesar | Cleopatra |
| Port of Alexandria | 30 | 20 | 1.50 | 30 | 0 |
| Legion of soldiers | 50 | 40 | 1.25 | ||
| Palace | 20 | 20 | 1.00 | ||
| Exotic poisons | 0 | 20 | 0.00 | 0 | 20 |
| Total | 100 | 100 | 30 | 20 |
SubsubsectionStep 5
Assign the next item in the list, from top or bottom as needed, to the player who has used fewer points so far. Keep going until all items have been tentatively assigned. At this stage in the example, Cleopatra is behind by 3020, so she gets the next item. Working up from the bottom, the best item to give her is the palace.
| Score for | Score for | Ratio | Points for | Points for | |
| Item | Caesar | Cleopatra | Caesar Cleo | Caesar | Cleopatra |
| Port of Alexandria | 30 | 20 | 1.50 | 30 | 0 |
| Legion of soldiers | 50 | 40 | 1.25 | ||
| Palace | 20 | 20 | 1.00 | 0 | 20 |
| Exotic poisons | 0 | 20 | 0.00 | 0 | 20 |
| Total | 100 | 100 | 30 | 40 |
Now Caesar is behind 4030, so the final item gets assigned to him. This produces a tentative total of 80 for Caesar and 40 for Cleopatra.
| Score for | Score for | Ratio | Points for | Points for | |
| Item | Caesar | Cleopatra | Caesar Cleo | Caesar | Cleopatra |
| Port of Alexandria | 30 | 20 | 1.50 | 30 | 0 |
| Legion of soldiers | 50 | 40 | 1.25 | 50 | 0 |
| Palace | 20 | 20 | 1.00 | 0 | 20 |
| Exotic poisons | 0 | 20 | 0.00 | 0 | 20 |
| Total | 100 | 100 | 80 | 40 |
SubsubsectionSplitting the tipping point item
So far, we have not achieved the goal of fair division. Cleopatra values Caesar's share at 60 points and her own share at 40 points, so the division is not envy-free. We could improve the division by giving Cleopatra a portion of the tipping point itemthat is, the last item given to the player whose total is higher. In this example, the tipping point item is the legion, since it was the last item given to Caesar, who ended with the higher score.
The last step of the adjusted winner procedure consists of splitting the tipping point item in a certain way. Before discussing the details, let's experiment with this example. If we split the legion equally, then Caesar gets 30 for the port and 25 for the legion, for a total of 55, while Cleopatra gets 20 for each of the palace, the legion, and the poisons, for a total of 60. Note that each player's points for a share of the legion is based on that player's assessed value: half of the legion is worth 25 points to Caesar but only 20 points to Cleopatra.
| Score for | Score for | Ratio | Points for | Points for | |
| Item | Caesar | Cleopatra | Caesar Cleo | Caesar | Cleopatra |
| Port of Alexandria | 30 | 20 | 1.50 | 30 | 0 |
| Legion of soldiers | 50 | 40 | 1.25 | 25 | 20 |
| Palace | 20 | 20 | 1.00 | 0 | 20 |
| Exotic poisons | 0 | 20 | 0.00 | 0 | 20 |
| Total | 100 | 100 | 55 | 60 |
In this example, dividing the last item in half achieves the goal of an envy-free division, but the division is not equitable. Caesar likes his share better than he likes Cleopatra's share, but he does not like his share as much as Cleopatra likes hers. Being extremely competitive, he probably wants to make sure the values are actually equal, which would require that he gives Cleopatra less than half of the legion. In the adjusted winner procedure, a division is only equitable if each player's final score is the same.
Therefore, the last step of the adjusted winner procedure will, ideally, not just split the tipping point item in half. Instead, it is split in a very specific way, as described next in Step 6.
SubsubsectionStep 6
Assuming that some way can be found to divide the single shared item into two portions of whatever size is required, it is possible to use algebra to make the division equitable as well as envy-free by adding one final step:
Let \(S\) be the sum of the values the players placed on the item that must be shared. In the example, the legion is the shared item. Caesar's 50 points and Cleopatra's 40 points add up to 90, so \(S = 90\text{.}\)
Then let \(D\) be the difference in total point values initially awarded to the two players. Before the sharing of the legion, the score is Caesar 80 and Cleopatra 40 for a difference of \(80-40=40\text{,}\) so \(D = 40\text{.}\) The rule for equitable division is that the quantity
is the fraction of the shared item that is given away to the other player. In the example, we get \(x = 40=90 = 4=9 = 0.444\text{.}\) Thus, Caesar needs to give 0.444 (or 44.4%) of the legion to Cleopatra and keep \(5/9=0.556\) (or 55.6%) of it for himself. The share of 0.444 is worth \(0.444\cdot 40=17.8\) to Cleopatra, while the share of 0.556 is worth \(0.556\cdot 50=27.8\) to Caesar. Both players end up with a total of 57.8. These results are summarized in the table below.
| Score for | Score for | Ratio | Points for | Points for | |
| Item | Caesar | Cleopatra | Caesar Cleo | Caesar | Cleopatra |
| Port of Alexandria | 30 | 20 | 1.50 | 30 | 0 |
| Legion of soldiers | 50 | 40 | 1.25 | 27.8 | 17.8 |
| Palace | 20 | 20 | 1.00 | 0 | 20 |
| Exotic poisons | 0 | 20 | 0.00 | 0 | 20 |
| Total | 100 | 100 | 57.8 | 57.8 |
In practice, it is not necessary to achieve complete equitability. A legion typically consisted of 10 centuries, each with about 100 men. Cleopatra's share of 44% could be approximated by giving her 4 of the centuries in the legion. With this division, Cleopatra's total share of the legion is worth 16 points for a total of 56, while Caesar's total adds up to 60, a division that is envy-free, relatively simple to apply, and very close to equitable.
It might be harder to divide the shared item in a real situation. In this case, an alternative possibility would be to sell the tipping point item and then share the money according to the ratios calculated in Step 6. Even though this is not ideal, it is still probably preferable to selling all the items. The key to fair division of unequal distinct items is that any envy-free division is likely to be satisfying to both players, even if it is not quite equitable. In the example with the approximate division of the legion, Cleopatra will have got 56% of her assigned values and Caesar 60%. Both will be far happier than if they each got half of each item. And they will have had to pay their mathematician far less than they would have had to pay their lawyers.