Coherence,
also called uniformity
or consistency, is a criterion for evaluating rules for
fair division
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 inh ...
. 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
The legal term apportionment (french: apportionement; Mediaeval Latin: , derived from la, portio, share), also called delimitation, is in general the distribution or allotment of proper shares, though may have different meanings in different c ...
. In this context, failure to satisfy coherence is called the new states paradox: when a new state enters the union, and the house size 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 problem
A bankruptcy problem, also called a claims problem, is a problem of distributing a homogeneous divisible good (such as money) among people with different claims. The focus is on the case where the amount is insufficient to satisfy all the claims.
...
s.
Definition
There is a ''resource'' to allocate, denoted by
. For example, it can be an integer representing the number of seats in a ''h''ouse of representatives. The resource should be allocated between some
''agents''. For example, these can be
federal states
A federation (also known as a federal state) is a political entity characterized by a union of partially self-governing provinces, states, or other regions under a central federal government (federalism). In a federation, the self-governi ...
or
political parties
A political party is an organization that coordinates candidates to compete in a particular country's elections. It is common for the members of a party to hold similar ideas about politics, and parties may promote specific ideological or pol ...
. The agents have different ''entitlements'', denoted by a vector
. For example, ''t
i'' can be the fraction of votes won by party ''i''. An ''allocation'' is a vector
with
. An ''allocation rule'' is a rule that, for any
and entitlement vector
, returns an allocation vector
.
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
, and on the entitlement vector
, then the result is the allocation vector
. 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.
Handling ties
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
, and Denote by
the set of allocation vectors returned by
on the resource
and entitlement vector
. The rule
is called coherent if the following holds for every allocation vector
and any subset ''S'' of agents:
*
. That is, every part of every possible solution to the grand problem, is a possible solution to the sub-problem.
* For every
and
, we have
. 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.
Coherence in apportionment
In apportionment problems, the resource to allocate is ''discrete'', for example, the seats in a parliament. Therefore, each agent must receive an integer allocation.
Non-coherent methods: the new state paradox
One of the most intuitive rules for apportionment of seats in a parliament is the
largest remainder method
The largest remainder method (also known as Hare–Niemeyer method, Hamilton method or as Vinton's method) is one way of allocating seats proportionally for representative assemblies with party list voting systems. It contrasts with various h ...
(LRM). This method dictates that the entitlement vector should be normalized such that the sum of entitlements equals
(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
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
Oklahoma (; Choctaw language, Choctaw: ; chr, ᎣᎧᎳᎰᎹ, ''Okalahoma'' ) is a U.S. state, state in the South Central United States, South Central region of the United States, bordered by Texas on the south and west, Kansas on the nor ...
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 members. A recomputation of apportionment affected the number of seats because of other states: New York lost a seat, while Maine gained one.
Coherent methods
Every
divisor method
A highest-averages method, also called a divisor method, is a class of methods for allocating seats in a parliament among agents such as political parties or federal states. A divisor method is an iterative method: at each iteration, the number ...
is coherent. This follows directly from their description as picking sequences: at each iteration, the next agent to pick an item is the one with the highest ratio (entitlement / divisor). Therefore, the relative priority ordering between agents is the same even if we consider a subset of the agents.
Properties of coherent methods
When coherency is combined with other natural requirements, it characterizes a structured class of apportionment methods. Such characterizations were proved by various authors.
All results assume that the rules are
homogeneous ("''decent")''.
* Hylland proved that if a coherent decent apportionment rule is
''balanced'' and ''
concordant
Concordance may refer to:
* Agreement (linguistics), a form of cross-reference between different parts of a sentence or phrase
* Bible concordance, an alphabetical listing of terms in the Bible
* Concordant coastline, in geology, where beds, or la ...
'', then it is compatible with a divisor method.
* Balinsky and Young
proved that if a coherent decent apportionment rule is
''anonymous'' and
''balanced'', then it is a
rank-index method (a super-class of divisor methods). The opposite is also true: among the anonymous and balanced methods, a method is coherent if and only if it is a rank-index method.
* Balinsky and Young
proved that if a coherent decent apportionment rule is
''anonymous'',
''concordant'' and ''weakly exact'', then it is a divisor method.
* Balinsky and Rachev proved that if a coherent decent apportionment rule is
''anonymous'', ''order-preserving'', ''weakly exact'' and ''complete'', then it is a divisor method.
* Palomares, Pukelsheim and Ramirez
proved that:
** if a coherent decent apportionment rule is ''
anonymous
Anonymous may refer to:
* Anonymity, the state of an individual's identity, or personally identifiable information, being publicly unknown
** Anonymous work, a work of art or literature that has an unnamed or unknown creator or author
* Anonym ...
'' and ''
balanced
In telecommunications and professional audio, a balanced line or balanced signal pair is a circuit consisting of two conductors of the same type, both of which have equal impedances along their lengths and equal impedances to ground and to other ...
'', then it is
house-monotone;
** if, in addition, it is also
''concordant'', then it is
vote-ratio monotone;
** if, in addition, it is also ''strongly exact'', then it is compatible with a divisor method (that is, it returns a subset of the allocations returned by a divisor method);
** if, in addition, it is also ''complete'', then it is a
divisor method
A highest-averages method, also called a divisor method, is a class of methods for allocating seats in a parliament among agents such as political parties or federal states. A divisor method is an iterative method: at each iteration, the number ...
.
* Young proved that the unique apportionment method that is a coherent extension of the natural two-party apportionment rule of rounding to the nearest integer is the
Webster method.
Coherence in bankruptcy problems
In
bankruptcy problem
A bankruptcy problem, also called a claims problem, is a problem of distributing a homogeneous divisible good (such as money) among people with different claims. The focus is on the case where the amount is insufficient to satisfy all the claims.
...
s, the resource to allocate is ''continuous'', for example, the amount of money left by a debtor. Each agent can get any fraction of the resource. However, the sum of entitlements is usually larger than the total remaining resource.
The most intuitive rule for solving such problems is the ''
proportional rule'', in which each agent gets a part of the resource proportional to his entitlement. This rule is definitely coherent. However, it is not the only coherent rule: the Talmudic rule of the
contested garment can be extended to a coherent division rule.
Coherence in organ allocation
In most countries, the number of patients waiting for an
organ transplantation
Organ transplantation is a medical procedure in which an organ (anatomy), organ is removed from one body and placed in the body of a recipient, to replace a damaged or missing organ. The donor and recipient may be at the same location, or organ ...
is much larger than the number of available organs. Therefore, most countries choose who to allocate an organ to by some priority-ordering. Surprisingly, some priority orderings used in practice are not coherent. For example, one rule used by
UNOS in the past was as follows:
* Each patient is assigned a personal ''score'', based on some medical data.
* Each patient is assigned a ''bonus'', which is 10 times the fraction of patients who waited less than him.
* The agents are prioritized by the sum of their score + bonus.
Suppose the personal scores of some four patients A, B, C, D are 16, 21, 20, 23. Suppose their waiting times are A > B > C > D. Accordingly, their bonuses are 10, 7.5, 5, 2.5. So their sums are 26, 28.5, 25, 25.5, and the priority order is B > A > D > C. Now, after B receives an organ, the personal scores of A, C, D remain the same, but the bonuses change to 10, 6.67, 3.33, so the sums are 26, 26.67, 26.33, and the priority order is C > D > A. This inverts the order between the three agents.
In order to have a coherent priority ordering, the priority should be determined only by personal traits. For example, the bonus can be computed by the number of months in line, rather than by the fraction of patients.
See also
*
Apportionment paradox
An apportionment paradox exists when the rules for apportionment in a political system produce results which are unexpected or seem to violate common sense.
To apportion is to divide into parts according to some rule, the rule typically being one ...
*
References
{{reflist
Fairness criteria
Apportionment method criteria