Borda Count in Collective Decision Making: A Summary of Recent Results

Jörg Rothe

Borda Count in Collective Decision Making: A Summary of Recent Results

Introduction

The Borda count, a voting rule introduced over 230 years ago, remains a cornerstone of social choice theory. In a Borda election, voters rank $m$ candidates, assigning $m-1$ points to their top choice, $m-2$ to the second, and so on, down to 0 points for the last-ranked candidate. While its social-choice properties are well-documented, recent research has pivoted toward the computational aspects of this rule. This paper synthesizes a decade of research, primarily by Jörg Rothe and colleagues, exploring Borda through the lens of computational social choice. It examines how computational complexity serves as a safeguard against strategic behavior and how Borda’s principles can be extended to modern AI challenges like resource allocation and coalition formation.

Computational Complexity as a "Mathematical Shield"

A central theme in modern social choice is the use of computational complexity to protect the integrity of elections. If a strategic attack—such as manipulation by a group of voters or control by an election chair—is proven to be NP-hard, it suggests that finding a successful strategy is computationally infeasible for large-scale instances. This "shield" ensures that even if a theoretical way to "rig" an election exists, it may be impossible to execute in practice.

One of the most significant breakthroughs in this area was the resolution of the complexity of Constructive Coalitional Unweighted Manipulation (CCUM). For years, it was unclear how hard it was for a small group of voters to coordinate their ballots to ensure a specific candidate wins. In 2011, it was definitively shown that even with just two manipulators, Borda manipulation is NP-complete.

Key Results in Election Control

Election control refers to attempts by an external actor (the "chair") to alter the outcome by adding, deleting, or partitioning voters or candidates. Research shows a distinct asymmetry between "constructive" control (aiming to make a candidate win) and "destructive" control (aiming to make a candidate lose).

As shown in the table below, Borda is remarkably resistant to constructive control, with almost all scenarios being NP-complete (NPC). Conversely, many destructive control scenarios are computationally "easy" (in P), meaning a chair can efficiently determine how to prevent a candidate from winning.

Complexity results for various types of control in Borda elections.

A notable gap in current knowledge is the complexity of Destructive Control by Partition of Candidates in the Ties-Promote model (DCPC-TP), which remains an open question in the field.

Beyond Voting: Resource Allocation and Games

The utility of the Borda count extends far beyond simple balloting. Its scoring system provides a natural way to quantify agent preferences in multi-agent systems:

  1. Fair Division: Borda scores can represent an agent's "happiness" with a bundle of goods. Finding an allocation that maximizes social welfare or meets specific egalitarian thresholds is often NP-complete, highlighting the inherent difficulty of fair resource distribution.
  2. Hedonic Games: In coalition formation, Borda-induced preferences can determine how agents group together. While verifying Nash stability (where no agent wants to move to another existing coalition) is easy (in P), checking for Core stability (where no group of agents wants to break away to form a new coalition) is significantly harder, categorized as coNP-complete.

Conclusion and Future Directions

The Borda count continues to be a fertile ground for research. While its "worst-case" NP-hardness provides a theoretical barrier against manipulation, future work must address "average-case" complexity to see if heuristics can bypass these shields in typical scenarios. Furthermore, the application of Borda-based logic to new domains in AI and decentralized systems remains a promising frontier.

Summary updated

Abstract

Borda Count is one of the earliest and most important voting rules. Going far beyond voting, we summarize recent advances related to Borda in computational social choice and, more generally, in collective decision making. We first present a variety of well known attacks modeling strategic behavior in voting—including manipulation, control, and bribery—and discuss how resistant Borda is to them in terms of computational complexity. We then describe how Borda can be used to maximize social welfare when indivisible goods are to be allocated to agents with ordinal preferences. Finally, we illustrate the use of Borda in forming coalitions of players in a certain type of hedonic game. All these approaches are central to applications in artificial intelligence.
BibTeX
@inproceedings{rothe2019borda,
  author = {Jörg Rothe},
  title = {{Borda Count in Collective Decision Making: A Summary of Recent Results}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019830},
}
Figure