Misplaced Pages

This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: "Adjusted winner procedure" – news · newspapers · books · scholar · JSTOR (February 2024) (Learn how and when to remove this message)

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:

1. Envy-free: Each party believes their share of the goods is as good as or better than their opponent's;
2. Equitable: The "relative happiness levels" of both parties from their shares are equal;
3. Pareto-optimal: no other allocation is better for one party and still at least as good for the other party; and
4. Involves splitting at most one good between the parties.

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.

Algorithm

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Adjusted winner procedure" – news · newspapers · books · scholar · JSTOR (February 2024) (Learn how and when to remove this message)

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:

• Alice: 86, 75, 30, 9
• Bob: 19, 81, 60, 40

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

• [Good 2 = ${\displaystyle {\frac {81}{75}}}$], [Good 3 = ${\displaystyle {\frac {60}{30}}}$], [Good 4 = ${\displaystyle {\frac {40}{9}}}$].

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.

Simulations

There are no cases of Adjusted Winner being used to resolve real-life disputes. However, some studies have simulated how certain disputes would have resulted had the algorithm been used, including

• the Camp David Accords, whose valuation functions were modelled on the relative importance of each issue for Israel and Egypt, and whose theoretical results were similar to the actual agreement;
• For the Israeli–Palestinian conflict;
• For the Spratly Islands dispute;
• the Panama Canal Treaties; and
• the 1980 Jolis v. Jolis divorce case.

Limitations

AW is not a truthful mechanism: a party can gain from spying on its opponent and modifying their reports in order to get a larger share. However, Adjusted Winner always has an approximate Nash equilibrium, and under informed tie-breaking, also a pure Nash equilibrium.

As patented, the algorithm assumes the parties have additive utility functions: the value of their goods is equal to the sum of the individual goods' values. It does not handle, for example, multiple instances of a good with diminishing marginal utilities.

The algorithm also is designed for two parties only; when there are three or more parties, there may be no allocation that is simultaneously envy-free, equitable, and Pareto-optimal. This can be shown by the following example, constructed by J.H.Reijnierse, involving three parties and their valuations:

• Alice: 40, 50, 10
• Bob: 30, 40, 30
• Carl: 30, 30, 40

The only Pareto-optimal and equitable allocation would be the one giving good 1 to Alice, good 2 to Bob, and good 3 to Carl; however, this allocation would not be envy-free since Alice would envy Bob.

Any two of these three properties can be satisfied simultaneously:

• An envy-free and equitable allocation could be found by giving each party an equal amount of each good.
• An envy-free and Pareto-optimal allocation could be found via Pareto-efficient envy-free division or Weller's theorem.
• An equitable and Pareto-optimal allocation could be found via linear programming.

Moreover, it is possible to find an allocation that, while being Pareto-optimal/envy-free or Pareto-optimal/equitable, would minimize the number of objects that have to be shared between two or more parties. This it usually considered the generalization of the Adjusted Winner procedure to three or more parties.

Adjusted Winner is designed for agents with positive valuations over the items. It can be generalized for parties with mixed (positive and negative) valuations, however.

Related procedures

The Brams–Taylor procedure was designed by the same authors, but it is instead a procedure for envy-free cake-cutting: it handles heterogeneous resources ("cake") which are more challenging to divide than Adjusted Winning's homogeneous goods. Accordingly, BT guarantees only envy-freeness, not any other attributes.

The article on Fair division experiments describes some laboratory experiments comparing AW to related procedures.

References

1. ^ Aziz, Haris.; Brânzei, Simina; Filos-Ratsikas, Aris; Søren Kristoffer Stiil, Søren (2015). "The Adjusted Winner Procedure: Characterizations and Equilibria". Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. pp. 454–460. arXiv:1503.06665. Bibcode:2015arXiv150306665A.
2. ^ Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9.
3. ^ Steven J. Brams and Alan D. Taylr (2000). The Win-Win Solution: Guaranteeing Fair Shares to Everybody. Norton. ISBN 978-0393320817.
4. U.S. patent 5,983,205, Computer-based method for the fair division of ownership of goods.
5. Brams, Steven J.; Togman, Jeffrey M. (1996). "Camp David: Was The Agreement Fair?". Conflict Management and Peace Science. 15 (1): 99–112. doi:10.1177/073889429601500105. ISSN 0738-8942. S2CID 154854128.
6. Massoud, Tansa George (2000-06-01). "Fair Division, Adjusted Winner Procedure (AW), and the Israeli-Palestinian Conflict". Journal of Conflict Resolution. 44 (3): 333–358. doi:10.1177/0022002700044003003. ISSN 0022-0027. S2CID 154593488.
7. Denoon, D. B. H.; Brams, S. J. (1997-02-01). "Fair Division: A New Approach to the Spratly Islands Controversy". International Negotiation. 2 (2): 303–329. doi:10.1163/15718069720847997. ISSN 1571-8069.
8. Willson, Stephen J. (1995). "Fair Division using Linear Programming" (PDF). Iowa State University (unpublished manuscript).
9. Samuel Bismuth; Ivan Bliznets; Erel Segal-Halevi. "Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations". arXiv:1912.00459.
10. Sandomirskiy, Fedor; Segal-Halevi, Erel (2022-05-01). "Efficient Fair Division with Minimal Sharing". Operations Research. 70 (3): 1762–1782. arXiv:1908.01669. doi:10.1287/opre.2022.2279. ISSN 0030-364X. S2CID 247922344.
11. Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (2019-08-01). "Fair Allocation of Indivisible Goods and Chores". Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization. pp. 53–59. doi:10.24963/ijcai.2019/8. ISBN 978-0-9992411-4-1. S2CID 197468732.

External links

• Website explaining Adjusted Winner

• Fair division protocols
• Dispute resolution