Solving Seven Open Problems of Offline and Online Control in Borda Elections

Marc Neveling, Jörg Rothe

Introduction

In the field of computational social choice, the integrity of voting systems is often measured by their resistance to manipulation. A common form of manipulation is control, where an election "chair" attempts to alter the outcome by changing the structure of the election—for instance, by adding or removing voters or candidates. A voting system is considered resistant if the control problem is NP-hard, providing a computational barrier against such interference. Conversely, if a control strategy can be found in polynomial time, the system is deemed vulnerable.

This paper focuses on the Borda Count, a widely used and "natural" voting system where candidates receive points based on their rank in each voter's preference list. Despite its popularity, several gaps remained in our understanding of its complexity. This research settles seven open problems, distinguishing between offline control (where all information is known upfront) and online control (where candidates appear sequentially).

Methodology

The researchers utilized standard computational complexity proofs to categorize these problems:

  • For Offline Resistance: The authors employed polynomial-time reductions from known NP-complete problems. They reduced Exact Cover by 3-Sets (X3C) to prove the hardness of deleting voters, PARTITION for partitioning voters, and 3SAT for partitioning candidates.
  • For Online Vulnerability: The authors developed polynomial-time algorithms based on a "maximin" strategy. These algorithms determine if a preferred candidate can be guaranteed a win regardless of how future, unrevealed candidates are ranked, essentially checking if any "bad" candidate can overcome their current deficit in the worst-case future scenario.

Key Results: Offline Resistance

The paper proves that the Borda Count is resistant to several sophisticated forms of offline manipulation. Specifically, it establishes that constructive control by deleting voters (a model for vote suppression), partition of voters (a model for gerrymandering), and run-off partition of candidates are all NP-hard.

Summary of Borda control complexity. The symbols in the table denote the complexity status (R for Resistant, V for Vulnerable), with specific icons marking the new results established in this work.

As shown in the table above, these results fill critical gaps in the Borda complexity landscape, confirming that the system possesses inherent computational defenses against these specific structural attacks.

Key Results: Online Vulnerability

In a surprising contrast to the offline results, the paper finds that Borda is vulnerable to various forms of online control. In scenarios where candidates are introduced one by one and the chair must make immediate decisions (e.g., whether to delete a candidate) without full knowledge of future arrivals, the control problem becomes computationally easy (solvable in polynomial time).

The authors provide efficient algorithms for four online scenarios:

  1. Constructive and Destructive Control by Deleting Candidates (CCDC, DCDC)
  2. Constructive and Destructive Control by Adding Candidates (CCAC, DCAC)

This is a significant finding because previous research on online control often relied on "artificial" voting systems designed specifically to be hard. This work shows that for a natural system like Borda, the transition to an online setting can actually simplify the chair's computational task.

Conclusion and Future Work

By settling these seven problems, the paper provides a more complete picture of the Borda Count's robustness. While it is resistant to complex offline structural changes, its vulnerability in online settings highlights a potential weakness in sequential election processes.

Future research directions include exploring the "Ties-Promote" (TP) model for partitions, which remains an open question for Borda, and seeking a general "dichotomy result" that could predict the resistance or vulnerability of all scoring protocols across all types of control.

Summary updated

Abstract

Standard (offline) control scenarios in elections (such as adding, deleting, or partitioning either voters or candidates) have been studied for many voting systems, natural and less natural ones, and the related control problems have been classified in terms of their complexity. However, for one of the most important natural voting systems, the Borda Count, only a few such complexity results are known. We reduce the number of missing cases by pinpointing the complexity of three control scenarios for Borda elections, including some that arguably are among the practically most relevant ones. We also study online candidate control, an interesting dynamical, partial-information model due to Hemaspaandra et al. (2012a), who mainly focused on general complexity bounds by constructing artificial voting systems—only recently they succeeded in classifying four problems of online candidate control for one natural voting system: sequential plurality (Hemaspaandra et al. 2016). We settle the complexity of another four natural cases: constructive and destructive online control by deleting and adding candidates in sequential Borda elections.
BibTeX
@inproceedings{neveling2017solving,
  author = {Marc Neveling and Jörg Rothe},
  title = {{Solving Seven Open Problems of Offline and Online Control in Borda Elections}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10703},
}
Figure