Introduction
In many electoral and decision-making scenarios, votes are not collected or processed all at once. Ballots may arrive from different districts at different times, or system administrators may wish to preprocess early votes to minimize storage requirements. This practical need raises a fundamental theoretical question: what is the minimum amount of space required to store a partial set of votes such that the final winners can still be correctly determined once the remaining votes are cast?
This paper explores this concept, known as compilation complexity, specifically for multi-winner voting rules. While compilation complexity has been extensively studied for single-winner elections (e.g., standard plurality or Borda count), multi-winner systems—where a committee of size $k$ is selected—introduce significant new challenges. This research provides the first systematic analysis of these complexities, establishing tight mathematical bounds for several common multi-winner systems.
Theoretical Framework
The authors utilize an information-theoretic approach based on equivalence classes. In this context, two sets of partial votes (profiles) are considered equivalent if, regardless of the remaining votes cast, both profiles would result in the same winning committee.
The compilation complexity of a specific voting rule is defined as the logarithm of the number of these equivalence classes. To derive these values, the authors followed a three-step process:
- Identifying Sufficient Conditions: Determining what specific information (such as total Borda scores or approval counts) is enough to distinguish between non-equivalent profiles.
- Proving Necessity: Demonstrating that if any portion of that information is omitted, there exists a potential set of future votes that would lead to an incorrect winner.
- Categorization: Distinguishing between "decomposable" rules, where a committee's score is a simple sum of its members' scores, and more complex rules where scores depend on voter-specific representation.
Analysis of Voting Rules
The research highlights how different voting philosophies impact the amount of memory required to summarize an election.
Decomposable and Scoring-Based Rules
For rules like SNTV (Single Non-Transferable Vote), Bloc, and $k$-Borda, the state of the election can be summarized by tracking individual candidate scores. Because these rules are decomposable—meaning the total score of a committee is the sum of the scores of the candidates within it—they are relatively efficient to compile.
Representation and Diversity-Based Rules
Rules that prioritize diverse representation, such as Chamberlin-Courant (CC), are significantly harder to compress. In these systems, the score of a committee depends on which specific candidate in that committee a voter prefers most. Consequently, a summary must often store information about how candidates are ranked relative to each other, rather than just their aggregate scores. The authors found that the complexity for CC scales with the number of possible committees, $\binom{m}{k}$, making it one of the most "expensive" rules to preprocess.
Sequential Rules
For Sequential Plurality, the authors discovered that the system is particularly memory-intensive. To determine the winner, one must track the frequency of every possible ordered sequence of $k$ candidates appearing at the top of voters' ballots, leading to a massive state space compared to simple scoring rules.
Key Complexity Results
The paper establishes specific complexity bounds (using $\Theta$ notation), where $m$ represents the number of candidates and $n$ represents the number of voters:
- Approval Voting (AV): $\Theta(m \log n)$. This requires only storing the count of approvals for each candidate.
- $k$-Borda: $\Theta(m \log nm)$. This is slightly higher than AV because Borda scores grow larger than simple binary approval counts.
- SNTV: $\Theta(m \log(1 + n/m) + n \log(1 + m/n))$. This more complex formula accounts for the specific distribution of top-ranked votes.
- Chamberlin-Courant: The authors established lower and upper bounds, noting that the complexity is significantly higher due to the dependencies between different potential committee scores.
Conclusion and Future Work
This research provides a foundational map of the informational requirements for multi-winner elections. While it establishes tight bounds for several rules, the authors note that for Chamberlin-Courant rules (specifically $\alpha$-CC and $\beta$-CC), the lower and upper bounds do not yet perfectly match due to the mathematical difficulty of counting dependencies between committee scores.
Future research directions include tightening these bounds and extending the analysis to other complex rules such as Single Transferable Vote (STV), Monroe, and Proportional Approval Voting (PAV).
Summary updated