New candidates welcome! Possible winners with respect to the addition of new candidates

Yann Chevaleyre, Jérôme Lang, Nicolas Maudet, Jérôme Monnot, Lirong Xia

TL;DR

This paper investigates the "Possible Cowinner" problem in voting scenarios where new candidates join the race after initial votes have been cast. The authors map out the computational complexity of determining if an original candidate can still win, discovering a sharp "dichotomy" for $K$-approval rules and proving that Borda count remains surprisingly easy to compute even as the candidate pool grows.

What Problem Does This Paper Address?

In traditional voting theory, we usually assume the set of candidates is fixed from start to finish. However, real-world collective decision-making is often dynamic. Think of a Doodle poll for a meeting where a new time slot suddenly becomes available, or a job search where a late applicant enters the pool after the committee has already reviewed the initial pile.

The authors formalize this as the Possible Cowinner Problem with New Candidates (PCWNC). Given a set of initial candidates, a set of votes (rankings) over them, and a fixed number $k$ of new candidates yet to appear, can a specific initial candidate $x^*$ still win? This is a specific type of "voting with incomplete preferences," where the incompleteness comes solely from the unknown positions of the $k$ newcomers in the voters' rankings.

Methods

The paper employs the tools of computational complexity theory to analyze common positional scoring rules (where candidates get points based on their rank).

  • Max-Flow Reductions: To prove that certain cases are "easy" (polynomial-time solvable), the authors reduce the voting problem to a network flow problem. For example, in 2-approval voting, they use a max-flow construction to optimally "place" new candidates in a way that minimizes the threat to the preferred candidate.
  • NP-Completeness Reductions: To prove "hardness," they use reductions from the 3-Dimensional Matching (3-DM) problem. They show that for more complex rules, finding an arrangement of new candidates that allows $x^*$ to win is equivalent to solving a known difficult combinatorial problem.
  • Algorithmic Analysis: For the Borda rule, they provide a constructive proof showing that the "best-case scenario" for a candidate is always to place all newcomers immediately below them in every single vote.

Datasets

Not discussed in the paper. As a theoretical study in computational social choice, the paper relies on mathematical proofs and constructed examples rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • The Borda Advantage: One of the most striking "aha moments" is that the Borda rule—which is generally NP-hard for the "possible winner" problem with arbitrary missing data—becomes easy (polynomial) when the missing data is restricted to new candidates. This is because Borda's scoring is linear; you always know the optimal strategy to help your candidate is to shove all newcomers right below them.
  • The $K$-approval Dichotomy: The authors find a sharp boundary for $K$-approval rules (where voters "approve" their top $K$ choices). If $K \le 2$ or the number of new candidates $k \le 2$, the problem is easy. But as soon as $K \ge 3$ and $k \ge 3$, the problem jumps to being NP-complete.
  • Neutralizing Power: The paper shows how "dummy" candidates can be used in proofs to "neutralize" the points gained by newcomers, a clever technique for proving hardness in voting systems.
  • Dynamic vs. Static Incompleteness: The research highlights that not all "incomplete information" is created equal. Restricting how a vote can be incomplete (i.e., only by adding new candidates at the end) can significantly change the computational burden of finding a winner.

Key Results

The paper provides a comprehensive complexity map for the PCWNC problem:

Voting Rule $k = 1$ (New Candidate) $k = 2$ $k \ge 3$
Plurality Polynomial Polynomial Polynomial
Veto Trivial (Always P) Trivial Trivial
2-approval Polynomial Polynomial Polynomial
$K$-approval ($K \ge 3$) Polynomial Polynomial NP-complete
Borda Polynomial Polynomial Polynomial

Additionally, they prove that for some specific scoring rules (like a 3-2-1-0 scheme), the problem can be NP-complete even with just one new candidate, showing that the "easiness" of Borda and Plurality is not universal.

Limitations and Future Work

  • Scoring Rules Only: The primary focus is on positional scoring rules. The authors suggest that rules based on the "majority graph" (like Condorcet methods) are worth investigating next.
  • No Withdrawals: The paper only looks at candidate addition. In many real-world scenarios, candidates also withdraw, which would add another layer of complexity.
  • Fixed Preferences: The model assumes that the voters' relative rankings of the initial candidates are fixed. It doesn't account for "strategic rethink" where a newcomer might change how a voter perceives the original options.
  • Tie-breaking: The results focus on "cowinners" (can the candidate be one of the winners?). While they note that results for "unique winners" are likely similar, a formal treatment of different tie-breaking rules remains open.

Summary updated

Abstract

In voting contexts, some new candidates may show up in the course of the process. In this case, we may want to determine which of the initial candidates are possible winners, given that a fixed number k of new candidates will be added. We give a computational study of this problem, focusing on scoring rules, and we provide a formal comparison with related problems such as control via adding candidates or cloning. Highlights ► We study voting with a dynamic set of candidates. ► We study the possible winner problem upon candidate addition for scoring voting rules. ► We show that some rules allow efficient determination of possible winners, while some other give rise to algorithmically difficult problems.
BibTeX
@inproceedings{chevaleyre2012new,
  author = {Yann Chevaleyre and Jérôme Lang and Nicolas Maudet and Jérôme Monnot and Lirong Xia},
  title = {{New candidates welcome! Possible winners with respect to the addition of new candidates}},
  booktitle = {Math. Soc. Sci},
  year = {2012},
  url = {https://openreview.net/forum?id=SHFI5J2hxAt},
}

Loading related content...

Figure