Abstract
Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners). We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.
Introduction
In traditional social choice theory, voters are typically asked to provide a "linear order"—a strict, complete ranking of every available candidate. However, in multiagent systems and real-world applications, this requirement is often impractical. There might be too many alternatives to rank, or voters might find certain options incomparable. This lead to the submission of partial orders 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 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?
This paper maps the exact computational complexity of these two problems across a wide variety of standard voting rules in elections where votes are unweighted and the number of candidates is unbounded.
Methodology
The authors utilize complexity analysis and algorithm design to categorize these problems:
- 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 technique involves splitting the electorate into two groups. The first group submits partial orders encoding the logic of the hard problem, while the second group submits fully completed linear orders to adjust baseline scores or pairwise matchups.
- Algorithm Design: For 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$ and checking if they still survive. For the "plurality with runoff" rule, they map the problem to a Maximum Flow network graph.
Key Results and Insights
The research reveals a significant asymmetry in complexity: determining if a candidate could win is generally much harder than verifying if they must win.
Key findings include:
- Computational Hardness: The Possible Winner problem is NP-complete for most studied rules, including positional scoring rules (like Borda), Copeland, maximin, Bucklin, and ranked pairs. The Necessary Winner problem is coNP-complete for rules like Copeland, ranked pairs, and voting trees.
- Tractable Cases: The Necessary Winner problem can be solved efficiently (in P) for positional scoring rules, maximin, and Bucklin.
- Persistence of Hardness: Surprisingly, 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).
Conclusion and Future Work
While this paper provides a complete taxonomy for arbitrary partial orders, the authors note that their hardness results might not automatically apply if partial preferences are constrained by specific structural logics (like CP-nets). Future work should focus on approximation algorithms that can efficiently output a subset or superset of winners when exact determination is NP-hard.
Summary updated