Sequential Apportionment from Stationary Divisor Methods

1. Problem Statement

The paper addresses the gap in the literature regarding sequential apportionment—the specific order in which seats are awarded to political parties in proportional representation systems. While divisor methods (e.g., D'Hondt, Adams, Sainte-Laguë) are well-studied for their final seat allocations, less attention has been paid to the sequence of allocation. This sequence is practically significant in coalition governments (e.g., Northern Ireland) where cabinet positions are awarded sequentially based on the order of seat allocation, and in "Just-in-Time" (JIT) sequencing problems in operations research.

The authors focus on stationary divisor methods, a family of methods parametrized by a rounding cutpoint $c \in [0, 1]$. The core problem is to characterize the set of all possible apportionment sequences generated by these methods for given vote totals, determine the number of distinct sequences, and analyze the relationship between the sequence order and the method's bias toward large or small parties.

2. Methodology

The authors employ a combination of combinatorial analysis, number theory, and algorithmic construction:

• Definitions and Framework:
  • They define the sequential apportionment process where the $k$-th seat is awarded to the party $i$ maximizing the ratio $p_i / (a_i + c)$, where $p_i$ is the vote count, $a_i$ is the current seat count, and $c$ is the cutpoint.
  • They establish that for integer vote totals, these sequences are periodic. The period length $P$ is determined by the greatest common divisor (GCD) of the vote totals: $P = (\sum p_i) / \gcd(p_1, \dots, p_n)$.
• Lexicographical Ordering:
  • The authors introduce a lexicographical ordering of sequences to refine the concept of "size bias." Instead of viewing bias solely as the total number of seats a party receives, they analyze when parties receive seats.
  • They prove that sequences are ordered by their cutpoints: $S_0(p) \ge S_c(p) \ge S_1(p)$, where $S_0$ is Adams' method (favoring small parties) and $S_1$ is D'Hondt's method (favoring large parties).
• Two-Party Analysis (Section 3):
  • For two parties with votes $p_1 > p_2$, the authors derive explicit formulas for the sequence structure. They show the sequence consists of blocks of 1s (Party 1) separated by single 2s (Party 2).
  • They characterize the number of 1s between 2s ($k_i$) as a function of $c$ and the vote ratio, proving that the sequence is constant on intervals of the form $[\frac{\ell}{p_1-p_2}, \frac{\ell+1}{p_1-p_2})$.
• Multi-Party Extension (Section 4):
  • Utilizing the consistency property of divisor methods (where the relative allocation between any two parties is independent of other parties), they develop an algorithm to "lift" $\binom{n}{2}$ pairwise sequences into a single $n$-party sequence.
  • They provide a constructive algorithm (Algorithm 1) that merges pairwise sequences by identifying the unique party that appears as the leading term in $n-1$ pairwise subsequences at each step.
• Counting Distinct Sequences:
  • They apply the Principle of Inclusion/Exclusion to count the number of distinct sequences. This involves calculating the union of sets of "cutpoint endpoints" derived from all pairwise combinations of parties.

3. Key Contributions and Results

A. Characterization of Sequences

• Periodicity: Theorem 2 proves that for integer votes, stationary divisor methods generate periodic sequences with period $P = (\sum p_i)/\gcd(p_i)$.
• Structure: For two parties, the sequence is fully characterized by the number of consecutive seats the larger party receives before the smaller party gets one. The authors provide explicit formulas (Theorem 3) for these counts based on the cutpoint $c$.
• Adams vs. D'Hondt Relationship: Theorem 1 establishes a direct relationship between the sequences of the two extreme methods: The Adams sequence ($c=0$) is the D'Hondt sequence ($c=1$) shifted by the initial allocation of one seat to each party ($S_0(p) = (1, 2, \dots, n, s_1, s_2, \dots)$).

B. Refinement of Size Bias

• The paper reframes size bias. While Adams' method favors small parties and D'Hondt favors large parties in terms of total seats, the authors show that in a sequential context, the difference lies in the timing of seat acquisition.
• Proposition 2 proves that for any $c > c'$, the sequence $S_c$ is lexicographically smaller than $S_{c'}$. This means methods with higher $c$ (favoring large parties) award seats to large parties earlier in the sequence, while methods with lower $c$ award seats to small parties earlier.

C. Algorithms and Counting

• Lifting Algorithm: The authors provide a rigorous method to construct $n$-party sequences from pairwise data, proving that the pairwise consistency of divisor methods allows for this reconstruction (Theorem 6).
• Counting Formula: Theorem 8 provides a formula for the number of distinct sequential apportionments for $n$ parties. It is calculated as:
  $$1 + \left| \bigcup_{k \in M} A_k \right|$$
  where $A_k$ represents the set of critical cutpoint values derived from the pairwise vote differences, and the "1" accounts for the $c=1$ (D'Hondt) case. The size of the union is computed using the Principle of Inclusion/Exclusion involving GCDs of the pairwise denominators.

D. Specific Findings

• Two-Party Case: If $p_1$ and $p_2$ are relatively prime, there are exactly $p_1 - p_2 + 1$ distinct sequences.
• Multi-Party Case: The number of distinct sequences depends on the arithmetic properties of the vote totals (specifically the GCDs of pairwise differences), not just the number of parties.
• Non-Periodicity: The paper notes that non-stationary methods (like Hill-Huntington) or irrational vote ratios do not necessarily yield periodic sequences.

4. Significance and Applications

• Political Science: The work offers a new tool for analyzing coalition governments. It demonstrates that the choice of apportionment method (specifically the cutpoint $c$) does not just change the number of seats but fundamentally alters the order of cabinet selection. This can resolve or exacerbate political conflicts regarding portfolio allocation.
• Operations Research (JIT Sequencing): The results apply to Just-in-Time sequencing problems where items must be processed to meet demand. The paper connects fair queueing based on start times (Adams) vs. finish times (D'Hondt) to specific divisor methods, offering a theoretical basis for optimizing production schedules.
• Theoretical Advancement: By establishing a partial order on apportionment sequences and providing a complete enumeration of possible sequences for stationary methods, the paper fills a theoretical gap in the study of proportional representation. It moves beyond static allocation to dynamic, sequential analysis.

Conclusion

The paper successfully characterizes the landscape of sequential apportionments for stationary divisor methods. It proves that these sequences are periodic, provides a constructive algorithm to generate $n$-party sequences from pairwise data, and derives exact formulas for the number of distinct sequences. Crucially, it redefines the concept of bias in apportionment as a function of the timing of seat allocation, offering a nuanced perspective on how different divisor methods (from Adams to D'Hondt) influence political and operational outcomes.