Abstract
We define a new class of low-communication voting rules, tailored for contexts with few voters and possibly many candidates. These rules are defined by a predefined sequence of voters: at each stage, the designated voter eliminates a candidate, and the last remaining candidate wins. We study both deterministic (non-anonymous) variants, and randomized (and anonymous) versions of these rules. We focus on a subfamily of these rules defined by "non-interleaved" sequences. We first focus on the axiomatic properties of our rules. Then we focus on the identification of the non-interleaved sequence that gives the best approximation of the Borda score under the impartial culture. Finally, we apply our rules to randomly generated data. Our conclusion is that, in contexts where there are more candidates than voters, elimination-based rules allow for a very low communication complexity (and especially, avoid asking voters to rank alternatives), and yet can be good approximations of common voting rules, while enjoying a number of good properties.
Introduction
In social choice theory, traditional voting rules like the Borda count or Condorcet methods often require voters to provide a complete ranking of all candidates. While these methods are mathematically robust, they impose a significant communication burden and cognitive load, especially when the number of candidates ($m$) is large compared to the number of voters ($n$). For example, a small group of friends choosing a restaurant from dozens of options would find ranking every single choice tedious.
This research addresses this gap by proposing Sequential Elimination Rules (SER). These rules are specifically designed for low-communication environments where efficiency and ease of use are paramount.
The Sequential Elimination Rule
The mechanism of an SER is straightforward:
- A predefined sequence of voters is established.
- At each step, the designated voter "vetoes" or eliminates one candidate from the current pool.
- This continues until only one candidate remains, who is then declared the winner.
The authors explore two primary variants: Deterministic SER, where the sequence of specific voters is fixed, and Randomized SER, where a pattern of slots is fixed and voters are randomly assigned to slots to maintain anonymity and fairness. A specific focus is placed on non-interleaved sequences, where each voter performs all their assigned eliminations in a single continuous block.
Performance and Optimal Sequences
To evaluate these rules, the authors use the Borda score—the average rank of a candidate across all voters—as a proxy for social welfare. They seek sequences that maximize the expected Borda score of the winner.
As shown in Figure 1, different sequences yield varying levels of performance. Under the Impartial Culture (IC) model, the optimal non-interleaved sequence typically follows a geometric decay, where earlier voters eliminate more candidates than later ones. Interestingly, while non-interleaved sequences are easier to analyze, "round-robin" sequences (where voters take turns in a repeating cycle) often prove more robust in practice because they allow for more interaction between individual preferences.
Empirical Validation
The effectiveness of SERs was tested against several synthetic preference models, including Impartial Culture (IC), Mallows models, and Single-Peaked cultures (SPIC, SPUP). Additionally, the rules were applied to the real-world Sushi dataset from PrefLib.
The results, summarized in Figure 2, demonstrate that SERs consistently achieve high social welfare. In most simulations, the rules captured over 90% of the optimal Borda score. In highly correlated environments like the Mallows model ($M_{0.1}$), the efficiency reached as high as 99.5%. On the real-world Sushi dataset, the best sequence achieved a 93.035% Borda efficiency.
Axiomatic Properties and Complexity
Despite their simplicity, SERs satisfy several critical axiomatic properties:
- Pareto-efficiency: They never select a candidate that is unanimously disliked compared to another.
- Monotonicity: Improving a winning candidate's position in a voter's preference cannot cause them to lose.
- Neutrality: The rules do not inherently favor any specific candidate.
From a computational standpoint, while the rules are easy to execute, determining if a specific candidate could win under a randomized sequence is NP-complete. However, in practical applications like smartphone apps, the actual winner is computed instantly once the sequence is executed.
Conclusion
Sequential elimination rules offer a compelling alternative for small-group decision-making. They significantly reduce communication complexity—requiring only $O(m \log m)$ bits—while maintaining high social welfare. Future work may explore "support-based" models for scenarios where voters outnumber candidates and investigate the strategyproofness of these elimination sequences.
Summary updated