Compilation Complexity of Common Voting Rules

Lirong Xia, Vincent Conitzer

Abstract

This paper investigates "compilation complexity," defined as the minimum number of bits needed to summarize a subset of votes such that the final election winner can be determined once the remaining votes are cast. The study provides asymptotically tight upper and lower bounds for several common voting rules, including Borda, Bucklin, and Condorcet-consistent systems. The findings suggest that for many systems, intuitive summarization methods—such as maintaining candidate scores or weighted majority graphs—are asymptotically optimal.

Introduction

In many practical voting scenarios, ballots are not collected simultaneously. Votes may be cast over time (early voting) or across different geographic locations. To optimize storage, protect privacy, or facilitate faster final tallies, it is advantageous to "compile" or summarize votes from a subelectorate into a concise format. The central question addressed is: how much information can be discarded without losing the ability to correctly identify the winner once all votes are in?

The paper formalizes this by defining three types of compilation complexity based on the knowledge of the subelectorate size ($k$) and the number of missing votes ($u$):

  • $C_{m,k,?}$: $k$ is known, $u$ is unknown.
  • $C_{m,?,u}$: $k$ is unknown, $u$ is known.
  • $C_{m,k,u}$: Both $k$ and $u$ are known.

Methods

The authors employ a theoretical framework to analyze data compression limits for voting profiles. Key components of their methodology include:

  1. Compilation Functions: Defining functions that map vote profiles to bit strings. A valid summary must ensure that any two profiles mapping to the same string yield the same winner for any possible set of remaining votes.
  2. h-canceling-out Property: A structural property for anonymous voting rules where a specific set of $h$ votes can "cancel out," leaving the winner unchanged. This helps establish complexity limits as the number of voters approaches infinity.
  3. Upper and Lower Bounds: Upper bounds are established by designing explicit compilation functions (e.g., storing candidate scores). Lower bounds are proven using combinatorial arguments, showing that insufficient bit strings would lead to "blurring" profiles that could result in different winners.

Key Results and Insights

The research reveals that the "intuitive approach" to summarization is often optimal. If the subelectorate is smaller than the expected number of remaining votes, compiling as if the remaining number is unknown is efficient; conversely, if the subelectorate is larger, compiling as if its size is unknown is preferred.

Memory requirements vary significantly across rules:

  • Plurality and l-approval: Require tracking candidate scores ($\\approx m \\log k$ bits).
  • Borda: Requires higher precision in those scores.
  • Condorcet-consistent rules (e.g., Copeland, Maximin): Generally require storing the entire weighted majority graph ($\\approx m^2 \\log k$ bits).

The following table summarizes the derived bounds for various voting rules.

Table 1: Asymptotically tight upper and lower bounds for compilation complexity across various voting rules.

For rules like $l$-approval (when $l \le m/2$), Borda, and Bucklin, the derived bounds are asymptotically tight. For rules based on pairwise match-ups, complexity is tied to the representation of a weighted majority graph.

Limitations and Future Work

The study focuses on anonymous voting rules. Non-anonymous rules, where voter identity matters, would likely exhibit significantly higher complexity. Additionally, recursive rules like Single Transferable Vote (STV) remain unanalyzed due to their mathematical complexity. Future research could explore "streaming" compilation (updating summaries vote-by-vote) and the relationship between compilation complexity and Generalized Scoring Rules (GSRs).

Summary updated

Abstract

In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as the votes of voters outside the subelectorate, we can conclude which of the m alternatives wins. This corresponds to the notion of compilation complexity, the minimum number of bits required to summarize the votes for a particular rule, which was introduced by Chevaleyre et al. [IJCAI-09]. We study three different types of compilation complexity. The first, studied by Chevaleyre et al., depends on the size of the subelectorate but not on the size of the complement (the voters outside the subelectorate). The second depends on the size of the complement but not on the size of the subelectorate. The third depends on both. We first investigate the relations among the three types of compilation complexity. Then, we give upper and lower bounds on all three types of compilation complexity for the most prominent voting rules. We show that for l-approval (when l ≤ m/2), Borda, and Bucklin, the bounds for all three types are asymptotically tight, up to a multiplicative constant; for l-approval (when l > m/2), plurality with runoff, all Condorcet consistent rules that are based on unweighted majority graphs (including Copeland and voting trees), and all Condorcet consistent rules that are based on the order of pairwise elections (including ranked pairs and maximin), the bounds for all three types are asymptotically tight up to a multiplicative constant when the sizes of the subelectorate and its complement are both larger than m1+∊ for some ∊ > 0.
BibTeX
@inproceedings{xia2010compilation,
  author = {Lirong Xia and Vincent Conitzer},
  title = {{Compilation Complexity of Common Voting Rules}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7627},
}
Figure