Adjusted winner procedure
Adjusted Winner (AW) is a procedure for envy-free item allocation. Given two agents and some goods, it returns a partition of the goods between the two agents with the following properties:
- Envy-freeness: Each agent believes that his share of the goods is at least as good as the other share;
- Equitability: The "relative happiness levels" of both agents from their shares are equal;
- Pareto-optimality: no other allocation is better for one agent and at least as good for the other agent;
- At most one good has to be shared between the agents.
For two agents, Adjusted Winner is the only Pareto optimal and equitable procedure that divides at most a single good.[1]
The procedure can be used in divorce settlements and partnership dissolutions, as well as international conflicts.
The procedure was designed by Steven Brams and Alan D. Taylor. It was first published in their book on fair division[2]: 65–94 and later in a stand-alone book.[3]
The algorithm has been commercialized through the FairOutcomes Archived 2019-03-05 at the Wayback Machine [4] website. AW was patented in the United States but that patent has expired.[5]
Method
Each partner is given the list of goods and an equal number of points (e.g. 100 points) to distribute among them. He or she assigns a value to each good and submits it sealed to an arbiter.
The arbiter, or a computer program, assigns each item to the high bidder. If both partners have the same number of points, then we are done. Otherwise, call the partner who has more points "winner" and the other partner "loser".
Order the goods in increasing order of the ratio value-for-winner / value-for-loser. Start moving goods in this order from the winner to the loser, until the point-totals become "almost" equal, i.e., moving one more good from the winner to the loser will make the winner have less points than the loser.
At this point, divide the next good between the winner and the loser such that their totals are the same.
Use cases
While there is no account of AW actually being used to resolve disputes, there are several counterfactual studies checking what would have been the results of using this procedure to solve international disputes.
- For the Camp David Accords, the authors construct approximate numeric valuation functions for Israel and Egypt, based on the relative importance of each issue for each country. They then run the AW protocol. The theoretical results are very similar to the actual agreement, which leads the authors to conclude that the agreement is as fair as it could be.[6]
- For the Israeli-Palestinian conflict, the author constructs the valuation functions based on a survey of expert opinions, and describes the agreement that would result from running the AW protocol with these valuations.[7]
- For the Spratly Islands dispute, the authors construct a two-phase procedure for settling the dispute, and present its (hypothetic) outcome.[8]
- Other use cases are the Panama Canal Treaties, the Jolis v. Jolis divorce case (1980), and more.[2]: 95–114
Limitations
AW is not a truthful mechanism – the partners might gain from spying after their partners and modifying their reports in order to get a larger share. However, the authors claim that such manipulation can be difficult to carry out, so in practice, using this method would encourage honesty.[2] AW always has an approximate Nash equilibrium. Under informed tie-breaking, it also has a pure Nash equilibrium.[9]
As patented, AW assumes that the partners have additive utility functions, so that the utility of a set of goods is the sum of utilities of the goods. It does not handle, for example, multiple identical assets with diminishing marginal utility.
Three or more agents
AW is designed for two agents only. When there are three or more agents, there may be no allocation that is simultaneously envy-free, equitable and Pareto-optimal. This is shown by the following example, constructed by J.H.Reijnierse.[2]: 82–83 There are three goods and three agents with the following points:
- Alice: 40, 50, 10
- Bob: 30, 40, 30
- Carl: 30, 30, 40
It is possible to show that the only PO and equitable allocation is the one that gives good 1 to Alice, good 2 to Bob and good 3 to Carl. The equitable value in this case is 40. However, this allocation is not envy-free since Alice envies Bob.
Each two of these three properties can be satisfied simultaneously.
- An EF+EQ allocation can be found by just giving each agent an equal amount of each good.
- PO+EF allocations can be found by several algorithms; see Pareto-efficient envy-free division and also Weller's theorem.
- PO+EQ allocations can be found by linear programming.[10]
Moreover, it is possible to find an allocation that, subject to being PO+EF (or PO+EQ), minimizes the number of objects that have to be shared between two or more agents, or the amount of sharing. This can be seen as a proper generalization of the AW procedure to three or more agents.[11]
Positive and negative valuations
AW is designed for agents with positive valuations over the items. Aziz, Caragiannis, Igarashi and Walsh[12] present a generalization of AW that works also for agents with mixed (positive and negative) valuations.
Related procedures
The Brams–Taylor procedure was designed by the same authors, but it is different – it is a procedure for envy-free cake-cutting. While AW handles homogeneous goods, the BT procedure handles a heterogeneous resource ("cake") which is much more challenging. Accordingly, BT guarantees only envy-freeness – it does not guarantee equitability or Pareto-optimality.
The article on Fair division experiments describes some laboratory experiments comparing AW to related procedures.
References
- ^ 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.
- ^ a b c d Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9.
- ^ Steven J. Brams and Alan D. Taylr (2000). The Win-Win Solution: Guaranteeing Fair Shares to Everybody. Norton. ISBN 978-0393320817.
- ^ "Fair Outcomes, Inc". Archived from the original on 2019-03-05. Retrieved 2022-02-27.
{{cite web}}: CS1 maint: bot: original URL status unknown (link) - ^ U.S. patent 5,983,205, Computer-based method for the fair division of ownership of goods.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ "The Adjusted Winner Procedure: Characterizations and Equilibria". IJCAI-2015 proceedings.
- ^ Willson, Stephen J. (1995). "Fair Division using Linear Programming" (PDF). Iowa State University (unpublished manuscript).
- ^ 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.
- ^ 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.