Adjusted winner procedure

Last updated

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:

Contents

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

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:

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.

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.

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.

Related Research Articles

Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inheritance, partnership dissolutions, divorce settlements, electronic frequency allocation, airport traffic management, and exploitation of Earth observation satellites. It is an active research area in mathematics, economics, dispute resolution, etc. The central tenet of fair division is that such a division should be performed by the players themselves, maybe using a mediator but certainly not an arbiter as only the players really know how they value the goods.

Divide and choose is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource and two partners who have different preferences over parts of the cake. The protocol proceeds as follows: one person cuts the cake into two pieces; the other person selects one of the pieces; the cutter receives the remaining piece.

Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. In many fair division settings, all agents have equal entitlements, which means that each agent is entitled to 1/n of the resource. But there are practical settings in which agents have different entitlements. Some examples are:

Equitability is a criterion for fair division. A division is called equitable if the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners i and j:

The surplus procedure (SP) is a fair division protocol for dividing goods in a way that achieves proportional equitability. It can be generalized to more than 2=two people and is strategyproof. For three or more people it is not always possible to achieve a division that is both equitable and envy-free.

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece that he or she believes to be a fair share.

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

The fair pie-cutting problem is a variation of the fair cake-cutting problem, in which the resource to be divided is circular.

Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners i and j:

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

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. 1 2 3 4 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. ↑ "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)
  5. ↑ U.S. Patent 5,983,205 , Computer-based method for the fair division of ownership of goods.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ "The Adjusted Winner Procedure: Characterizations and Equilibria". IJCAI-2015 proceedings.
  10. ↑ Willson, Stephen J. (1995). "Fair Division using Linear Programming" (PDF). Iowa State University (unpublished manuscript).{{cite web}}: CS1 maint: url-status (link)
  11. ↑ 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.
  12. ↑ 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: 53–59. doi: 10.24963/ijcai.2019/8 . ISBN   978-0-9992411-4-1. S2CID   197468732.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.