Mathematics of apportionment
Mathematics of apportionment
In mathematics and fair-division, apportionment problems involve dividing (apportioning) a whole number of identical goods fairly across several parties with real-valued entitlements. The original, and best-known, example of an apportionment problem involves distributing seats in a legislature between different federal states or political parties. However, apportionment methods can be applied to other situations as well, including bankruptcy-problems, inheritance law (e.g. dividing animals), manpower planning (e.g. demographic quotas), and rounding percentages.
Mathematically, an apportionment method is just a method of rounding real numbers to natural numbers. Despite the simplicity of this problem, every method of rounding suffers one or more paradoxes, as proven by the Balinski–Young theorem. The mathematical theory of apportionment identifies what properties can be expected from an apportionment method.
The mathematical theory of apportionment was studied as early as 1907 by the mathematician Agner Krarup Erlang. It was later developed to a great detail by the mathematician Michel Balinski and the economist peyton-young.
Definitions ### Input The inputs to an apportionment method are:
- A positive integer <math>h</math> representing the total number of items to allocate. It is also called the house size, since in many cases, the items to allocate are seats in a house of representatives.
- A positive integer <math>n</math> representing the number of agents to which items should be allocated. For example, these can be federal states or political parties.
- A vector of numbers <math>(t_1,\ldots,t_n)</math> representing entitlements - <math>t_i</math> represents the entitlement of agent <math>i</math>, that is, the amount of items to which <math>i</math> is entitled (out of the total of <math>h</math>). These entitlements are often normalized such that <math>\sum_{i=1}^n t_i = 1</math>. Alternatively, they can be normalized such that their sum is <math>h</math>; in this case the entitlements are called quotas and termed denoted by <math>q_i</math>, where <math>q_i := t_i\cdot h</math> and <math>\sum_{i=1}^n q_i = h</math>. Alternatively, one is given a vector of populations <math>(p_1,\ldots,p_n)</math>; here, the entitlement of agent <math>i</math> is <math>t_i = p_i / \sum_{j=1}^n p_j</math>.
Output The output is a vector of integers <math>a_1,\ldots,a_n</math> with <math>\sum_{i=1}^n a_i = h</math>, called an apportionment of <math>h</math>, where <math>a_i</math> is the number of items allocated to agent i.
For each party <math>i</math>, the real number <math>q_i := t_i\cdot h</math> is called the *entitlement* or seat quota for <math>i</math>, and denotes the exact number of items that should be given to <math>i</math>. In general, a "fair" apportionment is one in which each allocation <math>a_i</math> is as close as possible to the quota <math>q_i</math>.
An apportionment method may return a set of apportionment vectors (in other words: it is a multivalued function). This is required, since in some cases there is no fair way to distinguish between two possible solutions. For example, if <math>h = 101</math> (or any other odd number) and <math>t_1 = t_2 = 1/2</math>, then (50,51) and (51,50) are both equally reasonable solutions, and there is no mathematical way to choose one over the other. While such ties are extremely rare in practice, the theory must account for them (in practice, when an apportionment method returns multiple outputs, one of them may be chosen by some external priority rules, or by coin flipping, but this is beyond the scope of the mathematical apportionment theory).
An apportionment method is denoted by a multivalued function <math>M(\mathbf{t}, h)</math>; a particular <math>M</math>-solution is a single-valued function <math>f(\mathbf{t}, h)</math> which selects a single apportionment from <math>M(\mathbf{t}, h)</math>.
A partial apportionment method is an apportionment method for specific fixed values of <math>n</math> and <math>h</math>; it is a multivalued function <math>M^(\mathbf{t})</math> that accepts only <math>n</math>*-vectors.
Variants Sometimes, the input also contains a vector of integers <math>r_1,\ldots,r_n</math> representing minimum requirements - <math>r_i</math> represents the smallest number of items that agent <math>i</math> should receive, regardless of its entitlement. So there is an additional requirement on the output: <math>a_i \geq r_i</math> for all <math>i</math>.
When the agents are political parties, these numbers are usually 0, so this vector is omitted. But when the agents are states or districts, these numbers are often positive in order to ensure that all are represented. They can be the same for all agents (e.g. 1 for USA states, 2 for France districts), or different (e.g. in Canada or the European parliament).
Sometimes there is also a vector of maximum requirements, but this is less common.
Basic requirements There are basic properties that should be satisfied by any reasonable apportionment method. They were given different names by different authors: the names on the left are from Pukelsheim;*' The names in parentheses on the right are from Balinsky and Young. means that exactness also holds "in the limit". That is, if a sequence of entitlement vectors converges to an integer quota vector <math>(q_1,\ldots,q_n)</math>, then the only allocation vector in all elements of the sequence is <math>(q_1,\ldots,q_n)</math>. To see the difference from weak exactness, consider the following rule. (a) Give each agent its quota rounded down, <math>\lfloor q_i\rfloor</math>; (b) give the remaining seats iteratively to the largest parties. This rule is weakly exact, but not strongly exact. For example, suppose h=6 and consider the sequence of quota vectors (4+1/k, 2-1/k). The above rule yields the allocation (5,1) for all k, even though the limit when k→∞ is the integer vector (4,2). Strong proportionality
Common apportionment methods There are many apportionment methods, and they can be classified into several approaches.
Largest remainder methods start by computing the vector of quotas rounded down, that is, <math>\lfloor q_1 \rfloor,\ldots,\lfloor q_n \rfloor</math>. If the sum of these rounded values is exactly <math>h</math>, then this vector is returned as the unique apportionment. Typically, the sum is smaller than <math>h</math>. In this case, the remaining items are allocated among the agents according to their remainders <math>q_i - \lfloor q_i \rfloor</math>: the agent with the largest remainder receives one seat, then the agent with the second-largest remainder receives one seat, and so on, until all items are allocated. There are several variants of the LR method, depending on which quota is used: #* The simple quota, also called the Hare quota, is <math>t_i h</math>. Using LR with the Hare quota leads to Hamilton's method. #* The Hagenbach-Bischoff quota, also called the exact Droop quota, is <math>t_i\cdot(h+1)</math>. The quotas in this method are larger, so there are fewer remaining items. In theory, it is possible that the sum of rounded-down quotas would be <math>h+1</math> which is larger than <math>h</math>, but this rarely happens in practice. # Divisor methods, instead of using a fixed multiplier in the quota (such as <math>h</math> or <math>h+1</math>), choose the multiplier such that the sum of rounded quotas is exactly equal to <math>h</math>, so there are no remaining items to allocate. Formally, <math>M(\mathbf{t},h) := \{\mathbf{a} | a_i = \operatorname{round}(t_i\cdot H) \text{ and } \sum_{i=1}^n a_i = h \text{ for some real number } H \}.</math> Divisor methods differ by the method they use for rounding. A divisor method is parametrized by a divisor function <math>d(k)</math> which specifies, for each integer <math>k\geq 0</math>, a real number in the interval <math>[k, k+1]</math>. It means that all numbers in <math>[k, d(k)]</math> should be rounded down to <math>k</math>, and all numbers in <math>[d(k), k+1]</math> should be rounded up to <math>k+1</math>. The rounding function is denoted by <math>\operatorname{round}^d(x)</math>, and returns an integer <math>k</math> such that <math>d(k-1)\leq x \leq d(k)</math>. The number <math>d(k)</math> itself can be rounded both up and down, so the rounding function is multi-valued. For example, Adams' method uses <math>d(k) = k</math>, which corresponds to rounding up; D'Hondt/Jefferson method uses <math>d(k) = k+1</math>, which corresponds to rounding down; and Webster/Sainte-Laguë method uses <math>d(k) = k+0.5</math>, which corresponds to rounding to the nearest integer. A divisor method can also be computed iteratively: initially, <math>a_i</math> is set to 0 for all parties. Then, at each iteration, the next seat is allocated to a party which maximizes the ratio <math>\frac{t_i}{d(a_i)}</math>. #Rank-index methods are parametrized by a function <math>r(t,a)</math> which is decreasing in <math>a</math>. The apportionment is computed iteratively. Initially, set <math>a_i</math> to 0 for all parties. Then, at each iteration, allocate the next seat to an agent which maximizes <math>r(t_i,a_i)</math>. Divisor methods are a special case of rank-index methods: a divisor method with divisor function <math>d(a)</math> is equivalent to a rank-index method with rank-index <math>r(t,a) = t/d(a)</math>. # Optimization-based methods aim to attain, for each instance, an allocation that is "as fair as possible" for this instance. An allocation is "fair" if <math>a_i = q_i</math> for all agents i; in this case, we say that the "unfairness" of the allocation is 0. If this equality is violated, one can define a measure of "total unfairness", and try to minimize it. One can minimize the sum of unfairness levels, or the maximum unfairness level. Each optimization criterion leads to a different optimal-apportionment rule.
Staying within the quota The exact quota of agent <math>i</math> is <math>q_i = t_i\cdot h</math>. A basic requirement from an apportionment method is that it allocates to each agent <math>i</math> its quota <math>q_i </math> if it is an integer; otherwise, it should allocate it an integer that is near the exact quota, that is, either its lower quota <math>\lfloor q_i\rfloor </math> or its upper quota <math>\lceil q_i\rceil </math>. We say that an apportionment method -
- Satisfies lower quota if <math>a_i\geq \lfloor q_i\rfloor </math> for all <math>i </math> (this holds iff <math>a_i + 1 > q_i </math>).
- Satisfies upper quota if <math>a_i\leq \lceil q_i\rceil </math> for all <math>i </math> (this holds iff <math>a_i - 1 < q_i </math>).
- Satisfies both quotas** if both the above conditions hold (this holds iff <math>\frac{q_i}{a_i+1} < 1 < \frac{q_i}{a_i-1} </math>).
Hamilton's largest-remainder method satisfies both lower quota and upper quota by construction. This does not hold for the divisor methods. This yields the Quota-Webster method, Quota-Hill method, etc. This family of methods is often called the **quatatone methods*', Some of the possibilities do not lead to a stable solution. For example, if we define inequality as <math>|a_i/a_j - t_i/t_j|</math>, then there are instances in which, for any allocation, moving a seat from one agent to another might decrease their pairwise inequality. There is an example with 3 states with populations (737,534,329) and 16 seats.) means that, if we take some subset of the agents <math>1,\ldots,k</math>, and apply the same method to their combined allocation <math>h_k = a_1+\cdots+a_k</math>, then the result is the vector <math>(a_1,\ldots,a_k)</math>. All rank-index methods (hence all divisor methods) are uniform, since they assign seats to agents in a pre-determined method - determined by <math>r(t,a)</math>, and this order does not depend on the presence or absence of other agents. Moreover, every uniform method that is also *anonymous* and *balanced* must be a rank-index method.
- Jefferson's method is the only uniform method satisfying lower quota;
- Adams's method is the only uniform method satisfying upper quota;
- Webster's method is the only uniform method that is near quota;
- No uniform method satisfies both quotas. In particular, Hamilton's method and the Quota method are not uniform. However, the Quota method is the unique method that satisfies both quotas in addition to house-monotonicity and "quota-consistency", which is a weaker form of uniformity.
Encouraging coalitions When the agents are political parties, they often split or merge. How such splitting/merging affects the apportionment will impact political fragmentation. Suppose a certain apportionment method gives two agents <math>i,j</math> some <math>a_i, a_j</math> seats respectively, and then these two agents form a coalition, and the method is re-activated.
- An apportionment method always encourages coalitions if a coalition of two parties receives at least <math>a_i + a_j</math> seats (in other words, it is split-proof - a party cannot gain a seat by splitting).
- An apportionment method always encourages schisms if the coalition receives at most <math>a_i + a_j</math> seats (in other words, it is merge-proof - two parties cannot gain a seat by merging).
Among the divisor methods: * A divisor method with divisor <math>d</math> is coalitionally-stable iff <math>d(a_1 + a_2) \leq d(a_1) + d(a_2) \leq d(a_1 + a_2+1)</math>; this holds for all five standard divisor methods.
Moreover, every method satisfying both quotas is "almost coalitionally-stable" - it gives every coalition between <math>a_i + a_j-2</math> and <math>a_i + a_j+2</math> seats.