Highest averages 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 of votes of each party is divided by its divisor, which is a function of the number of seats (initially 0) currently allocated to that party. The next seat is allocated to the party whose resulting ratio is largest.^[1]

Definitions

The inputs to a divisor method are the number of seats to allocate, denoted by h, and the vector of parties' entitlements, where the entitlement of party ${\displaystyle i}$  is denoted by ${\displaystyle t_{i}}$  (a number between 0 and 1 determining the fraction of seats to which ${\displaystyle i}$  is entitled). Assuming all votes are counted, ${\displaystyle t_{i}}$  is simply the number of votes received by ${\displaystyle i}$ , divided by the total number of votes.

Procedural definition

A divisor method is parametrized by a function ${\displaystyle d(k)}$ , mapping each integer ${\displaystyle k}$  to a real number (usually in the range ${\displaystyle [k,k+1]}$ ) .

The number of seats allocated to party ${\displaystyle i}$  is denoted by ${\displaystyle a_{i}}$ . Initially, ${\displaystyle a_{i}}$  is set to 0 for all parties. Then, at each iteration, the next seat is allocated to a party which maximizes the ratio ${\displaystyle {\frac {t_{i}}{d(a_{i})}}}$ . The method proceeds for h iterations, until all seats are allocated.

Multiplier definition

An equivalent definition directly gives the outcome of the divisor method as follows.

For an election, a quotient is calculated, usually the total number of votes divided by the number of seats to be allocated (the Hare quota). Parties are then allocated seats by determining how many quotients they have won, by dividing their vote totals by the quotient. Where a party wins a fraction of a quotient, this can be rounded down or rounded to the nearest whole number. Rounding down is equivalent to using the D'Hondt method, while rounding to the nearest whole number is equivalent to the Sainte-Laguë method. Rounding up is equivalent to using Adams's method. However, because of the rounding, this will not necessarily result in the desired number of seats being filled. In that case, the quotient may be adjusted up or down until the number of seats after rounding is equal to the desired number.

The tables used in the D'Hondt or Sainte-Laguë methods can then be viewed as calculating the highest quotient possible to round off to a given number of seats. For example, the quotient which wins the first seat in a D'Hondt calculation is the highest quotient possible to have one party's vote, when rounded down, be greater than 1 quota and thus allocate 1 seat. The quotient for the second round is the highest divisor possible to have a total of 2 seats allocated, and so on.

Formally, given the vector of entitlements ${\displaystyle \mathbf {t} }$  and house-size ${\displaystyle h}$ , a divisor method can be defined as:

${\displaystyle \{\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\}}$ 

where the method of rounding is defined by the divisor function d.

Max-min definition

Every divisor method can be defined using a min-max inequality: a is an allocation for the divisor method with divisor d, if-and-only-if^{[2]: 78–81}

${\displaystyle \max _{i}t_{i}/d(a_{i}+1)\leq \min _{i:a_{i}>0}t_{i}/d(a_{i})}$ .

Every number in the range ${\displaystyle [\max _{i}t_{i}/d(a_{i}+1)~,~\min _{i:a_{i}>0}t_{i}/d(a_{i})]}$  is a possible divisor. If the range is not a singleton (that is, the inequality is strict), then the solution is unique; otherwise (the inequality is an equality), there are multiple solutions.^[2]: 83

Specific divisor methods

Divisor formulas

Method	Divisor d(k)	Rounding of Seats	First values (approx.)
Adam's	k	Up	0.00 1.00 2.00 3.00
Danish	k + 1⁄3		0.33 1.33 2.33 3.33
Dean's	k(k+1)/(k + 1⁄2) = 2÷(1⁄k + 1⁄k+1)	Harmonic	0.00 1.33 2.40 3.43
Huntington– Hill	√k(k + 1)	Geometric	0.00 1.41 2.45 3.46
Webster / Sainte-Laguë	k + 1⁄2	Arithmetic	0.50 1.50 2.50 3.50
D'Hondt / Jefferson	k + 1	Down	1.00 2.00 3.00 4.00
Imperiali	k + 2		2.00 3.00 4.00 5.00

The methods have different properties, as explained in the following.

Imperiali method

The Imperiali highest average method (not to be confused with the Imperiali quota which is a Largest remainder method) has divisors 1, 1.5, 2, 2.5, 3, 3.5 etc., or equivalently 2, 3, 4, 5, etc., corresponding to a divisor function ${\displaystyle d(k)=k+2}$ . It is designed to disfavor the smallest parties, akin to a "cutoff", and is used only in Belgian municipal elections. This method (unlike other listed methods) is not strictly proportional: if a perfectly proportional allocation exists, it is not guaranteed to find it.

D'Hondt method

The most widely used divisor sequence is 1, 2, 3, 4, etc., corresponding to the divisor function ${\displaystyle d(k)=k+1}$ . It is called the D'Hondt formula.^[3] This system tends to give larger parties a slightly larger portion of seats than their portion of the electorate, and thus guarantees that a party with a majority of voters will get at least half of the seats.

Webster/Sainte-Laguë method

The Webster/Sainte-Laguë method divides the number of votes for each party by the odd numbers (1, 3, 5, 7 etc.), or equivalently by 0.5, 1.5, 2.5, 3.5 etc. It corresponds to a divisor function ${\displaystyle d(k)=k+0.5}$ .

It is sometimes considered more proportional than D'Hondt in terms of a comparison between a party's share of the total vote and its share of the seat allocation though it can lead to a party with a majority of votes winning fewer than half the seats. This system is more favourable to smaller parties than D'Hondt's method, and thus it encourages splits.

The Webster/Sainte-Laguë method is sometimes modified by increasing the first divisor from 1 to e.g. 1.4, to discourage very small parties gaining their first seat "too cheaply".

Huntington–Hill method

In the Huntington–Hill method, the divisor function is ${\displaystyle d(k)={\sqrt {k(k+1)}}}$ , which makes sense only if every party is guaranteed at least one seat: this effect can be achieved by disqualifying parties receiving fewer votes than a specified number of votes, be it a percentage threshold or a quota such as Hare, Droop, or Imperiali. This method is used for allotting seats in the US House of Representatives among the states. Because squaring does not change the order of the computed ratios, the square root involved in comparing ${\displaystyle {\frac {t_{i}}{\sqrt {a_{i}(a_{i}+1)}}}}$  values can be avoided by instead comparing ${\displaystyle {\frac {t_{i}^{2}}{a_{i}(a_{i}+1)}}}$  values.

Danish method

The Danish method is used in Danish elections to allocate each party's compensatory seats (or levelling seats) at the electoral province level to individual multi-member constituencies. It divides the number of votes received by a party in a multi-member constituency by the divisors growing by step equal to 3 (1, 4, 7, 10, etc.). Alternatively, dividing the votes numbers by 0.33, 1.33, 2.33, 3.33 etc. yields the same result. The divisor function is ${\displaystyle d(k)=k+1/3}$ . This system purposely attempts to allocate seats equally rather than proportionately.^[4]

Adams's method

Adams's method was conceived by John Quincy Adams for apportioning seats of the House to states.^[5] He perceived Jefferson's method to allocate too few seats to smaller states. It can be described as the inverse of Jefferson's method; it awards a seat to the party that has the most votes per seat before the seat is added. The divisor function is ${\displaystyle d(k)=k}$ .^[6]

Like the Huntington-Hill method, this results in a value of 0 for the first seats to be appointed for each party, resulting in an average of ∞. It can only violate the lower quota rule.^[7] This occurs in the example below.

Without a threshold, all parties that have received at least one vote, also receive a seat, with the obvious exception of cases where there are more parties than seats. This property can be desirable, for example when apportioning seats to electoral districts. As long as there are at least as many seats as districts, all districts are represented. In a party-list proportional representation election, it may result in very small parties receiving seats. Furthermore, quota rule violations in the pure Adams's method are very common.^[8] These problems may be solved by introducing an electoral threshold.^[6]

Comparative example

In the following example, the total vote is 100,000. There are 10 seats. The number at each cell in the "pink" table denotes the number of votes divided by the corresponding divisor ${\displaystyle d(k)}$ . For example, for D'Hondt's method, in the row ${\displaystyle k=0}$ , the numbers are just the parties' votes (divided by ${\displaystyle k+1=1}$ ). In the row ${\displaystyle k=1}$ , the numbers are the votes divided by 2. For the Saint-Lague method, in the row ${\displaystyle k=1}$ , the numbers are the votes divided by 3 (the second element in the sequence of divisors), and so on.

	D'Hondt method						Sainte-Laguë method (unmodified: sequence 1,3,5,7...)						Sainte-Laguë method (modified: sequence 1.4,3,5,7...)						Huntington–Hill method^[a]						Pure Adams's method						Adams's method with threshold = 1
party	Yellow	White	Red	Green	Blue	Pink	Yellow	White	Red	Green	Blue	Pink	Yellow	White	Red	Green	Blue	Pink	Yellow	White	Red	Green	Blue	Pink	Yellow	White	Red	Green	Blue	Pink	Yellow	White	Red	Green	Blue	Pink
votes	47,000	16,000	15,900	12,000	6,000	3,100	47,000	16,000	15,900	12,000	6,000	3,100	47,000	16,000	15,900	12,000	6,000	3,100	47,000	16,000	15,900	12,000	6,000	3,100	47,000	16,000	15,900	12,000	6,000	3,100	47,000	16,000	15,900	12,000	6,000	3,100
seats	5	2	2	1	0	0	4	2	2	1	1	0	5	2	2	1	0	0	5	2	2	1	0	0	3	2	2	1	1	1	4	2	2	2	0	0
votes/seat	9,400	8,000	7,950	12,000			11,750	8,000	7,950	12,000	6,000		9,400	8,000	7,950	12,000			9,400	8,000	7,950	12,000			15,667	8,000	7,950	12,000	6,000	3,100	11,750	8,000	7,950	6,000
${\displaystyle k}$	quotient
0	47,000	16,000	15,900	12,000	6,000	3,100	47,000	16,000	15,900	12,000	6,000	3,100	33,571	11,429	11,357	8,571	4,286	2,214	∞	∞	∞	∞	excluded		∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	excluded
1	23,500	8,000	7,950	6,000	3,000	1,550	15,667	5,333	5,300	4,000	2,000	1,033	15,667	5,333	5,300	4,000	2,000	1,033	33,234	11,314	11,243	8,485			47,000	16,000	15,900	12,000	6,000	3,100	47,000	16,000	15,900	12,000
2	15,667	5,333	5,300	4,000	2,000	1,033	9,400	3,200	3,180	2,400	1,200	620	9,400	3,200	3,180	2,400	1,200	620	19,187	6,531	6,491	4,898			23,500	8,000	7,950	6,000	3,000	1,550	23,500	8,000	7,950	6,000
3	11,750	4,000	3,975	3,000	1,500	775	6,714	2,857	2,271	1,714	875	443	6,714	2,857	2,271	1,714	875	443	13,567	4,618	4,589	3,464			15,667	5,333	5,300	4,000	2,000	1,033	15,667	5,333	5,300	4,000
4	9,400	3,200	3,180	2,400	1,200	620	5,222	1,778	1,767	1,333	667	333	5,222	1,778	1,767	1,333	667	333	10,509	3,577	3,555	2,683			11,750	4,000	3,975	3,000	1,500	775	11,750	4,000	3,975	3,000
5	7,833	2,667	2,650	2,000	1,000	517	4,273	1,454	1,445	1,091	545	282	4,273	1,454	1,445	1,091	545	282	8,580	2,921	2,902	2,190			9,400	3,200	3,180	2,400	1,200	620	9,400	3,200	3,180	2,400
seat	seat allocation
1	47,000						47,000						33,571						∞				excluded		∞						∞				excluded
2	23,500							16,000					15,667							∞						∞						∞
3		16,000							15,900					11,429							∞						∞						∞
4			15,900				15,667								11,357							∞						∞						∞
5	15,667									12,000			9,400						33,234										∞		47,000
6				12,000			9,400									8,571			19,187											∞	23,500
7	11,750						6,714						6,714						13,567						47,000							16,000
8	9,400										6,000			5,333						11,314					23,500								15,900
9		8,000						5,333							5,300						11,243					16,000					15,667
10			7,950						5,300				5,222						10,509								15,900							12,000

As can be seen in the example, D'Hondt, Sainte-Laguë and Huntington-Hill allow different strategies by parties looking to maximize their seat allocation. D'Hondt and Huntington–Hill can favor the merging of parties, while Sainte-Laguë can favor splitting parties (modified Saint-Laguë reduces the splitting advantage).

In these examples, under D'Hondt and Huntington–Hill the Yellows and Greens combined would gain an additional seat if they merged, while under Sainte-Laguë the Yellows would gain if they split into six lists with about 7,833 votes each.

Properties

All divisor methods satisfy the basic properties of anonymity, balance, concordance, exactness and completeness.

All the divisor methods satisfy house monotonicity. This means that, when the number of seats in the parliament increases, no party loses a seat.^{[9]: Cor.4.3.1} This is evident from the iterative description of the methods: when a seat is added, the initial process remains the same, it just proceeds to an additional iteration. In other words, divisor methods avoid the Alabama paradox.

Moreover, all divisor methods satisfy pairwise population monotonicity. This means that, if the number of votes of one party increases in a faster rate than the number of votes of another party, then it does not happen that the first party loses seats while the second party gains seats. Moreover, the divisor methods are provably the only methods satisfying this form of monotonicity.^{[9]: Thm.4.3} In other words, divisor methods are the only ones avoiding the population paradox.

On the negative side, divisor methods might violate the quota rule: they might give some agents less than their lower quota (quota rounded down) or more than their upper quota (quota rounded up). This can be fixed by using quota-capped divisor methods (see below).

Simulation experiments^[10] show that different divisor methods have greatly different probabilities of violating quota (when the number of votes is selected by an exponential distribution):

• The probability for Adams and D'Hondt is 98%;
• The probability for D'Hondt with a minimum requirement of 1 is 78%;
• The probability for Dean is about 9%, and for Huntington-Hill about 4%;
• The probability for Webster/Sainte-Laguë is the smallest - only 0.16%.

A divisor method is called stationary^[11]: 68 if its divisor is of the form ${\displaystyle d(k)=k+r}$  for some real number ${\displaystyle r\in [0,1]}$ . The methods of Adams, Webster and DHondt are stationary, while those of Dean and Huntington-Hill are not.

Quota-capped divisor method

A quota-capped divisor method is an apportionment method in which the next seat is allocated only to a party from a set of eligible parties. Eligible parties should satisfy two conditions:

• Their current allocation is smaller than their upper quota (where the quota is computed based on the total number of seats including the next one).
• Giving them an additional seat would not deprive other states of their lower quota.

Formally, in each iteration ${\displaystyle h}$  (corresponding to allocating the ${\displaystyle h}$ -th seat), the following sets are computed (see mathematics of apportionment for the definitions and notation):

• ${\displaystyle U(\mathbf {t} ,\mathbf {a} )}$  is the set of parties that can get an additional seat without violating their upper quota, that is, ${\displaystyle a_{i}<\lceil t_{i}\cdot h\rceil }$ .
• ${\displaystyle L(\mathbf {t} ,\mathbf {a} )}$  is the set of parties whose number of seats might be below their lower quota in some future iteration, that is, ${\displaystyle a_{i}<\lfloor t_{i}\cdot (h+z)\rfloor }$  for the smallest integer ${\displaystyle z}$  for which ${\displaystyle \sum _{i}\lfloor t_{i}\cdot (h+z)\rfloor \geq h-1+z}$ . If there is no such ${\displaystyle z}$  then ${\displaystyle L(\mathbf {t} ,\mathbf {a} )}$  contains all states.

The ${\displaystyle h}$ -th seat is given to a party ${\displaystyle i\in U(\mathbf {t} ,\mathbf {a} )\cap L(\mathbf {t} ,\mathbf {a} )}$  for which the ratio ${\displaystyle {\frac {t_{i}}{d(a_{i})}}}$  is largest.

The Balinsky-Young quota method^[12] is the quota-capped variant of the D'Hondt method (also called: Quota-Jefferson). Similarly, one can define the Quota-Webster, Quota-Adams, etc.^[13]

Every quota-capped divisor method satisfies house-monotonicity. If eligibility is based on quotas as above, then the quota-capped divisor method satisfies upper quota by definition, and it can be proved that it satisfies lower quota as well.^{[14]: Thm.7.1}

However, quota-capped divisor methods might violate a property of population monotonicity: it is possible that some party i wins more votes, while all other parties win the same number of votes, but party i loses a seat.^{[14]: Tbl.A7.2 [15]} This could happen when, due to party i getting more votes, the upper quota of some other party j decreases. Therefore, party j is not eligible to a seat in the current iteration, and some third party receives the next seat. But then, at the next iteration, party j is again eligible to a seat, and it beats party i. There are similar examples for all quota-capped divisor methods.

Rank-index methods

A rank-index methods^{[16]: Sec.8} is a generalization of a divisor method. Another term is a Huntington method,^[17] since it generalizes an idea by Edward Vermilye Huntington.

Input and output

Like all apportionment methods, the inputs of any rank-index method are:

• A positive integer ${\displaystyle h}$  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 ${\displaystyle n}$  representing the number of agents to which items should be allocated. For example, these can be federal states or political parties.
• A vector of fractions ${\displaystyle (t_{1},\ldots ,t_{n})}$  with ${\displaystyle \sum _{i=1}^{n}t_{i}=1}$ , representing entitlements - ${\displaystyle t_{i}}$  represents the entitlement of agent ${\displaystyle i}$ , that is, the fraction of items to which ${\displaystyle i}$  is entitled (out of the total of ${\displaystyle h}$ ).

Its output is a vector of integers ${\displaystyle a_{1},\ldots ,a_{n}}$  with ${\displaystyle \sum _{i=1}^{n}a_{i}=h}$ , called an apportionment of ${\displaystyle h}$ , where ${\displaystyle a_{i}}$  is the number of items allocated to agent i.

Iterative procedure

Every rank-index method is parametrized by a rank-index function ${\displaystyle r(t,a)}$ , which is increasing in the entitlement ${\displaystyle t}$  and decreasing in the current allocation ${\displaystyle a}$ . The apportionment is computed iteratively as follows:

• Initially, set ${\displaystyle a_{i}}$  to 0 for all parties.
• At each iteration, allocate one item to an agent for whom ${\displaystyle r(t_{i},a_{i})}$  is maximum (break ties arbitrarily).
• Stop after ${\displaystyle h}$  iterations.

Divisor methods are a special case of rank-index methods: a divisor method with divisor function ${\displaystyle d(a)}$  is equivalent to a rank-index method with rank-index function ${\displaystyle r(t,a)=t/d(a)}$ .

Min-max formulation

Every rank-index method can be defined using a min-max inequality: a is an allocation for the rank-index method with function r, if-and-only-if:^{[16]: Thm.8.1}

${\displaystyle \min _{i:a_{i}>0}r(t_{i},a_{i}-1)\geq \max _{i}r(t_{i},a_{i})}$ .

Properties

Every rank-index method is house-monotone. This means that, when ${\displaystyle h}$  increases, the allocation of each agent weakly increases. This immediately follows from the iterative procedure.

Every rank-index method is uniform. This means that, we take some subset of the agents ${\displaystyle 1,\ldots ,k}$ , and apply the same method to their combined allocation ${\displaystyle h_{k}=a_{1}+\cdots +a_{k}}$ , then the result is exactly the vector ${\displaystyle (a_{1},\ldots ,a_{k})}$ . In other words: every part of a fair allocation is fair too. This immediately follows from the min-max inequality.

Moreover:

• Every apportionment method that is uniform, symmetric and balanced must be a rank-index method.^{[16]: Thm.8.3}
• Every apportionment method that is uniform, house-monotone and balanced must be a rank-index method.^[17]

Notes

1. The excluded parties would not change regardless of the base quota being used, be it Hare ${\displaystyle \left({\frac {100,000}{10}}={10,000}\right)}$ , Droop ${\displaystyle \left(\left\lfloor {\frac {100,000}{11}}\right\rfloor +1={9,091}\right)}$ , or Imperiali ${\displaystyle \left({\frac {100,000}{12}}={8,333.{\bar {3}}}\right)}$ 

References

1. Norris, Pippa (2004). Electoral Engineering: Voting Rules and Political Behavior. Cambridge University Press. p. 51. ISBN 0-521-82977-1.
2. Pukelsheim, Friedrich (2017), Pukelsheim, Friedrich (ed.), "Divisor Methods of Apportionment: Divide and Round", Proportional Representation: Apportionment Methods and Their Applications, Cham: Springer International Publishing, pp. 71–93, doi:10.1007/978-3-319-64707-4_4, ISBN 978-3-319-64707-4, retrieved 2021-09-01
3. Gallagher, Michael (1991). (PDF). Electoral Studies. 10 (1): 33–51. doi:10.1016/0261-3794(91)90004-C. Archived from the original (PDF) on 4 March 2016. Retrieved 30 January 2016.
4. "The Parliamentary Electoral System in Denmark".
5. "Apportioning Representatives in the United States Congress - Adams' Method of Apportionment | Mathematical Association of America". www.maa.org. Retrieved 2020-11-11.
6. Gallagher, Michael (1992). "Comparing Proportional Representation Electoral Systems: Quotas, Thresholds, Paradoxes and Majorities" (PDF). British Journal of Political Science. 22 (4): 469–496. doi:10.1017/S0007123400006499. ISSN 0007-1234.
7. Iian, Smythe (July 10, 2015). "MATH 1340 — Mathematics & Politics" (PDF). Retrieved November 11, 2020.
8. Ichimori, Tetsuo (2010). "New apportionment methods and their quota property". JSIAM Letters. 2: 33–36. doi:10.14495/jsiaml.2.33. ISSN 1883-0617.
9. Balinski, Michel L.; Young, H. Peyton (1982). Fair Representation: Meeting the Ideal of One Man, One Vote. New Haven: Yale University Press. ISBN 0-300-02724-9.
10. "RangeVoting.org - Apportionment methods". rangevoting.org. Retrieved 2021-08-06.
11. Pukelsheim, Friedrich (2017), Pukelsheim, Friedrich (ed.), "From Reals to Integers: Rounding Functions and Rounding Rules", Proportional Representation: Apportionment Methods and Their Applications, Cham: Springer International Publishing, pp. 59–70, doi:10.1007/978-3-319-64707-4_3, ISBN 978-3-319-64707-4, retrieved 2021-09-01
12. Balinski, M. L.; Young, H. P. (1975-08-01). "The Quota Method of Apportionment". The American Mathematical Monthly. 82 (7): 701–730. doi:10.1080/00029890.1975.11993911. ISSN 0002-9890.
13. Still, Jonathan W. (1979-10-01). "A Class of New Methods for Congressional Apportionment". SIAM Journal on Applied Mathematics. 37 (2): 401–418. doi:10.1137/0137031. ISSN 0036-1399.
14. Balinski, Michel L.; Young, H. Peyton (1982). Fair Representation: Meeting the Ideal of One Man, One Vote. New Haven: Yale University Press. ISBN 0-300-02724-9.
15. "RangeVoting.org - Apportionment and rounding schemes". rangevoting.org. Retrieved 2021-08-06.
16. Balinski, Michel L.; Young, H. Peyton (1982). Fair Representation: Meeting the Ideal of One Man, One Vote. New Haven: Yale University Press. ISBN 0-300-02724-9.
17. Balinski, M. L.; Young, H. P. (1977-12-01). "On Huntington Methods of Apportionment". SIAM Journal on Applied Mathematics. 33 (4): 607–618. doi:10.1137/0133043. ISSN 0036-1399.