Coherence (fairness)
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Coherence, also called uniformity or consistency, is a criterion for evaluating rules for fair division. Coherence requires that the outcome of a fairness rule is fair not only for the overall problem, but also for each sub-problem. Every part of a fair division should be fair. The coherence requirement was first studied in the context of apportionment. In this context, failure to satisfy coherence is called the new states paradox: when a new U.S. state enters the union, and the number of seats in the House of Representatives is enlarged to accommodate the number of seats allocated to this new state, some other unrelated states are affected. Coherence is also relevant to other fair division problems, such as bankruptcy problems.
Background
Coherence, also called uniformity or consistency, is a criterion for evaluating rules for fair division. Coherence requires that the outcome of a fairness rule is fair not only for the overall problem, but also for each sub-problem. Every part of a fair division should be fair. The coherence requirement was first studied in the context of apportionment.
In this context, failure to satisfy coherence is called the new states paradox: when a new U.S. state enters the union, and the number of seats in the House of Representatives is enlarged to accommodate the number of seats allocated to this new state, some other unrelated states are affected. Coherence is also relevant to other fair division problems, such as bankruptcy problems. There is a resource to allocate, denoted by h . For example, it can be an integer representing the number of seats in a house of representatives.
The resource should be allocated between some n agents. For example, these can be federal states or political parties. The agents have different entitlements, denoted by a vector t_1,\ldots,t_n . For example, t i can be the fraction of votes won by party i. An allocation is a vector a_1,\ldots,a_n with \sum_{i=1}^n a_i = h . An allocation rule is a rule that, for any h and entitlement vector t_1,\ldots,t_n , returns an allocation vector a_1,\ldots,a_n .
An allocation rule is called coherent (or uniform) if, for every subset S of agents, if the rule is activated on the subset of the resource h_S := \sum_{i\in S} a_i , and on the entitlement vector (t_i)_{i\in S} , then the result is the allocation vector (a_i)_{i\in S} . That is: when the rule is activated on a subset of the agents, with the subset of resources they received, the result for them is the same. In general, an allocation rule may return more than one allocation (in case of a tie). In this case, the definition should be updated.
Denote the allocation rule by M , and Denote by M\big(h; (t_i)_{i=1}^n\big) the set of allocation vectors returned by M on the resource h and entitlement vector t_1, \ldots, t_n . The rule M is called coherent if the following holds for every allocation vector (a_i)_{i=1}^n \in M\big(h; (t_i)_{i=1}^n\big) and any subset S of agents: (a_i)_{i\in S} \in M\Big(\sum_{i\in S} a_i; (t_i)_{i\in S}\Big) . That is, every part of every possible solution to the grand problem, is a possible solution to the sub-problem.
How it works
For every (b_i)_{i\in S} \in M\Big(\sum_{i\in S} a_i; (t_i)_{i\in S}\Big) and (c_i)_{i\notin S} \in M\Big(\sum_{i\notin S} a_i; (t_i)_{i\notin S}\Big) , we have [(b_i)_{i\in S}, (c_i)_{i\notin S}] \in M\big(h; (t_i)_{i=1}^n\big) . That is, if there are other (tied) solutions to the sub-problems, then putting them instead of the original solutions to the sub-problems yield other (tied) solutions to the grand problem. One of the most intuitive rules for apportionment of seats in a parliament is the largest remainder method (LRM).
This method dictates that the entitlement vector should be normalized such that the sum of entitlements equals h (the total number of seats to allocate). Then each agent should get his normalized entitlement (often called quota) rounded down. If there are remaining seats, they should be allocated to the agents with the largest remainder the largest fraction of the entitlement. Surprisingly, this rule is not coherent. As a simple example, suppose h = 5 and the normalized entitlements of Alice, Bob and Chana are 0.4, 1.35, 3.25 respectively.
Then the unique allocation returned by LRM is 1, 1, 3 (the initial allocation is 0, 1, 3, and the extra seat goes to Alice, since her remainder 0.4 is largest). Now, suppose that we activate the same rule on Alice and Bob alone, with their combined allocation of 2. The normalized entitlements are now 0.4/1.75 × 2 ≈ 0.45 and 1.35/1.75 × 2 ≈ 1.54. Therefore, the unique allocation returned by LRM is 0, 2 rather than 1, 1.
This means that in the grand solution 1, 1, 3, the internal division between Alice and Bob does not follow the principle of largest remainders it is not coherent. Another way to look at this non-coherence is as follows. Suppose that the house size is 2, and there are two states A, B with quotas 0.4, 1.35. Then the unique allocation given by LRM is 0, 2. Now, a new state C joins the union, with quota 3.25. It is allocated 3 seats, and the house size is increased to 5 to accommodate these new seats.
This change should not affect the existing states A and B. In fact, with the LRM, the existing states are affected: state A gains a seat, while state B loses a seat. This is called the new state paradox. The new state paradox was actually observed in 1907, when Oklahoma became a state. It was given a fair share 5 of seats, and the total number of seats increased by that number, from 386 to 391 members1. After recomputation of apportionment affected the number of seats because of other states: New York lost a seat, while Maine gained one.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1360631726 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Coherence (fairness)” members (×1) · confidence 0.95 revision URL