Adjusted winner procedure

Last updated
Logo Logo of Adjusted Winner.gif
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:

Contents

  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. [1] 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 [2] : 65–94  and later in a stand-alone book. [3] : 69–88  Adjusted Winning was previously patented in the United States, but expired in 2016. [4]

Algorithm

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 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. [3] : 71–74 

As an example, if two parties have the following valuations for four goods:

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 , giving

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 th of the good (approximately 60.9%), while Bob receives th (approximately 39.1%). Their valuations now become and 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

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. [2] However, Adjusted Winner always has an approximate Nash equilibrium, and under informed tie-breaking, also a pure Nash equilibrium. [1]

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, [2] : 82–83  involving three parties and their valuations:

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

Any two of these three properties can be satisfied simultaneously:

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

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

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

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, and dispute resolution. The central tenet of fair division is that such a division should be performed by the players themselves, without the need for external arbitration, as only the players themselves really know how they value the goods.

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

In economics, philosophy, and social choice theory, a person's entitlement refers to the value of goods they are owed or deserve, i.e. the total value of the goods or resources that a player would ideally receive. For example, in party-list proportional representation, a party's seat entitlement is equal to its share of the vote, times the number of seats in the legislature.

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:

<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 believed 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:

Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

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.

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.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

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

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. 1 2 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. Archived from the original on 23 May 2018.
  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. 1 2 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. ↑ Segal-Halevi, Erel (2018-07-09). "Competitive Equilibrium For almost All Incomes". Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1267–1275.
  9. ↑ Willson, Stephen J. (1995). "Fair Division using Linear Programming" (PDF). Iowa State University (unpublished manuscript).
  10. ↑ Samuel Bismuth; Ivan Bliznets; Erel Segal-Halevi (2019). "Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations". arXiv: 1912.00459 [cs.GT].
  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. pp. 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.