TL;DR
In real-world voting scenarios, voters often can't rank every single candidate, resulting in partial preferences. This paper completely characterizes the computational complexity of determining whether a candidate could win (Possible Winner) or must win (Necessary Winner) under these partial orders for common voting rules. The authors reveal that while checking if someone must win is often computationally easy, figuring out if they could win is usually highly complex (NP-complete).
What Problem Does This Paper Address?
In traditional social choice theory, voters are asked to provide a "linear order"—a strict, complete ranking of every available candidate or alternative. However, in multiagent systems and real-world applications, this is often impractical. There might be too many alternatives to rank, voters might find certain options incomparable, or an AI might be in the middle of incrementally eliciting a user's preferences.
This results in a partial order of preferences. Given a specific voting rule and a set of these partial orders, two fundamental questions arise for any given candidate $c$:
- Possible Winner (PW): Is there at least one valid way to fill in the blanks (extend the partial orders to linear orders) such that candidate $c$ wins?
- Necessary Winner (NW): Does candidate $c$ win in every single valid completion of the partial orders?
The authors set out to map the exact computational complexity of these two problems across a wide variety of standard voting rules (like Borda, Copeland, maximin, Bucklin, and ranked pairs) in elections where votes are unweighted and the number of candidates is unbounded.
Methods
This is a theoretical computer science paper that relies on complexity analysis and algorithm design:
- Hardness Proofs: To prove that finding a Possible or Necessary Winner is computationally intractable (NP-complete or coNP-complete), the authors use polynomial-time reductions from known hard problems, specifically Exact 3-Cover (X3C) and 3-SAT.
- Profile Construction: A recurring, clever technique in their proofs is splitting the simulated electorate into two groups. The first group submits partial orders that encode the logic of the X3C or 3-SAT problem. The second group submits fully completed linear orders designed purely to adjust the baseline scores or pairwise matchups of the candidates. This perfectly isolates the "unknown" variables to simulate computational gates.
- Algorithm Design: For the rules where the problems are tractable (in P), the authors design polynomial-time algorithms. These generally work by constructing a "worst-case" scenario for candidate $c$—greedily maximizing the score of a rival while minimizing $c$'s score—and checking if $c$ still survives. For the "plurality with runoff" rule, they ingeniously map the problem to a Maximum Flow network graph.
Datasets
Not discussed in the paper. (This is a theoretical paper focused on algorithmic complexity and mathematical proofs, so no empirical datasets were used).
Key Insights and Ideas
- The Asymmetry of Difficulty: There is a fascinating split in complexity. Finding a Possible Winner is generally much harder than verifying a Necessary Winner. It is computationally easier to prove someone isn't a guaranteed winner (you just need to construct one valid counter-example where they lose) than to search the exponentially large space of all possible preference completions to find the one specific scenario where they win.
- Hardness Holds Even with Tiny Unknowns: You might think the problem is only hard if the voters leave their ballots mostly blank. Surprisingly, the authors prove that the Possible Winner problem remains NP-complete even if the number of undetermined pairs in each voter's partial order is bounded by a tiny constant (e.g., just 4 or 8 unknown relationships per voter).
- Graph Theory Meets Voting: The realization that the Possible co-Winner problem for "plurality with runoff" can be perfectly modeled as a Maximum Flow problem is a brilliant algorithmic crossover, showing how classic network routing algorithms can solve social choice problems.
Key Results
The authors provide a complete taxonomy of complexity for the studied rules:
- NP-Complete (Computationally Hard): The Possible Winner problem is NP-complete for positional scoring rules (including Borda and k-approval), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff (when looking for a unique winner).
- coNP-Complete (Computationally Hard): The Necessary Winner problem is coNP-complete for Copeland, ranked pairs, voting trees, and plurality with runoff (when looking for a co-winner).
- Polynomial Time (Efficiently Solvable): The Necessary Winner problem can be solved efficiently for positional scoring rules, maximin, and Bucklin. The Possible co-Winner problem for plurality with runoff is also solvable in polynomial time.
Limitations and Future Work
- Unrestricted Partial Orders: The paper assumes that the partial orders can take any arbitrary shape. However, if partial preferences are generated by specific representation languages (like CP-nets, often used in AI), they have an inherent structural logic. The authors note that their negative (hardness) results might not automatically apply if the partial orders are strictly constrained by such structures.
- Approximations: Because finding the exact set of possible or necessary winners is NP-hard for many common rules, the authors suggest that future work should focus on approximation algorithms. A promising direction is developing algorithms that can efficiently output a superset or subset of the winners that is guaranteed to be within a fixed ratio of the true set's size.
Summary updated