Coherence (fairness)

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 ${\displaystyle M}$, and Denote by ${\displaystyle M{\big (}h;(t_{i})_{i=1}^{n}{\big )}}$ the set of allocation vectors returned by ${\displaystyle M}$ on the resource ${\displaystyle h}$ and entitlement vector ${\displaystyle t_{1},\ldots ,t_{n}}$. The rule ${\displaystyle M}$ is called coherent if the following holds for every allocation vector ${\displaystyle (a_{i})_{i=1}^{n}\in M{\big (}h;(t_{i})_{i=1}^{n}{\big )}}$ and any subset S of agents:[3]^: Sec.4

• ${\displaystyle (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.
• For every ${\displaystyle (b_{i})_{i\in S}\in M{\Big (}\sum _{i\in S}a_{i};(t_{i})_{i\in S}{\Big )}}$ and ${\displaystyle (c_{i})_{i\notin S}\in M{\Big (}\sum _{i\notin S}a_{i};(t_{i})_{i\notin S}{\Big )}}$, we have ${\displaystyle [(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 ${\displaystyle 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 ${\displaystyle 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 members. A recomputation of apportionment affected the number of seats because of other states: New York lost a seat, while Maine gained one.[4]^{: 232–233}[5]

Every divisor method 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.

When coherency is combined with other natural requirements, it characterizes a structured class of apportionment methods. Such characterizations were proved by various authors.[3]^: Sec.1 All results assume that the rules are homogeneous ("decent").

• Hylland[6]^{: Thm.3, 10} proved that if a coherent decent apportionment rule is balanced and concordant, then it is compatible with a divisor method.
• Balinsky and Young[2]^: Thm.8.3 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[2]^{: Thm.8.4, p.147} proved that if a coherent decent apportionment rule is anonymous, concordant and weakly exact, then it is a divisor method.
• Balinsky and Rachev[7][8]^{: Thm.2.2, p.8} 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[3] proved that:
  • if a coherent decent apportionment rule is anonymous and balanced, 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.
• 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.[9]^{: 49–50, 190}[10]^: Sub.9.10