Adjusted winner procedure

Adjusted Winner (AW) is an algorithm for envy-free item allocation. Given two parties and some discrete goods, it returns a partition of the goods between the two parties that is:

It is the only procedure that can satisfy all four properties simultaneously. Despite this, however, there are no accounts of the algorithm actually being used to resolve disputes.

The procedure was designed by Steven Brams and Alan D. Taylor, and published in their book on fair division and later in a stand-alone book. Adjusted Winning was previously patented in the United States, but expired in 2016.

Each party is given the list of goods and an equal, fixed number of points to distribute among them. They then assign values to each good and submit their (sealed) list of bids to an arbiter, who assigns each item to its highest bidder.

If the combined value of one party's goods are then greater than the other's, the algorithm then orders the higher-valued-party's goods in increasing order based on the ratio $${\displaystyle {\frac {\text{value for higher-combined-value party}}{\text{value for lower-combined-value party}}},}$$ and begins transferring them from the higher-combined value party to the lower-combined value party until their valuations are almost equal (moving any more goods would cause the lower-combined-value party to now have a higher combined value than the other). The next good is then divided between the parties such that their values become the same.

As an example, if two parties have the following valuations for four goods:

The goods would first be divided such that Alice receives good 1, while Bob receives goods 2, 3, and 4. At this point, Alice's combined valuation of her goods is 86, while Bob's is 81 + 60 + 40 = 181; as such, Bob's goods are then ordered based on the ratio ${\displaystyle {\frac {\text{Bob's valuations}}{\text{Alice's valuations}}}}$, giving

Moving Good 2 from Bob to Alice would cause Alice to have a valuation greater than Bob's (161 versus 100), so no goods are transferred. Instead, Good 2 is split between Alice and Bob: Alice receives ${\displaystyle {\frac {95}{156}}}$th of the good (approximately 60.9%), while Bob receives ${\displaystyle {\frac {61}{156}}}$th (approximately 39.1%). Their valuations now become ${\displaystyle 86+{\frac {95}{156}}(75)=131.673...}$ and ${\displaystyle 60+40+{\frac {61}{156}}(81)=131.673...}$ respectively, which are equal.