Source-linked AI summary
Determining Possible and Necessary Winners Given Partial Orders
Lirong Xia, Vincent Conitzer
TL;DR
The paper asks how possible and necessary winner questions can be solved when voters submit partial orders rather than complete rankings. It characterizes the complexity of four winner variants across several voting rules in unweighted elections with an unbounded number of alternatives. The results identify broad NP-completeness and coNP-completeness patterns, alongside polynomial-time cases.
Problem
Complete rankings can be impractical, motivating possible and necessary winner questions over linear extensions of voters’ partial orders.
Method
The paper characterizes possible/necessary winner complexity for positional scoring rules, Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.
Results
Possible-winner problems are NP-complete for the listed rules except plurality with runoff’s possible unique-winner case, while selected necessary-winner variants are coNP-complete and remaining cases have polynomial-time algorithms.
Takeaways & Limitations
The results provide a complexity map for deciding whether candidates can or must win under partial preferences across common voting rules.
Takeaways & Limitations
The analysis allows arbitrary partial orders, so negative results may not immediately apply to the more structured partial orders induced by CP-nets.
Abstract
from arXiv · showhide
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.
1. Introduction
Partial orders address the impracticality of eliciting complete rankings, while possible and necessary winner problems ask whether a candidate can win under some or all linear extensions. The paper characterizes these problems for several common voting rules in unweighted elections with an unbounded number of alternatives.
- Motivation: Partial orders arise when alternatives are too numerous to rank completely or when agents cannot compare some alternatives.The paper connects partial orders to preference languages such as CP-nets and to incomparability between alternatives.
- Research questions: Possible winner asks whether candidate c wins under some linear extension, whereas necessary winner asks whether c wins under every extension.Each problem has unique-winner and co-winner variants.
- Setting: The paper studies unweighted votes with an unbounded number of alternatives, a setting distinct from bounded-alternative weighted elections.With bounded alternatives and unweighted votes, these problems are polynomial-time solvable when the voting rule is polynomial-time computable.
- Main results: Possible winner is NP-complete for the studied rules except plurality with runoff’s possible unique-winner problem, while several necessary-winner variants are coNP-complete and the remaining cases are polynomial-time solvable.The characterized rules include positional scoring rules, Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.
- Novelty: The paper corrects an earlier claim by showing hardness for some positional scoring rules while retaining polynomial-time solvability of necessary winner for all positional scoring rules.Borda is among the rules covered by the hardness results.
- Novelty: The extended paper adds complete proofs and new results on voting trees, plurality with runoff, and k-approval beyond the conference version.Later work fully characterized possible-winner complexity for positional scoring rules, including Borda and k-approval.
2. Preliminaries
The preliminaries define the preference, profile, voting-rule, and winner concepts used throughout the paper. They also specify the major voting rules and the parallel-universes treatment of ties in multiround rules.
- Basic notation: A linear order is transitive, antisymmetric, and total; a profile contains one linear order for each voter.The paper uses m for the number of alternatives and n for the number of voters.
- Basic notation: A voting rule maps every profile to a nonempty set of winning alternatives.The paper represents positional scoring, pairwise, and multiround rules within this framework.
- Voting rules: Positional scoring rules assign scores by rank and select alternatives with maximum total score; examples include Borda, plurality, veto, and k-approval.The scoring vector is assumed computable in polynomial time.
- Voting rules: Copeland awards points for pairwise majority wins, while maximin selects alternatives maximizing their weakest pairwise support.Bucklin selects alternatives with the smallest rank level at which more than half the votes place them among the top k.
- Voting rules: Ranked pairs orders alternatives by locking the strongest not-yet-considered pairwise comparisons without violating transitivity.Voting trees use binary pairwise contests, and plurality with runoff retains the two leading first-place alternatives for a final plurality contest.
- Voting rules: Single transferable vote repeatedly eliminates the alternative with the lowest plurality score until one alternative remains.The paper also defines pairwise score differences and relates them to pairwise scores by DP(c,c′) = 2NP(c,c′) − n.
- Tie-breaking: For ranked pairs, voting trees, plurality with runoff, and STV, an alternative wins when some tie-breaking choices make it the winner.This is the adopted parallel-universes tiebreaking convention.
- Partial orders: A linear order extends a partial order when it preserves every pairwise preference specified by the partial order.The notation distinguishes linear orders, partial orders, and profiles of each.
3. Possible/Necessary Winners
Possible and necessary winner notions quantify how a candidate fares across linear extensions of partial-order profiles. The section formalizes four variants and establishes relationships among their computational problems.
- Definitions: A possible winner wins uniquely in at least one extension, whereas a necessary winner wins uniquely in every extension.The corresponding co-winner variants require membership in the winner set rather than sole victory.
- Definitions: The four computational problems are Possible Winner, Necessary Winner, Possible co-Winner, and Necessary co-Winner.They are defined by asking whether the corresponding condition holds for a given candidate and partial-order profile.
- Relationships: If Possible co-Winner is polynomial-time solvable for a voting rule, Necessary Winner is also polynomial-time solvable for that rule.The reduction tests whether any alternative other than c is a possible co-winner.
- Relationships: Possible Winner and Necessary co-Winner do not have the same general reduction relationship as Necessary Winner and Possible co-Winner.The paper gives plurality profiles showing that answers to one problem can agree while answers to another differ.
- Relationships: Plurality constructions demonstrate that the four winner notions are generally distinct, including cases where possible unique-winner and possible co-winner answers diverge.The constructions use partial orders whose sets of possible top-ranked alternatives are controlled across profiles.
- Examples: For some plurality profiles, adding another partial order can make c the only necessary winner because c must rank first in at least two votes.This illustrates how profile structure affects necessary-winner status.
4. Hardness Results
The paper establishes broad hardness results for possible and necessary winner problems under unbounded alternatives and unweighted votes, using reductions that encode combinatorial constraints in partial-order extensions.
- Positional scoring rules and general hardness: PW and PcW are NP-complete for a class of positional scoring rules, Copeland, maximin, Bucklin, ranked pairs, and voting trees.The results for positional scoring rules do not cover plurality and veto, for which PW is easy.
- Positional scoring rules and general hardness: PW and PcW are NP-complete for Borda, even when each vote has at most 4 undetermined pairs.The proof applies a sufficient condition for positional scoring rules to Borda.
- Positional scoring rules and general hardness: For every fixed k ≥2, PW and PcW are NP-complete for k-approval, even when each vote has at most 4 undetermined pairs.The reduction is first established for 2-approval and then extended to larger fixed k by adding alternatives to control the top positions.
- Other voting rules: Copeland has NP-complete PW and PcW problems and coNP-complete NW and NcW problems, even with at most 8 undetermined pairs per vote.The reductions connect feasible extensions to exact-cover solutions.
5. Polynomial-time Algorithms for Possible and Necessary Winner Problems
The section presents polynomial-time tests for necessary-winner variants under positional scoring rules, maximin, and Bucklin, plus possible co-winner and necessary unique-winner tests for plurality with runoff. The algorithms construct adversarial extensions of partial orders, using score comparisons or maximum flow where appropriate.
- Section overview: Polynomial-time algorithms decide necessary winners for all positional scoring rules, maximin, and Bucklin, and decide plurality-with-runoff possible co-winners and necessary unique winners.The section contrasts these tractable cases with plurality-with-runoff possible unique winners and necessary co-winners, which are stated to be NP-complete and coNP-complete, respectively.
- Positional scoring rules: For score-based rules, each alternative w ≠ c is tested by constructing extensions that minimize the score difference S(c) − S(w).When c is not forced above w, the algorithm places w as high and c as low as the partial orders permit; when c is forced above w, it positions the intervening block as favorably as possible for w.
- Positional scoring rules: Algorithm 1 checks necessary winners for any positional scoring rule in polynomial time by comparing the resulting scores of c against every rival.The necessary co-winner variant changes the rejection test from S(w) ≥ S(c) to S(w) > S(c).
- Maximin: Algorithm 2 checks necessary winners for maximin in polynomial time by considering rival pairs and pairwise-preference counts across extensions.The construction handles conflicts between placing w′ above c and placing w as high as possible, then checks the relevant inequalities for all alternatives d.
- Bucklin: Algorithm 3 checks necessary winners for Bucklin in polynomial time by seeking an extension where a rival reaches a favorable top-k threshold relative to c.For each k, it attempts to place w among the top k in more than half the votes while keeping c among the top k−1 in at most half.
- Plurality with runoff: For plurality with runoff, possible co-winner testing reduces to maximum-flow feasibility, and the same test yields a polynomial-time necessary unique-winner algorithm.A flow of value n corresponds to an extension in which c and a selected rival enter the runoff together and c is a co-winner.
6. Conclusion and Future Work
The paper characterizes possible and necessary winners for unweighted votes with unbounded alternatives, while noting boundaries involving structured partial orders and approximation.
- The study determines which alternatives are possible or necessary winners under some or all extensions of partial orders.The results apply whether an alternative must be a unique winner or merely a co-winner, unless specifically stated otherwise.
- The analysis imposes no restriction on the partial orders themselves.If partial orders arise from CP-nets, their additional structure means not every partial order is representable.
- Positive results continue to apply to CP-net-induced partial orders, but the negative results do not immediately carry over.
- Approximating possible and necessary winner sets is identified as another direction, with conjectured inapproximability for many rules whose exact problems are (co-)NP-complete.The cited prior work proves inapproximability for single transferable vote; the broader claim is presented as a conjecture.