Rank-index method

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.

Input and output

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

• A positive integer [math]\displaystyle{ h }[/math] representing the total number of items to allocate. It is also called the house size.

• A positive integer [math]\displaystyle{ 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 fractions [math]\displaystyle{ (t_1,\ldots,t_n) }[/math] with [math]\displaystyle{ \sum_{i=1}^n t_i = 1 }[/math], representing entitlements - [math]\displaystyle{ t_i }[/math] represents the entitlement of agent [math]\displaystyle{ i }[/math], that is, the fraction of items to which [math]\displaystyle{ i }[/math] is entitled (out of the total of [math]\displaystyle{ h }[/math]).

Its output is a vector of integers [math]\displaystyle{ a_1,\ldots,a_n }[/math] with [math]\displaystyle{ \sum_{i=1}^n a_i = h }[/math], called an apportionment of [math]\displaystyle{ h }[/math], where [math]\displaystyle{ a_i }[/math] is the number of items allocated to agent i.

Iterative procedure

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

• Initially, set [math]\displaystyle{ a_i }[/math] to 0 for all parties.
• At each iteration, allocate one item to an agent for whom [math]\displaystyle{ r(t_i,a_i) }[/math] is maximum (break ties arbitrarily).
• Stop after [math]\displaystyle{ h }[/math] iterations.

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

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:

[math]\displaystyle{ \min_{i: a_i \gt 0} r(t_i, a_i-1) \geq \max_{i} r(t_i, a_i) }[/math].

Properties

Every rank-index method is house-monotone. This means that, when [math]\displaystyle{ h }[/math] 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 [math]\displaystyle{ 1,\ldots,k }[/math], and apply the same method to their combined allocation, then the result is exactly the vector [math]\displaystyle{ (a_1,\ldots,a_k) }[/math]. 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.
• Every apportionment method that is uniform, house-monotone and balanced must be a rank-index method.