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]
Definitions
Input
The inputs to an apportionment method are:
A positive integer 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 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 representing entitlements - represents the entitlement of agent , that is, the amount of items to which is entitled (out of the total of ). These entitlements are often normalized such that . Alternatively, they can be normalized such that their sum is ; in this case the entitlements are called quotas and termed denoted by , where and . Alternatively, one is given a vector of populations ; here, the entitlement of agent is .
Output
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.
Variants
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.
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;[10]:75 The names in parentheses on the right are from Balinsky and Young.[1]
Anonymity (=Symmetry) means that the apportionment does not depend on the agents' names or indices. Formally, if is any permutation of , then the apportionments in are exactly the corresponding permutations of the apportionments in .
This requirement makes sense when there are no minimal requirements, or when the requirements are the same; if they are not the same, then anonymity should hold subject to the requirements being satisfied.
Balancedness (=Balance) means that if two agents have equal entitlements, then their allocation should differ by at most 1: implies .
Concordance (=Weak population monotonicity) means that an agent with a strictly higher entitlement receives at least as many items: implies .
Decency (=Homogeneity) means that scaling the entitlement vector does not change the outcome. Formally, for every constant c (this is automatically satisfied if the input to the apportionment method is normalized).
Exactness (=Weak proportionality) means that if there exists a perfect solution, then it must be selected. Formally, for normalised , if the quota of each agent is an integer number, then must contain a unique vector . In other words, if an h-apportionment is exactly proportional to , then it should be the unique element of .
Strong exactness[11]:13 means that exactness also holds "in the limit". That is, if a sequence of entitlement vectors converges to an integer quota vector , then the only allocation vector in all elements of the sequence is . To see the difference from weak exactness, consider the following rule. (a) Give each agent its quota rounded down, ; (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[1] means that, in addition, if , and , and there is some h-apportionment that is exactly proportional to , then it should be the unique element of . For example, if one solution in is (3,3), then the only solution in must be (2,2).[why?]
Completeness means that, if some apportionment is returned for a converging sequence of entitlement vectors, then is also returned for their limit vector. In other words, the set - the set of entitlement vectors for which is a possible apportionment - is topologically closed. An incomplete method can be "completed" by adding the apportionment to any limit entitlement if and only if it belongs to every entitlement in the sequence. The completion of a symmetric and proportional apportionment method is complete, symmetric and proportional.[1]:Prop.2.2
Completeness is violated by methods that apply an external tie-breaking rule, as done by many countries in practice. The tie-breaking rule applies only in the limit case, so it might break the completeness.
Completeness and weak-exactness together imply strong-exactness. If a complete and weakly-exact method is modified by adding an appropriate tie-breaking rule, then the resulting rule is no longer complete, but it is still strongly-exact.[11]:13
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, . If the sum of these rounded values is exactly , then this vector is returned as the unique apportionment. Typically, the sum is smaller than . In this case, the remaining items are allocated among the agents according to their remainders : 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 Hagenbach-Bischoff quota, also called the exact Droop quota, is . 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 which is larger than , but this rarely happens in practice.
The Imperiali quota is . This quota is less common, since there are higher chances that the sum of rounded-down quotas will be larger than .
Divisor methods, instead of using a fixed multiplier in the quota (such as or ), choose the multiplier such that the sum of rounded quotas is exactly equal to , so there are no remaining items to allocate. Formally, Divisor methods differ by the method they use for rounding. A divisor method is parametrized by a divisor function which specifies, for each integer , a real number in the interval . It means that all numbers in should be rounded down to , and all numbers in should be rounded up to . The rounding function is denoted by , and returns an integer such that . The number itself can be rounded both up and down, so the rounding function is multi-valued. For example, Adams' method uses , which corresponds to rounding up; D'Hondt/Jefferson method uses , which corresponds to rounding down; and Webster/Sainte-Laguë method uses , which corresponds to rounding to the nearest integer. A divisor method can also be computed iteratively: initially, is set to 0 for all parties. Then, at each iteration, the next seat is allocated to a party which maximizes the ratio .
Rank-index methods are parametrized by a function which is decreasing in . The apportionment is computed iteratively. Initially, set to 0 for all parties. Then, at each iteration, allocate the next seat to an agent which maximizes . Divisor methods are a special case of rank-index methods: a divisor method with divisor function is equivalent to a rank-index method with rank-index .
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 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.
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 -
Satisfies lower quota if for all (this holds iff ).
Satisfies upper quota if for all (this holds iff ).
Satisfies both quotas if both the above conditions hold (this holds iff ).
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
All divisor methods satisfy both quotas when there are 2 agents;
Webster's method is the only divisor method satisfying both quotas for 3 agents;
Adams' method is the only divisor method satisfying upper quota for any number of agents;
Jefferson's method is the only divisor method satisfying lower quota for any number of agents;
No divisor method simultaneously violates upper quota for one agent and violates lower quota for another agent.
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.
Minimizing pairwise inequality
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
. Webster's method is the unique apportionment method in which, for each pair of agents and , this difference is minimized (that is, moving a seat from to or vice versa would not make the difference smaller).
for This leads to Adams's method.
for . This leads to Jefferson's method.
. This leads to Dean's method.
. This leads to the Huntington-Hill method.
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
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]
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 some seats respectively, and then these two agents form a coalition, and the method is re-activated.
An apportionment method alwaysencourages coalitions if a coalition of two parties receives at least seats (in other words, it is split-proof - a party cannot gain a seat by splitting).
An apportionment method alwaysencourages schisms if the coalition receives at most seats (in other words, it is merge-proof - two parties cannot gain a seat by merging).
Jefferson's method is the unique split-proof divisor method;
Adams's method is the unique merge-proof divisor method;
Webster's method is neither split-proof nor merge-proof, but it is "coalition neutral": when votes are distributed randomly (with uniform[disambiguation needed] remainders), a coalition is equally likely to gain a seat or to lose a seat.[1]:Prop.9.4
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.
The Hamilton method is coalitionally-stable.[20]:Thm.2[14]:Appendix
A divisor method with divisor is coalitionally-stable iff ; this holds for all five standard divisor methods.[20]:Thm.1
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.
In physics, Hamiltonian mechanics is a reformulation of Lagrangian mechanics that emerged in 1833. Introduced by Sir William Rowan Hamilton, Hamiltonian mechanics replaces (generalized) velocities used in Lagrangian mechanics with (generalized) momenta. Both theories provide interpretations of classical mechanics and describe the same physical phenomena.
The Webster method, also called the Sainte-Laguë method, is a highest averages apportionment method for allocating seats in a parliament among federal states, or among parties in a party-list proportional representation system. The Sainte-Laguë method shows a more equal seats-to-votes ratio for different sized parties among apportionment methods.
In mathematics, economics, and political science, the highest averages methods, also called divisor methods, are a class of apportionment algorithms for proportional representation. Divisor algorithms seek to fairly divide a legislature between agents. More generally, divisor methods are used to divide or round a whole number of objects being used to represent (non-whole) shares of a total.
In mathematics and classical mechanics, the Poisson bracket is an important binary operation in Hamiltonian mechanics, playing a central role in Hamilton's equations of motion, which govern the time evolution of a Hamiltonian dynamical system. The Poisson bracket also distinguishes a certain class of coordinate transformations, called canonical transformations, which map canonical coordinate systems into canonical coordinate systems. A "canonical coordinate system" consists of canonical position and momentum variables that satisfy canonical Poisson bracket relations. The set of possible canonical transformations is always very rich. For instance, it is often possible to choose the Hamiltonian itself as one of the new canonical momentum coordinates.
In condensed matter physics, Bloch's theorem states that solutions to the Schrödinger equation in a periodic potential can be expressed as plane waves modulated by periodic functions. The theorem is named after the Swiss physicist Felix Bloch, who discovered the theorem in 1929. Mathematically, they are written
In the physical science of dynamics, rigid-body dynamics studies the movement of systems of interconnected bodies under the action of external forces. The assumption that the bodies are rigid simplifies analysis, by reducing the parameters that describe the configuration of the system to the translation and rotation of reference frames attached to each body. This excludes bodies that display fluid, highly elastic, and plastic behavior.
In geometry, curvilinear coordinates are a coordinate system for Euclidean space in which the coordinate lines may be curved. These coordinates may be derived from a set of Cartesian coordinates by using a transformation that is locally invertible at each point. This means that one can convert a point given in a Cartesian coordinate system to its curvilinear coordinates and back. The name curvilinear coordinates, coined by the French mathematician Lamé, derives from the fact that the coordinate surfaces of the curvilinear systems are curved.
In algebraic geometry and the theory of complex manifolds, a logarithmic differential form is a differential form with poles of a certain kind. The concept was introduced by Pierre Deligne. In short, logarithmic differentials have the mildest possible singularities needed in order to give information about an open submanifold.
In abstract algebra, the biquaternions are the numbers w + xi + yj + zk, where w, x, y, and z are complex numbers, or variants thereof, and the elements of {1, i, j, k} multiply as in the quaternion group and commute with their coefficients. There are three types of biquaternions corresponding to complex numbers and the variations thereof:
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied.
The Eckart conditions, named after Carl Eckart, simplify the nuclear motion (rovibrational) Hamiltonian that arises in the second step of the Born–Oppenheimer approximation. They make it possible to approximately separate rotation from vibration. Although the rotational and vibrational motions of the nuclei in a molecule cannot be fully separated, the Eckart conditions minimize the coupling close to a reference configuration. The Eckart conditions are explained by Louck and Galbraith and in Section 10.2 of the textbook by Bunker and Jensen, where a numerical example is given.
In physics, Lagrangian mechanics is a formulation of classical mechanics founded on the stationary-action principle. It was introduced by the Italian-French mathematician and astronomer Joseph-Louis Lagrange in his presentation to the Turin Academy of Science in 1760 culminating in his 1788 grand opus, Mécanique analytique.
House monotonicity is a property of apportionment methods. These are methods for allocating seats in a parliament among federal states. The property says that, if the number of seats in the "house" increases, and the method is re-activated, then no state should have fewer seats than it previously had. A method that fails to satisfy house-monotonicity is said to have the Alabama paradox.
State-population monotonicity is a property of apportionment methods, which are methods of allocating seats in a parliament among federal states or political parties. The property says that if the population of State A increases faster than that of State B, then State A should not lose any seats to State B. Apportionment methods violating this rule are called population paradoxes.
Seat bias is a property describing methods of apportionment. These are methods used to allocate seats in a parliament among federal states or among political parties. A method is biased if it systematically favors small parties over large parties, or vice versa. There are various ways to compute the bias of apportionment methods.
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.
Optimal apportionment is an approach to apportionment that is based on mathematical optimization.
Vote-ratio monotonicity (VRM) is a property of apportionment methods, which are methods of allocating seats in a parliament among political parties. The property says that, if the ratio between the number of votes won by party A to the number of votes won by party B increases, then it should NOT happen that party A loses a seat while party B gains a seat.
Balance or balancedness is a property of apportionment methods, which are methods of allocating identical items between among agens, such as dividing seats in a parliament among political parties or federal states. The property says that, if two agents have exactly the same entitlements, then the number of items they receive should differ by at most one. So if two parties win the same number of votes, or two states have the same populations, then the number of seats they receive should differ by at most one.
In apportionment theory, rank-index methods are a set of apportionment methods that generalize the divisor method. These have also been called Huntington methods, since they generalize an idea by Edward Vermilye Huntington.
↑ Balinski, Michel L.; Young, H. Peyton (2001). Fair Representation: Meeting the Ideal of One Man, One Vote (2nded.). Washington, DC: Brookings Institution Press. ISBN0-8157-0111-X.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.