Adjusted winner procedure

Adjusted Winner (AW) is a procedure for envy-free item assignment. Given two agents and some goods, it returns a partition of the goods between the agents with the following properties:

  1. Envy-freeness: Each agent believes that his share of the goods is at least as good as the other share;
  2. Equitability: The "relative happiness levels" of both agents from their shares are equal;
  3. Pareto-optimality: no other allocation is better for one agent and at least as good for the other agent;
  4. At most one good has to be divided between the agents.

For two agent, Adjusted Winner is the only Pareto optimal and equitable that divides the minimum number of items.[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 is patented in the United States.[4] It has been commercialized through the FairOutcomes website.


[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.

Strategies

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.[6]

Limitations

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.

AW is built for two agents. 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. 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.[7] An EF+EQ allocation can be found by just giving each agent an equal amount of each good.

Software patent

AW was patented in the United States but that patent has expired.[4] Some concerns have been raised that this patent is overly broad.

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.[8]
  • 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.[9]
  • For the Spratly Islands dispute, the authors construct a two-phase procedure for settling the dispute, and present its (hypothetic) outcome.[10]
  • Other use-cases are the Panama Canal Treaties, the Jolis vs. Jolis divorce case (1980), and more.[2] :95–114

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.

gollark: Isn't there going to be significant bias from looking at *people who go to hospital*?
gollark: The government here seems to be actively refusing to say what they're planning to do.
gollark: It seems like we should have been using the time to try and come up with more permanently sustainable solutions, but this... doesn't really seem to have been happening *here*, at least.
gollark: Thoughts?
gollark: be able to last a bit without work.

See also

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. 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.
  6. "The Adjusted Winner Procedure: Characterizations and Equilibria". IJCAI-2015 proceedings.
  7. Willson, Stephen (1995). "Fair Division using Linear Programming" (PDF).
  8. 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.
  9. 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.
  10. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.