Equitability

Last updated

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:

Contents

Where:

Comparison to other criteria

The following table illustrates the difference. In all examples there are two partners, Alice and Bob. Alice receives the left part and Bob receives the right part.

DivisionEQ?EF?EX?
A:50%50%
B:50%50%
Yes check.svgYes check.svgYes check.svg
A:60%40%
B:40%60%
Yes check.svgYes check.svgDark Red x.svg
(Alice and Bob don't agree on the values of the pieces).
A:40%60%
B:60%40%
Yes check.svgDark Red x.svg
(Alice and Bob envy each other's share).		Dark Red x.svg
A:70%30%
B:40%60%
Dark Red x.svg
(Alice enjoys her share more than Bob enjoys his share).		Yes check.svgDark Red x.svg
A:60%40%
B:60%40%
Dark Red x.svgDark Red x.svg
(Bob envies Alice).		Yes check.svg
A:60%40%
B:70%30%
Dark Red x.svgDark Red x.svgDark Red x.svg

Note that the table has only 6 rows, because 2 combinations are impossible: an EX+EF division must be EQ, and an EX+EQ division must be EF.

Existence and computation

Equitability has been mainly applied in the division of a heterogeneous continuous resource; see Equitable cake-cutting.

It has also been applied in the division of homogeneous resources; see Adjusted winner procedure.

Recently, it has also been studied in the context of fair item allocation. With indivisible items, an equitable allocation might not exist, but it can be approximated in several ways. For example, an allocation is called EQ1 if the difference between subjective valuations is at most a single item. It was studied for goods, [1] for chores, [2] for a goods on a path, [3] and in conjunction with utilitarian optimality. [4]

Related Research Articles

In game theory, fair division is the problem of dividing a set of resources among several people who have an entitlement to them, such that each person receives their due share. This 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. This is an active research area in mathematics, economics, dispute resolution, and more. 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.

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.

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 two 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 shared between the agents.
Fair cake-cutting 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.

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 a fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who 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:

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

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.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

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.

The Probabilistic Serial rule (PS), also called serial eating algorithm, is a rule for fair random assignment. It yields a randomized allocation of indivisible items among several agents that is ex-ante envy-free and Pareto efficient. It was developed by Hervé Moulin and Anna Bogomolnaia.

Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into n parts and taking the part with the minimum value.

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.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.

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 house and two people, and the house must be given entirely to one of them, the allocation will be unfair towards the other one. With monetary transfers, it is possible to attain fairness using the following simple algorithm :

References

  1. ↑ Freeman, Rupert; Sikdar, Sujoy; Vaish, Rohit; Xia, Lirong (2019-05-25). "Equitable Allocations of Indivisible Goods". arXiv: 1905.10656 [cs.GT].
  2. ↑ Freeman, Rupert; Sikdar, Sujoy; Vaish, Rohit; Xia, Lirong (2020-02-24). "Equitable Allocations of Indivisible Chores". arXiv: 2002.11504 [cs.GT].
  3. ↑ Misra, Neeldhara; Sonar, Chinmay; Vaidyanathan, P. R.; Vaish, Rohit (2021-01-26). "Equitable Division of a Path". arXiv: 2101.09794 [cs.GT].
  4. ↑ Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (2021-06-01). "Computing Welfare-Maximizing Fair Allocations of Indivisible Goods". arXiv: 2012.03979 [cs.GT].
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.