Adjusted Winner (AW) is an algorithm developed by Steven J. Brams and Alan D. Taylor to divide n divisible goods between two parties as fairly as possible.

The examples and other information found on this site are from the two books, Fair Division: From Cake-Cutting to Dispute Resolution (1996) and The Win-Win Solution: Guaranteeing Fair Shares to Everybody (1999), both by Brams and Taylor.

This site will
• demonstrate the AW procedure;
• provide some background information about the mathematics of fair division;
• allow you to try the algorithm; and
• provide links to information about the authors and other sites on fair division.

Clicke here to view a printer friendly version of this site (without frames and dynamic text).

This site is optimized for MS Internet Explorer.

AW starts with the designation of goods or issues in a dispute. The parties then indicate how much they value obtaining the different goods, or "getting their way" on the different issues, by distributing 100 points across them. This information, which may or may not be made public, becomes the basis for fairly dividing the goods and issues later. Once the points have been assigned by both parties (in secret), a mediator (or a computer) can use AW to allocate the goods to each party, and to determine which good (there will be at most one) that may need to be divided.

Let's illustrate the procedure with an example. Suppose Bob and Carol are getting a divorce and must divide up some of their assets. We assume that they distribute 100 points among the five items as follows:

 Item Carol Bob Retirement Account 50 40 Home 20 30 Summer Cottage 15 10 Investments 10 10 Other 5 10 Total 100 100

AW works by assigning, initially, the item to the person who puts more points on it (that person's points are underlined above). Thus, Bob gets the home, because he placed 30 points on it compared to Carol's 20. Likewise, Bob also gets the items in the "other" category, whereas Carol gets the retirement account and the summer cottage. Leaving aside the tied item (investments), Carol has a total of 65 (50 + 15) of her points, and Bob a total of 40 (30 + 10) of his points. This completes the "winner" phase of adjusted winner.

Because Bob trails Carol in points (40 compared to 65) in this phase, initially we award the investments on which they tie to Bob, which brings him up to 50 points (30 + 10 + 10). Now we will start the "adjusted" phase of AW. The goal of this phase is to achieve an equitable allocation by transferring items, or fractions thereof, from Carol to Bob until their points are equal.

What is important here is the order in which items are transferred. This order is determined by looking at certain fractions, corresponding to the items that Carol, the initial winner, has and may have to give up. In particular, for each item Carol won initially, we look at the fraction giving the ratio of Carol's points to Bob's for that item:

(Number of points Carol assigned to the item)/(Number of points Bob assigned to the item)

In our example, Carol won two items, the retirement account and the summer cottage. For the retirement account, the fraction is 50/40 = 1.25, and for the summer cottage the fraction is 15/10 = 1.50.

We start by transferring items from Carol to Bob, beginning with the item with the smallest fraction. This is the retirement account, with a fraction equal to 1.25. We continue transferring goods until the point totals are equal.

Notice that if we transferred the entire retirement account from Carol to Bob, Bob would wind up with 90 (50 + 40) of his points, whereas Carol would plunge to 15 (65 - 50) of her points. We conclude, therefore, that the parties will have to share or split the item. So our task is to find exactly what fraction of this item each party will get so that their point totals come out to be equal.

We can use algebra to find the solution. Let p be the fraction (or percentage) of the retirement account that we need to transfer from Carol to Bob in order to equalize totals; in other words, p is the fraction of the retirement account that Bob will get, and (1-p) is the fraction that Carol will get. After the transfer, Bob's point total will be 50 + 40p, and Carol's point total will be 15 + 50(1-p). Since we want the point totals to be equal, we want to choose p so that it satisfies

50 + 40p = 15 + 50(1-p)

Solving for p we get

90p = 15

p = 15/90 = 1/6

Thus, Bob should get 1/6 of the retirement account and Carol should get the remaining 5/6.

Recall that initially Bob is receiving: (1) the home (30 points), (2) the "other" items (10 points), and (3) the investments (10 points). Together with 1/6 of the retirement account, Bob's point total is now

30 + 10 + 10 + 40(1/6) = 50 + 40(1/6) 50 + 6.67 = 56.67

Recall that initially Carol is receiving: (1) the summer cottage (15 points). Together with 5/6 of the retirement account, Carol's point total is now

15 + 50(5/6) 15 + 41.67 = 56.67

Thus, each person receives exactly the same number of points, as he or she values their allocations.

Suppose that Bob and Carol want to fairly divide k goods, where k 2. We will illustrate the general description below with additional examples.

AW allocates goods as follows:

1. Each player is given 100 points to assign to each good as he/she sees fit.

2. Suppose X is sum of the points of all goods that Bob reports that he values more than Carol does. Let Y be the sum of the values of the goods that Carol reports that she values more than Bob does. Assume X Y. Assign the goods so that Bob initially gets all the goods where xi yi, and Carol gets the others.

3. List the goods in an order G1,G2,..., so that the following holds:

• Bob, based on his reported values, values goods G1,...,Gr at least as much as Carol does (i.e. xi  yi for  i   r)

• Carol, based on her reported values, values goods Gr+1,...,Gk at least as much as Bob does (i.e. yi xi for r+1   i   k)

• x1/y  x2/y  . . .    xr/yr

4. Transfer as much of G1 from Bob to Carol as needed to achieve equitability -- that is , until the point totals of the two players are equal. If the scores are not equal after transferring all of G1 to Carol, transfer as much of G2, G3, etc., as needed.

The AW procedure satisfies the following properties:

• Envy-free: Bob and Carol both believe that their portion is at least tied for largest (based on their announced valuations)

• Equitability: Bob and Carol both believe that their portion is valued the same as the other player's (based on their announced valuations)

• Efficient: There is no allocation that is strictly better for Bob (or Carol) and as good for Carol (or Bob)

## Examples

Suppose Bob and Carol are dividing three goods: A, B, and C.

1. They report the following point assignments:

 Item Bob's reported values Carol's reported value A 6 5 B 67 34 C 27 61 Total 100 100

2. X = 6+67 = 73 and Y = 61 so, initially Bob is assigned A and B, giving him 73 points, and Carol is assigned item C, giving her 61 points.

3. Since 6/5 = 1.2 and 67/34 = 1.97, order the goods: (1) A, (2) B, and (3) C.

4. We first transfer item A from Bob to Carol, so Bob has 67 points and Carol has 66 points (61 + 5). This allocation is not equitable, so we need to transfer part of item B from Bob to Carol. Let p denote the proportion of B that Bob will keep, and (1-p) the proportion that Carol will keep. Then Bob's point total will be 67p, and Carol's point total will be 61 + 5 + 34(1-p) = 100 - 34p. We will choose p so that

67p = 100 - 34p

yielding p = 100/101, which is approximately equal to 0.99.

Thus, Bob ends up with 99% of item B for a total of 66.3 of his points (67 x 0.99), whereas Carol ends up with all of item C, all of item A, and 1% of item B for a total of 66.3 of her points [61 + 5 + ( 34 x 0.01)].

Check the properties

• Envy-free: Bob would not trade his allocation for Carol's allocation, since that would give him only 33 points. Similarly, Carol would not trade her allocation for Bob's allocation, since that would give her only 34 points.

• Equitable: This property is obviously satisfied since both parties receive 66.3 points.
• Efficient: This is more difficult to show, because it requires showing that there can be no better allocation for both players. The formal proof can be found in the book Fair Division by Brams and Taylor. It should be noted that the initial allocation is efficient, since each player receives all the goods he or she most values, and the equitability adjustment step does not affect efficiency.

There are many examples of the application of AW in the Brams - Taylor books, Fair Division: From Cake-Cutting to Dispute Resolution and The Win-Win Solution: Guaranteeing Gair Shares to Everybody. They are meant to demonstrate the real-life applicability of the AW procedure. We will illustrate two examples:

1. Panama Canal Treaty Negotiations

In June 1974, the United States and Panama agreed on a treaty after two rounds of negotiations. The following point allocations are taken from The Art and Science of Negotiation (1982) by Howard Raiffa:

 Issue United States Panama 1 US defense rights 22 9 2 Use rights 22 15 3 Land and water 15 15 4 Expansion rights 14 3 5 Duration 11 15 6 Expansion routes 6 5 7 Compensation 4 11 8 Jurisdiction 2 7 9 US military rights 2 7 10 Defense role of Panama 2 13 Total 100 100

The United States wins on issues 1, 2, 4, and 6 (its points are underlined above), giving it 64 points (22 + 22 + 14 + 6), whereas Panama wins on issues 5, 7, 8, 9, and 10, giving it 53 points (15 + 11 + 7 + 7 + 13). The players tie on issue 3, which we initially give to the US for an initial allocation of 79 points.

Issue 3 has the smallest point ratio (15/15 = 1.0) and becomes the first issue used in the equitability adjustment. Let p denote the fraction of that issue that the US will retain, and (1-p) the proportion that Panama will retain; then p must satisfy the following equation

64 + 15p = 53 + 15(1 - p)

Solving for p, we find that p= 4/30 = 2/15. Thus, the United States should get 13.3 percent of its position (2 points), and Panama 86.7 percent of its position (13 points) on issue 3 to equalize their point totals. This results in the United States and Panama receiving each receiving 66 of their points.

2. A Hypothetical Divorce Settlement

Divorces may be not only bitter and acrimonious but also very costly to the two parties as lawyers' fees accumulate. The following hypothetical divorce will illustrate how AW could be used to save heartache and money.

It is presented in Negotiating to Settlement in Divorce (1987, pp. 166 - 169), a manual for lawyers. Suppose Bob and Carol have decided to get a divorce. There are three major issues to be resolved: custody, alimony, and the house. Bob and Carol assign points as specified in the table below. Put the mouse over the numbers to see the justification for the point assignment. The justifications are quotations taken from Negotiating to Settlement in Divorce.

 Item Bob Carol Custody (sole) 23 65 Alimony 60 25 House 15 10 Total 100 100

Under AW, Carol wins sole custody of John (their son), whereas Bob gets his way on alimony, and, initially, gets the house. However, Bob ends up with 75 points (60 + 15) and Carol with only 65 points. So Bob must give back some points on the house, which has the smallest ratio of Bob's points to Carol's points (15/10 = 1.5).

Let p denote the proportion that Bob will retain, and (1-p) the proportion that Carol will retain. Then p must satisfy the following equation:

60 + 15p = 65 + 10(1 - p)

Solving for p gives p = 15/25 = 3/5. So Bob is entitled to 60 percent, and Carol to 40 percent, of the house. In terms of points, Bob will get 69 points [60 + 15(3/5) = 60 + 9 = 69], and so will Carol [65 + 10(2/5) = 65 + 4 = 69].

## Manipulation

While the AW procedure has each party assign points independently,how can one know that the announced point assignments reflect each party's true valuations? There are certain situations, such as a divorce proceeding, in which each person will have more than an inkling of the preferences of the other person. Indeed, the intimate knowledge that a divorcing couple will have of each other's cares and concerns will frequently enable each to make rather accurate estimates of the points that the other spouse is likely to assign to the items in a divorce.

Thus we are led to ask whether the parties under AW can capitalize on their knowledge of each other's preferences. It turns out that if this knowledge is possessed by only one side -- a relatively unlikely scenario -- then the knowledgeable side can, in fact, exploit its informational advantage. However, if knowledge is roughly symmetric, then attempts by both sides to be strategic can lead to disaster, even without each spouse's being spiteful.

To illustrate this, let's start with a simple example. Suppose there are two paintings, a Matisse and a Picasso, and Carol thinks that the Matisse is worth three times as much as the Picasso, whereas Bob thinks the Picasso is worth three times as much as the Matisse. Thus, if Carol and Bob are sincere, then there point assignments will be as follows:

 Matisse Picasso Total Carol's true valuations 75 25 100 Bob's true valuations 25 75 100

Because of the symmetry in the preceding example, Carol will receive the Matisse and Bob will receive the Picasso, and there will be no need for an equability adjustment: both parties will receive 75 points.

Now suppose that Carol knows Bob's preferences, and that Bob does not know Carol's preferences. In the absence of any additional information, Bob will announce his true valuation (75 points for the Picasso and 25 points for the Matisse). Can Carol benefit from her knowledge?

The answer is yes. Carol should pretend that she likes the Matisse only slightly more than Bob likes the Matisse. This way, Carol will get all of the Matisse as she did before, but it will appear that she is getting only a little more than one-fourth of her total value, whereas Bob is getting three-fourths of his value (since he put 75 points on the Picasso). Consequently, a big equability adjustment will be required to transfer much of the value of the Picasso from Bob to Carol.

To be more precise, let's work from the numbers in this example to see the extent to which Carol can manipulate AW to her advantage. Knowing that Bob will place 25 points on the Matisse, Carol should place 26 points on this item and her remaining 74 points on the Picasso. Hence, the announced point totals, assuming Bob is sincere and Carol is not, will be as follows:

 Matisse Picasso Total Carol's announced valuations 26 74 100 Bob's true valuations 25 75 100

Initially Carol will get the Matisse, receiving 26 of her announced points, and Bob will get the Picasso, receiving 75 of his announced (and sincere) points. But now, since it appears that Bob is getting almost three times as many points as Carol does (75 to 26), there must be a large transfer from Bob to Carol.

The exact amount will be determined by solving the following equation for p.

26 + 74p = 75 - 75p

Solving for p, we find

149p = 49

p = 49/149 0.33

This gives Bob, in particular,

75 - 75(0.33) 75 - 25 = 50

of his points. In fact, it will appear that Carol, also, is getting the same low number of points

26 + 74(0.33) 26 + 24 = 50

However, let's consider Carol's true valuations. She is getting 75 points from winning all of the Matisse; in addition, she is getting 33% of the Picasso that she values at 25 points, which might mean that Bob would have to pay Carol one-third of the assessed value of the Picasso to keep it entirely for himself. Altogether, then, Carol is getting

75 + 25(0.33) 75 + 8.33 = 83.33

of her points. Of course, Bob could exploit Carol in the same manner if it were he, rather than Carol, who had one-sided information and capitalized on his knowledge of her preferences.

## How to Optimally Deceive Bob

This section will let you test your ability to deceive Bob. Suppose Bob and Carol are arguing over two items (A and B). Let Carol's valuation of these items be 70 points for A and 30 points for B, and Bob's valuation of these items be 50 points for A and 50 points for B.

Now suppose that Carol knows that Bob's valuation is 50-50, and Bob does not know Carol's valuation. What should Carol announce in order to maximize her total point allocation (valuations are restricted to integers)?

Enter the values that you think Carol should announce in order to deceive Bob. Hit the "What is the total point allocation?" button to see the outcome of your allocation. Scroll down to see the answer.

Carol should announce for item A

Carol should announce for item B

Carol should announce 51 points for item A and 49 points for item B . Since it appears that Carol has only has a slight advantage over Bob, only a trivial fraction (1/101) of A will be transfered to Bob. Thereby Carol will end up with a generous 70 - 0.7 = 69.3 points (according to here true valuations).

As we have shown, a possible drawback of AW is that one player (with complete information) can exploit another player (without such information). In fact, the optimal response for any player is completely determined by the following theorem, which is proved in Fair Division.

Theorem: Assume there are two goods, G1 and G2, and all true and announced valuations are restricted to integers. Suppose Bob's announced valuation of G1 is x, where x 50, and suppose Carol's true valuation of G1 is b. Then Carol's optimal announced valuation of G1 is:

 x + 1 if b > x x if b = x x = 1 if b < x

What if the goods are not divisible?

Under AW, the only good or issue that must be divided is that on which an equitability adjustment is made. This will not be known in advance but only after the application of AW, so all goods and issues must be considered potentially divisible. In applying AW, probably the biggest problem is identifying a set of separable issues on which points are additive.

If the items being divided are not tangible property but more intangible issues, then the parties should decide before AW is applied what each would obtain if it came out the winner on an issue. Only on the one issue on which an equitability adjustment must be made will a finer breakdown actually be necessary.

This is a situation in which a mediator could play a valuable role. He or she could tell the parties the split on this issue but not which party is the relative winner. Each party, not knowing whether it got the larger or the smaller percentage, would then be motivated to reach a fair-minded agreement. This could mean that one party could win entirely on that issue, or receive all of a good, but in turn it would have to pay the other party an agreed-upon amount.

When exactly should AW be used?

We suggest that AW first be tried out in negotiations that involve easily specified issues or well-defined goods. Examples might include a dispute within a company over the division of job responsibilities, or the division of marital property in a divorce settlement, as illustrated in the examples page. If the procedure works well in these settings, it might be used in more complex negotiations.

We focused on divorce settlements because of the sheer magnitude of the problem -- half of all marriages end in divorce in the United States. AW, in our view, provides a straightforward settlement device that takes due account of the interests of both parties. Since the settlement is not the product of protracted negotiations or court battles, it is likely to lead to a more satisfying and durable outcome as well as foster more civil future relations between the parties, which is especially important if children are involved.

But divorce settlements are not the only domain in which the application of AW seems desirable. In the political arena, negotiations over arms control or border disputes often involve a plethora of issues that AW could help to resolve. In the economic sphere, negotiations between labor and management over a new contract, or between two companies over a merger, are usually sufficiently complex that a point-allocation procedure could, we believe, prove very useful in finding a settlement that mirrors each side's most salient concerns.

All in all, what should I know before I attempt to use AW?

• AW is easily applied to goods but less easily to issues, in which much negotiation must precede its use. In applying AW to goods in, say, a divorce or estate division, the only real difficulty is in each person's assigning points to the goods. If the items are not physical goods but issues that must be resolved, then the parties need to reach agreement - before the application of AW can even begin - on not only what the issues are but also what winning and losing on each issue means. Because there is no mechanical procedure that can resolve difference at this level, this is the area in which a good deal of hard bargaining is to be expected.
• The packaging of issues is crucial in applying AW, particularly breaking up a single large issue into different parts that are as separable as possible. Thus, if salary is the overriding concern in a labor-management dispute, then there is nothing to trade off against losing on this issue. But often an issue like this can be broken down into components, such as basic hourly or piecework rate, overtime wages, pensions, medical benefits, and the like that the employer and the employee value differently. Hence, "salary" is turned into a compensation package, and its components can be treated as separate issues. Care must be taken in packaging items, however, so as to make them relatively independent of each other. This is to ensure that winning on one does not affect how much one wins on another; otherwise, the summation of points across all items would not be meaningful.

• Manipulation is sufficiently difficult under AW so as not to be a practical problem. One catch in using AW is that, theoretically, one side can do even better, at the expense of the other side, by capitalizing on its advance knowledge of the other side's allocations. This is not usually a serious practical problem, however, because it is highly unlikely that one side would have the precise information it needs about the other side's allocations to exploit AW in this manner. In fact, although being off by only one point can lead to a relatively poor outcome for both parties, the honest party's sincerity guarantees that it will not envy the disingenuous party. Thus, the incentives to exploit AW will be minimal, with honesty guaranteeing a party at least half its total valuation of all items.

Given the simplicity of AW, would we need to hire a lawyer in a divorce?

The fact that AW may circumvent litigation that drags on in court and drains husbands and wives of their resources may be a social good, but it will not delight lawyers if it robs them of legal fees. We believe, however, that lawyers can play a valuable role in AW's use by

• helping their clients make their point assignments in a way that reflects their honest estimates of worth, thereby enabling them to obtain better settlements;
• assisting them in predicting possible outcomes, perhaps by anticipating the allocations of the other party and running through various scenarios they might face, so as to reduce certainty.

Of course, it will remain for lawyers and courts to determine what constitutes marital property, to which AW can then be applied.

How will I come up with the point assignments?

While honesty usually pays, it will not always be a simple matter to come up with point assignments that mirror one's valuations of the different issues. One way to facilitate this task is to have the parties begin by ranking the issues, from most to least important, in terms of their desire to get their way on each.

After the issues have been ranked, the parties face the problem of turning a ranking into point assignments that reflect their intensities of preferences for the different issues. In The Art and Science of Negotiation (1982), decision analyst Howard Raiffa discusses this problem in considerable detail, essentially concluding that a party must carefully weigh how much it would be willing to give up on one issue to obtain more on another.

To come up with point assignments, one option for a party would be to begin by rating the importance of winning on its highest-ranked issue, compared with its next-highest-ranked issue, by specifying a ratio. Continuing down the list, comparing the second-highest-ranked issue with the third-highest-ranked issue, and so on, parties would indicate, in relative terms, an "importance ratio" between adjacent issues.

For example, if there are three issues, and the importance ratios are 2:1 on the first issue relative to the second, and 3:2 on the second issue relative to the third, these will translate into a 6:3:2 proportion over the three issues. Rounding to the nearest integer, the point assignments would be 55, 27, and 18, respectively, on the three issues. A more systematic method for eliciting weightings, pioneered by mathematician Thomas L. Saaty and his associates and called "analytic hierarchy processing," could also be used.

Another option for a party is to begin by assigning points intuitively to items. These assignments could be "tested" by asking whether various 50-point packages represent half the total value. To the extent that they do not, the initial point assignments for items would need to be modified. This process would continue until a party is satisfied that no further adjustments in its allocations of points to each item are necessary.

Will AW work with more than two players?

When there are more than two parties, there is no procedure that will simultaneously satisfy envy-freeness, efficiency, and equitability (see below for an example). However, it turns out that it is always possible to find an allocation that satisfies two of the three properties: A procedure that gives both efficiency and envy-freeness has been obtained by Dutch mathematicians J.H. Reijnierse and J.A.M. Potters; procedures (called "linear programs") that give both efficiency and equitability have been obtained by American mathematician Stephen J. Willson; and an equal division of each item to the parties gives both equitability and envy-freeness.

The following example, given by J.H. Reijnierse and J.A.M. Potters, demonstrates the impossibility of satisfying all three properties (efficiency, envy-freeness, and equitability). Suppose there are three disputants named Ann, Bob, and Carol, and assume that they allocate the following numbers of points to items X, Y, and Z:

 Items Ann Bob Carol X 40 30 30 Y 50 40 30 Z 10 30 40

The only efficient and equitable allocation turns out to be to give X to Ann, Y to Bob and Z to Carol. Obviously, this 40-40-40 allocation is equitable; it can also be shown to be efficient.

But it is not envy-free, because Ann will envy Bob for getting Y, which Ann considers to be worth 50 points. If we gave Y to Ann and X to Bob while still giving Z to Carol, this allocation would be efficient, but it would be neither equitable (because each player would get a different number of his or her points) nor envy-free (because Bob would envy Ann).

Of course, this three-person hypothetical example does not preclude the possibility that all three properties can be satisfied in a particular situation; it says only that it is not always possible to guarantee their satisfaction when there are more than two parties. The fact that one cannot guarantee the satisfaction of efficiency, envy-freeness, and equitability, however, means that a hard choice might have to be made among them in situations with more than two parties.

I heard that the AW algorithm is patented, is this true?

Yes, the algorithm was patented in 1999 (patent number 5,983,205).