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

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.

Introduction: The PCWNC Problem

In traditional voting theory, the set of candidates is typically assumed to be static. However, real-world collective decision-making is often dynamic. For instance, a Doodle poll for a meeting might see a new time slot become available, or a job search committee might receive a late application after initial reviews have already begun.

This paper formalizes this dynamic as the Possible Cowinner Problem with New Candidates (PCWNC). Given an initial set of candidates, a set of voter rankings over them, and a fixed number $k$ of new candidates yet to enter the race, the goal is to determine if a specific initial candidate $x^*$ can still be a winner. This problem represents a specific instance of voting with incomplete preferences, where the uncertainty is restricted solely to the placement of $k$ newcomers within existing rankings.

Methodology: Complexity and Reductions

The authors analyze the PCWNC problem through the lens of computational complexity, focusing on positional scoring rules. To determine if a problem is "easy" (solvable in polynomial time), they often employ Max-Flow Reductions. For example, in 2-approval voting, the problem of placing new candidates to benefit $x^*$ can be mapped to a network flow problem to find an optimal arrangement.

Conversely, to prove "hardness" (NP-completeness), the paper utilizes reductions from the 3-Dimensional Matching (3-DM) problem. These proofs involve constructing complex preference profiles where finding a winning arrangement for $x^*$ is equivalent to solving a known difficult combinatorial task.

Figure 3: An example of a preference profile construction ($v_1$ to $v_{19}$) used in the complexity analysis of $K$-approval rules.

Results: A Map of Computational Complexity

The research provides a comprehensive complexity map for various scoring rules based on the number of new candidates $k$:

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

A key finding is the $K$-approval Dichotomy: while the problem is easy for $K \le 2$ or $k \le 2$, it becomes NP-complete once both $K$ and $k$ are at least 3. This jump in complexity highlights how the interaction between the rule's threshold and the number of newcomers creates combinatorial explosions.

Key Insights: The Borda Exception and Neutralizing Power

One of the most significant results is that the Borda rule remains polynomial-time solvable for PCWNC. While Borda is generally NP-hard for "possible winner" problems with arbitrary missing data, the restriction that missing data only involves new candidates makes it tractable. Because Borda scores are linear, the optimal strategy for $x^*$ is always to place all $k$ newcomers immediately below $x^*$ in every vote.

The paper also introduces the concept of "neutralizing power," where specific candidates or "dummies" are used in proofs to balance the points gained by newcomers. This technique is central to the scoring analysis used in hardness proofs, where voters are partitioned into priority groups to manage score differentials.

Figure 4: Scoring analysis showing the partitioning of voters into priority groups (HP, MP, LP) and the calculated score differences (Δ) for candidates.

Conclusion and Future Work

This study highlights that the nature of "incomplete information" significantly impacts computational tractability. Restricting incompleteness to the addition of new candidates at the end of rankings simplifies some rules (like Borda) while maintaining hardness for others (like $K$-approval).

Future research directions include investigating Condorcet methods based on the majority graph, modeling scenarios where candidates can both join and leave the race, and accounting for strategic behavior where newcomers might change voters' relative preferences among initial candidates.

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.
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},
}
Figure