View source for Adjusted winner procedure

{{Short description|Method of fairly dividing property}}
{{primary|date=February 2024}}
[[File:Logo of Adjusted Winner.gif|thumb|Logo]]
'''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:
# [[Envy-free]]: Each party believes their share of the goods is as good as or better than their opponent's;
# [[Equitable division|Equitable]]: The "relative happiness levels" of both parties from their shares are equal;
# [[Pareto-optimal]]: no other allocation is better for one party and still at least as good for the other party; and
# Involves splitting at most one good between the parties.

It is the only procedure that can satisfy all four properties simultaneously.<ref name=Aziz>{{Cite book|last1=Aziz|first1=Haris.|last2=Brânzei|first2=Simina|last3=Filos-Ratsikas|first3=Aris|last4=Søren Kristoffer Stiil|first4=Søren|date=2015|chapter=The Adjusted Winner Procedure: Characterizations and Equilibria|title=Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence|language=en|pages=454–460|chapter-url=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/download/11147/10727|bibcode=2015arXiv150306665A|arxiv=1503.06665|archive-url=https://web.archive.org/web/20180523095344/http://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/download/11147/10727 |archive-date=23 May 2018 }}</ref> 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<ref name=":0">{{Cite Brams Taylor 1996}}</ref>{{Rp|65–94}} and later in a stand-alone book.<ref name="winwin">{{Cite book|title=The Win-Win Solution: Guaranteeing Fair Shares to Everybody|last=Steven J. Brams and Alan D. Taylr|publisher=Norton|year=2000|isbn=978-0393320817|url-access=registration|url=https://archive.org/details/winwinsolutiongu00stev}}</ref>{{rp|69-88}} Adjusted Winning was previously patented in the United States, but expired in 2016.<ref name="patent">{{US patent|5983205}}, ''Computer-based method for the fair division of ownership of goods''.</ref>

== Algorithm ==
{{unsourced|section|date=February 2024}}
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 <math display="block">\frac{\text{value for higher-combined-value party}}{\text{value for lower-combined-value party}},</math> 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.<ref name="winwin"/>{{rp|71-74}}

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 <math>\frac{\text{Bob's valuations}}{\text{Alice's valuations}}</math>, giving
* [Good 2 = <math>\frac{81}{75}</math>], [Good 3 = <math>\frac{60}{30}</math>], [Good 4 = <math>\frac{40}{9}</math>].
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 <math>\frac{95}{156}</math>th of the good (approximately 60.9%), while Bob receives <math>\frac{61}{156}</math>th (approximately 39.1%). Their valuations now become <math>86 + \frac{95}{156}(75) = 131.673...</math> and <math>60 + 40 + \frac{61}{156}(81) = 131.673...</math> 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;<ref>{{Cite journal|last1=Brams|first1=Steven J.|last2=Togman|first2=Jeffrey M.|date=1996|title=Camp David: Was The Agreement Fair?|journal=Conflict Management and Peace Science|language=en|volume=15|issue=1|pages=99–112|doi=10.1177/073889429601500105|s2cid=154854128|issn=0738-8942}}</ref>
* For the [[Israeli–Palestinian conflict]];<ref>{{Cite journal|last=Massoud|first=Tansa George|date=2000-06-01|title=Fair Division, Adjusted Winner Procedure (AW), and the Israeli-Palestinian Conflict|journal=Journal of Conflict Resolution|language=en|volume=44|issue=3|pages=333–358|doi=10.1177/0022002700044003003|s2cid=154593488|issn=0022-0027}}</ref>
* For the [[Spratly Islands dispute]];<ref>{{Cite journal|last1=Denoon|first1=D. B. H.|last2=Brams|first2=S. J.|date=1997-02-01|title=Fair Division: A New Approach to the Spratly Islands Controversy|journal=International Negotiation|language=en|volume=2|issue=2|pages=303–329|doi=10.1163/15718069720847997|issn=1571-8069}}</ref>
* the [[Panama Canal Treaties]]; and
* the 1980 ''Jolis v. Jolis'' divorce case.<ref name=":0" />{{Rp|95–114}}

== 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.<ref name=":0" /> However, Adjusted Winner always has an approximate [[Nash equilibrium]], and under informed tie-breaking, also a pure Nash equilibrium.<ref name=Aziz />

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 utility|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,<ref name=":0" />{{Rp|82–83}} 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.<ref>{{Cite journal |last=Segal-Halevi |first=Erel |date=2018-07-09 |title=Competitive Equilibrium For almost All Incomes |url=https://dl.acm.org/doi/abs/10.5555/3237383.3237887 |journal=Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems |series=AAMAS '18 |location=Richland, SC |publisher=International Foundation for Autonomous Agents and Multiagent Systems |pages=1267–1275}}</ref>

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]].<ref>{{Cite web |last=Willson |first=Stephen J. |date=1995 |title=Fair Division using Linear Programming |url=https://swillson.public.iastate.edu/FairDivisionUsingLPUnpublished6.pdf |website=Iowa State University (unpublished manuscript)}}</ref><ref>{{Cite arXiv |eprint=1912.00459 |author1=Samuel Bismuth |author2=Ivan Bliznets |title=Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations |author3=Erel Segal-Halevi|date=2019 |class=cs.GT }}</ref>
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.<ref>{{Cite journal |last1=Sandomirskiy |first1=Fedor |last2=Segal-Halevi |first2=Erel |date=2022-05-01 |title=Efficient Fair Division with Minimal Sharing |url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.2279 |journal=Operations Research |volume=70 |issue=3 |pages=1762–1782 |doi=10.1287/opre.2022.2279 |arxiv=1908.01669 |s2cid=247922344 |issn=0030-364X}}</ref>

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.<ref>{{Cite book |last1=Aziz |first1=Haris |last2=Caragiannis |first2=Ioannis |last3=Igarashi |first3=Ayumi |last4=Walsh |first4=Toby |title=Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence |chapter=Fair Allocation of Indivisible Goods and Chores |date=2019-08-01 |pages=53–59 |location=California |publisher=International Joint Conferences on Artificial Intelligence Organization |doi=10.24963/ijcai.2019/8|isbn=978-0-9992411-4-1 |s2cid=197468732 |doi-access=free }}</ref>

== 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.{{how|date=February 2024}} 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 ==
{{reflist}}

==External links==
* [https://pages.nyu.edu/adjustedwinner/ Website explaining Adjusted Winner]

{{DEFAULTSORT:Adjusted Winner Procedure}}
[[Category:Fair division protocols]]
[[Category:Dispute resolution]]