Rank-index method explained

In apportionment theory, rank-index methods[1] are a set of apportionment methods that generalize the divisor method. These have also been called Huntington methods,[2] since they generalize an idea by Edward Vermilye Huntington.

Input and output

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

h

representing the total number of items to allocate. It is also called the house size.

n

representing the number of agents to which items should be allocated. For example, these can be federal states or political parties.

(t1,\ldots,tn)

with
n
\sum
i=1

ti=1

, representing entitlements -

ti

represents the entitlement of agent

i

, that is, the fraction of items to which

i

is entitled (out of the total of

h

).

Its output is a vector of integers

a1,\ldots,an

with
n
\sum
i=1

ai=h

, called an apportionment of

h

, where

ai

is the number of items allocated to agent i.

Iterative procedure

Every rank-index method is parametrized by a rank-index function

r(t,a)

, which is increasing in the entitlement

t

and decreasing in the current allocation

a

. The apportionment is computed iteratively as follows:

ai

to 0 for all parties.

r(ti,ai)

is maximum (break ties arbitrarily).

h

iterations.

Divisor methods are a special case of rank-index methods: a divisor method with divisor function

d(a)

is equivalent to a rank-index method with rank-index function

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:

min
i:ai>0

r(ti,ai-1)\geqmaxir(ti,ai)

.

Properties

Every rank-index method is house-monotone. This means that, when

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

1,\ldots,k

, and apply the same method to their combined allocation, then the result is exactly the vector

(a1,\ldots,ak)

. In other words: every part of a fair allocation is fair too. This immediately follows from the min-max inequality.

Moreover:

Quota-capped divisor methods

A quota-capped divisor method is an apportionment method where we begin by assigning every state its lower quota of seats. Then, we add seats one-by-one to the state with the highest votes-per-seat average, so long as adding an additional seat does not result in the state exceeding its upper quota.[3] However, quota-capped divisor methods violate the participation criterion (also called population monotonicity)—it is possible for a party to lose a seat as a result of winning more votes.[4]

Every quota-capped divisor method satisfies house monotonicity. Moreover, quota-capped divisor methods satisfy the quota rule.[5]

However, quota-capped divisor methods violate the participation criterion (also called population monotonicity)—it is possible for a party to lose a seat as a result of winning more votes. This occurs when:

  1. Party i gets more votes.
  2. Because of the greater divisor, 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 seat instead.
  3. Then, at the next iteration, party j is again eligible to win a seat and it beats party i.

Moreover, quota-capped versions of other algorithms frequently violate the true quota in the presence of error (e.g. census miscounts). Jefferson's method frequently violates the true quota, even after being quota-capped, while Webster's method and Huntington-Hill perform well even without quota-caps.[6]

Notes and References

  1. Book: Balinski, Michel L. . Fair Representation: Meeting the Ideal of One Man, One Vote . Young . H. Peyton . Yale University Press . 1982 . 0-300-02724-9 . New Haven . registration.
  2. Balinski . M. L. . Young . H. P. . 1977-12-01 . On Huntington Methods of Apportionment . SIAM Journal on Applied Mathematics . en-US . 33 . 4 . 607–618 . 10.1137/0133043 . 0036-1399.
  3. Balinski . M. L. . Young . H. P. . 1975-08-01 . The Quota Method of Apportionment . The American Mathematical Monthly . 82 . 7 . 701–730 . 10.1080/00029890.1975.11993911 . 0002-9890.
  4. Book: Balinski . Michel L. . Fair Representation: Meeting the Ideal of One Man, One Vote . Young . H. Peyton . Yale University Press . 1982 . 0-300-02724-9 . New Haven . registration.
  5. Book: Balinski . Michel L. . Fair Representation: Meeting the Ideal of One Man, One Vote . Young . H. Peyton . Yale University Press . 1982 . 0-300-02724-9 . New Haven . registration.
  6. Spencer . Bruce D. . December 1985 . Statistical Aspects of Equitable Apportionment . Journal of the American Statistical Association . en . 80 . 392 . 815–822 . 10.1080/01621459.1985.10478188 . 0162-1459.