Mathematics of apportionment describes mathematical principles and algorithms for fair allocation of identical items among parties with different entitlements. Such principles are used to apportion seats in parliaments among federal states or political parties. See apportionment (politics) for the more concrete principles and issues related to apportionment, and apportionment by country for practical methods used around the world.
Mathematically, an apportionment method is just a method of rounding fractions to integers. As simple as it may sound, each and every method for rounding suffers from one or more paradoxes. The mathematical theory of apportionment aims to decide what paradoxes can be avoided, or in other words, 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 Balinsky and the economist Peyton Young. [1] [2] [3] Besides its application to political parties, [4] it is also applicable to fair item allocation when agents have different entitlements. [5] [6] It is also relevant in manpower planning - where jobs should be allocated in proportion to characteristics of the labor pool, to statistics - where the reported rounded numbers of percentages should sum up to 100%, [7] [8] and to bankruptcy problems. [9]
The inputs to an apportionment method are:
The output is a vector of integers with , called an apportionment of , where is the number of items allocated to agent i.
For each agent , the real number is called the quota of , and denotes the exact number of items that should be given to . In general, a "fair" apportionment is one in which each allocation is as close as possible to the quota .
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 (or any other odd number) and , 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 ; a particular -solution is a single-valued function which selects a single apportionment from .
A partial apportionment method is an apportionment method for specific fixed values of and ; it is a multivalued function that accepts only -vectors.
Sometimes, the input also contains a vector of integers representing minimum requirements - represents the smallest number of items that agent should receive, regardless of its entitlement. So there is an additional requirement on the output: for all .
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 it is less common.
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; [10]: 75 The names in parentheses on the right are from Balinsky and Young. [1]
The proportionality of apportionment can be measured by seats-to-votes ratio and Gallagher index. The proportionality of apportionment together with electoral thresholds impact political fragmentation and barrier to entry to the political competition. [12]
There are many apportionment methods, and they can be classified into several approaches.
The exact quota of agent is . A basic requirement from an apportionment method is that it allocates to each agent its quota if it is an integer; otherwise, it should allocate it an integer that is near the exact quota, that is, either its lower quota or its upper quota . [13] We say that an apportionment method -
Hamilton's largest-remainder method satisfies both lower quota and upper quota by construction. This does not hold for the divisor methods. [1]: Prop.6.2, 6.3, 6.4, 6.5
Therefore, no divisor method satisfies both upper quota and lower quota for any number of agents. The uniqueness of Jefferson and Adams holds even in the much larger class of rank-index methods. [14]
This can be seen as a disadvantage of divisor methods, but it can also be considered a disadvantage of the quota criterion: [1]: 129
"For example, to give D 26 instead of 25 seats in Table 10.1 would mean taking a seat from one of the smaller states A, B, or C. Such a transfer would penalize the per capita representation of the small state much more - in both absolute and relative terms - than state D is penalized by getting one less than its lower quota. Similar examples can be invented in which some state might reasonably get more than its upper quota. It can be argued that staying within the quota is not really compatible with the idea of proportionality at all, since it allows a much greater variance in the per capita representation of smaller states than it does for larger states."
In Monte-Carlo simulations, Webster's method satisfies both quotas with a very high probability. Moreover, Wesbter's method is the only division method that satisfies near quota: [1]: Thm.6.2 there are no agents such that moving a seat from to would bring both of them nearer to their quotas:
.
Jefferson's method can be modified to satisfy both quotas, yielding the Quota-Jefferson method. [13] Moreover, any divisor method can be modified to satisfy both quotas. [15] This yields the Quota-Webster method, Quota-Hill method, etc. This family of methods is often called the quatatone methods, [14] as they satisfy both quotas and house-monotonicity.
One way to evaluate apportionment methods is by whether they minimize the amount of inequality between pairs of agents. Clearly, inequality should take into account the different entitlements: if then the agents are treated "equally" (w.r.t. to their entitlements); otherwise, if then agent is favored, and if then agent is favored. However, since there are 16 ways to rearrange the equality , there are correspondingly many ways by which inequality can be defined. [1]: 100–102
This analysis was done by Huntington in the 1920s. [16] [17] [18] Some of the possibilities do not lead to a stable solution. For example, if we define inequality as , 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. [1]: Prop.3.5
When the agents are federal states, it is particularly important to avoid bias between large states and small states. There are several ways to measure this bias formally. All measurements lead to the conclusion that Jefferson's method is biased in favor of large states, Adams' method is biased in favor of small states, and Webster's method is the least biased divisor method.
Consistency properties are properties that characterize an apportionment method, rather than a particular apportionment. Each consistency property compares the outcomes of a particular method on different inputs. Several such properties have been studied.
State-population monotonicity means that, if the entitlement of an agent increases, its apportionment should not decrease. The name comes from the setting where the agents are federal states, whose entitlements are determined by their population. A violation of this property is called the population paradox. There are several variants of this property. One variant - the pairwise PM - is satisfied exclusively by divisor methods. That is, an apportionment method is pairwise PM if-and-only-if it is a divisor method. [1]: Thm.4.3
When and , no partial apportionment method satisfies pairwise-PM, lower quota and upper quota. [1]: Thm.6.1 Combined with the previous statements, it implies that no divisor method satisfies both quotas.
House monotonicity means that, when the total number of seats increases, no agent loses a seat. The violation of this property is called the Alabama paradox. It was considered particularly important in the early days of the USA, when the congress size increased every ten years. House-monotonicity is weaker than pairwise-PM. All rank-index methods (hence all divisor methods) are house-monotone - this clearly follows from the iterative procedure. Besides the divisor methods, there are other house-monotone methods, and some of them also satisfy both quotas. For example, the Quota method of Balinsky and Young satisfies house-monotonicity and upper-quota by construction, and it can be proved that it also satisfies lower-quota. [13] It can be generalized: there is a general algorithm that yields all apportionment methods which are both house-monotone and satisfy both quotas. However, all these quota-based methods (Quota-Jefferson, Quota-Hill, etc.) may violate pairwise-PM: there are examples in which one agent gains in population but loses seats. [1]: Sec.7
Uniformity (also called coherence [19]) means that, if we take some subset of the agents , and apply the same method to their combined allocation , then the result is the vector . All rank-index methods (hence all divisor methods) are uniform, since they assign seats to agents in a pre-determined method - determined by , 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. [1]: Thm.8.3
Every uniform method that is also anonymous, weakly-exact and concordant (= implies ) must be a divisor method. [1]: Thm.8.4 Moreover, among all anonymous methods: [14]
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 some seats respectively, and then these two agents form a coalition, and the method is re-activated.
Among the divisor methods: [1]: Thm.9.1, 9.2, 9.3
Since these are different methods, no divisor method gives every coalition of exactly seats. Moreover, this uniqueness can be extended to the much larger class of rank-index methods. [14]
A weaker property, called "coalitional-stability", is that every coalition of should receive between and seats; so a party can gain at most one seat by merging/splitting.
Moreover, every method satisfying both quotas is "almost coalitionally-stable" - it gives every coalition between and seats. [14]
The following table summarizes uniqueness results for classes of apportionment methods. For example, the top-left cell states that Jefferson's method is the unique divisor method satisfying the lower quota rule.
Uniquely satisfies Among
|
Lower quota | Upper quota | Near Quota | House monotonicity | Uniformity | Population Monotonic | Splitproof | Mergeproof |
---|---|---|---|---|---|---|---|---|
Divisor rules | Jefferson | Adams | Webster | Any | Any | Any | Jefferson | Adams |
Rank-index rules | Jefferson | Adams | Webster | Divisor rules | Any | Divisor rules | Jefferson | Adams |
Quota rules | Any | Any | Any | None | None | None | ||
Quota-capped divisor rules | Yes | Yes | Yes | Yes | None | None |
Mathematics of apportionment describes mathematical principles and algorithms for fair allocation of identical items among parties with different entitlements. Such principles are used to apportion seats in parliaments among federal states or political parties. See apportionment (politics) for the more concrete principles and issues related to apportionment, and apportionment by country for practical methods used around the world.
Mathematically, an apportionment method is just a method of rounding fractions to integers. As simple as it may sound, each and every method for rounding suffers from one or more paradoxes. The mathematical theory of apportionment aims to decide what paradoxes can be avoided, or in other words, 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 Balinsky and the economist Peyton Young. [1] [2] [3] Besides its application to political parties, [4] it is also applicable to fair item allocation when agents have different entitlements. [5] [6] It is also relevant in manpower planning - where jobs should be allocated in proportion to characteristics of the labor pool, to statistics - where the reported rounded numbers of percentages should sum up to 100%, [7] [8] and to bankruptcy problems. [9]
The inputs to an apportionment method are:
The output is a vector of integers with , called an apportionment of , where is the number of items allocated to agent i.
For each agent , the real number is called the quota of , and denotes the exact number of items that should be given to . In general, a "fair" apportionment is one in which each allocation is as close as possible to the quota .
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 (or any other odd number) and , 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 ; a particular -solution is a single-valued function which selects a single apportionment from .
A partial apportionment method is an apportionment method for specific fixed values of and ; it is a multivalued function that accepts only -vectors.
Sometimes, the input also contains a vector of integers representing minimum requirements - represents the smallest number of items that agent should receive, regardless of its entitlement. So there is an additional requirement on the output: for all .
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 it is less common.
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; [10]: 75 The names in parentheses on the right are from Balinsky and Young. [1]
The proportionality of apportionment can be measured by seats-to-votes ratio and Gallagher index. The proportionality of apportionment together with electoral thresholds impact political fragmentation and barrier to entry to the political competition. [12]
There are many apportionment methods, and they can be classified into several approaches.
The exact quota of agent is . A basic requirement from an apportionment method is that it allocates to each agent its quota if it is an integer; otherwise, it should allocate it an integer that is near the exact quota, that is, either its lower quota or its upper quota . [13] We say that an apportionment method -
Hamilton's largest-remainder method satisfies both lower quota and upper quota by construction. This does not hold for the divisor methods. [1]: Prop.6.2, 6.3, 6.4, 6.5
Therefore, no divisor method satisfies both upper quota and lower quota for any number of agents. The uniqueness of Jefferson and Adams holds even in the much larger class of rank-index methods. [14]
This can be seen as a disadvantage of divisor methods, but it can also be considered a disadvantage of the quota criterion: [1]: 129
"For example, to give D 26 instead of 25 seats in Table 10.1 would mean taking a seat from one of the smaller states A, B, or C. Such a transfer would penalize the per capita representation of the small state much more - in both absolute and relative terms - than state D is penalized by getting one less than its lower quota. Similar examples can be invented in which some state might reasonably get more than its upper quota. It can be argued that staying within the quota is not really compatible with the idea of proportionality at all, since it allows a much greater variance in the per capita representation of smaller states than it does for larger states."
In Monte-Carlo simulations, Webster's method satisfies both quotas with a very high probability. Moreover, Wesbter's method is the only division method that satisfies near quota: [1]: Thm.6.2 there are no agents such that moving a seat from to would bring both of them nearer to their quotas:
.
Jefferson's method can be modified to satisfy both quotas, yielding the Quota-Jefferson method. [13] Moreover, any divisor method can be modified to satisfy both quotas. [15] This yields the Quota-Webster method, Quota-Hill method, etc. This family of methods is often called the quatatone methods, [14] as they satisfy both quotas and house-monotonicity.
One way to evaluate apportionment methods is by whether they minimize the amount of inequality between pairs of agents. Clearly, inequality should take into account the different entitlements: if then the agents are treated "equally" (w.r.t. to their entitlements); otherwise, if then agent is favored, and if then agent is favored. However, since there are 16 ways to rearrange the equality , there are correspondingly many ways by which inequality can be defined. [1]: 100–102
This analysis was done by Huntington in the 1920s. [16] [17] [18] Some of the possibilities do not lead to a stable solution. For example, if we define inequality as , 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. [1]: Prop.3.5
When the agents are federal states, it is particularly important to avoid bias between large states and small states. There are several ways to measure this bias formally. All measurements lead to the conclusion that Jefferson's method is biased in favor of large states, Adams' method is biased in favor of small states, and Webster's method is the least biased divisor method.
Consistency properties are properties that characterize an apportionment method, rather than a particular apportionment. Each consistency property compares the outcomes of a particular method on different inputs. Several such properties have been studied.
State-population monotonicity means that, if the entitlement of an agent increases, its apportionment should not decrease. The name comes from the setting where the agents are federal states, whose entitlements are determined by their population. A violation of this property is called the population paradox. There are several variants of this property. One variant - the pairwise PM - is satisfied exclusively by divisor methods. That is, an apportionment method is pairwise PM if-and-only-if it is a divisor method. [1]: Thm.4.3
When and , no partial apportionment method satisfies pairwise-PM, lower quota and upper quota. [1]: Thm.6.1 Combined with the previous statements, it implies that no divisor method satisfies both quotas.
House monotonicity means that, when the total number of seats increases, no agent loses a seat. The violation of this property is called the Alabama paradox. It was considered particularly important in the early days of the USA, when the congress size increased every ten years. House-monotonicity is weaker than pairwise-PM. All rank-index methods (hence all divisor methods) are house-monotone - this clearly follows from the iterative procedure. Besides the divisor methods, there are other house-monotone methods, and some of them also satisfy both quotas. For example, the Quota method of Balinsky and Young satisfies house-monotonicity and upper-quota by construction, and it can be proved that it also satisfies lower-quota. [13] It can be generalized: there is a general algorithm that yields all apportionment methods which are both house-monotone and satisfy both quotas. However, all these quota-based methods (Quota-Jefferson, Quota-Hill, etc.) may violate pairwise-PM: there are examples in which one agent gains in population but loses seats. [1]: Sec.7
Uniformity (also called coherence [19]) means that, if we take some subset of the agents , and apply the same method to their combined allocation , then the result is the vector . All rank-index methods (hence all divisor methods) are uniform, since they assign seats to agents in a pre-determined method - determined by , 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. [1]: Thm.8.3
Every uniform method that is also anonymous, weakly-exact and concordant (= implies ) must be a divisor method. [1]: Thm.8.4 Moreover, among all anonymous methods: [14]
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 some seats respectively, and then these two agents form a coalition, and the method is re-activated.
Among the divisor methods: [1]: Thm.9.1, 9.2, 9.3
Since these are different methods, no divisor method gives every coalition of exactly seats. Moreover, this uniqueness can be extended to the much larger class of rank-index methods. [14]
A weaker property, called "coalitional-stability", is that every coalition of should receive between and seats; so a party can gain at most one seat by merging/splitting.
Moreover, every method satisfying both quotas is "almost coalitionally-stable" - it gives every coalition between and seats. [14]
The following table summarizes uniqueness results for classes of apportionment methods. For example, the top-left cell states that Jefferson's method is the unique divisor method satisfying the lower quota rule.
Uniquely satisfies Among
|
Lower quota | Upper quota | Near Quota | House monotonicity | Uniformity | Population Monotonic | Splitproof | Mergeproof |
---|---|---|---|---|---|---|---|---|
Divisor rules | Jefferson | Adams | Webster | Any | Any | Any | Jefferson | Adams |
Rank-index rules | Jefferson | Adams | Webster | Divisor rules | Any | Divisor rules | Jefferson | Adams |
Quota rules | Any | Any | Any | None | None | None | ||
Quota-capped divisor rules | Yes | Yes | Yes | Yes | None | None |