Coalitional Strategic Behaviour in Collective Decision Making

Grzegorz LisowskiAAAI 2020 · OpenReview

Abstract

In this research project, I investigate the algorithmic aspects of strategic behaviour in collective decision-making, with a specific focus on voting mechanisms. The study explores two primary modes of manipulation: the strategic selection of candidates by groups of representatives and the influence exerted on voters within social networks. By applying tools from computational social choice and game theory, this work seeks to determine the computational complexity of these strategic actions, assessing whether the difficulty of finding optimal strategies serves as a natural safeguard for democratic processes.

Introduction

In an ideal democratic setting, voting is a straightforward aggregation of honest preferences. However, real-world collective decision-making is often a battlefield of strategic manipulation. This research addresses two significant gaps in our understanding of how systems are "gamed":

  1. Candidate Selection: How do coalitions, such as political parties, strategically choose which candidates to field to maximize their collective success? This shifts the focus from individual strategy to coordinated group behavior.
  2. Social Influence: Voters do not make decisions in isolation; they are nodes in complex social networks. How can an agent strategically misrepresent their views to influence their neighbors and ultimately sway an election outcome?

At the heart of this inquiry is computational complexity. If identifying the "perfect" manipulation strategy is computationally "hard" (e.g., NP-complete or PSPACE-complete), the voting mechanism may remain robust in practice simply because the optimal move is too difficult to calculate.

Theoretical Framework and Methodology

The research integrates several mathematical and computational disciplines:

  • Game Theory: Used to identify Nash Equilibria (where no player benefits from changing their strategy) and Dominant Strategy Equilibria (the optimal move regardless of others' actions).
  • Spatial Modeling: The Hotelling-Downs model is employed to place voters and candidates on a multi-dimensional spectrum (e.g., a political left-right axis) to analyze strategic positioning.
  • Graph Theory & Diffusion: Social networks are modeled as directed graphs where opinions spread via threshold models—for instance, a voter might change their mind if a specific percentage of their peers hold a differing view.
  • Complexity Theory: The core of the analysis involves proving whether specific manipulation problems are solvable in polynomial time (tractable) or are NP-complete/PSPACE-complete (intractable).

Key Insights and Algorithmic Results

The Complexity of Stability

In the Hotelling-Downs model, the research demonstrates a sharp divide in complexity. While it is relatively simple to check for the existence of a dominant strategy, finding a Nash Equilibrium becomes NP-complete as soon as more than two parties are involved. This suggests that strategic coordination in multi-party systems is inherently chaotic and computationally difficult to predict.

Tournament Manipulation

In knockout tournaments (such as sports brackets or tiered voting systems), the research established that finding Dominant Strategy Equilibria (DSE) is polynomial (tractable) across all considered settings. However, finding Nash Equilibria is significantly more difficult, often requiring quasi-polynomial time, though it remains tractable in specific dynamic scenarios that go beyond simple win/lose outcomes.

The Unpredictability of Social Influence

One of the most striking findings concerns opinion diffusion. The research proves that determining whether a social network will ever reach a stable state of opinion (convergence) is PSPACE-complete. This indicates that even with simple rules of influence, predicting the long-term behavior of a social network is a fundamentally "hard" problem requiring immense computational resources.

Future Directions

While this research establishes the theoretical difficulty of manipulation, several avenues remain for exploration:

  • The "Majority Illusion": Investigating how network structures can make a minority opinion appear to be a majority to most individuals.
  • Coalition Formation: Analyzing how different parties might form temporary alliances to achieve outcomes that neither could reach individually.
  • Network Constraints: Identifying specific classes of network structures where strategic manipulation is mathematically impossible, providing a blueprint for more resilient decision-making systems.

Summary updated

Abstract

In my PhD project I study the algorithmic aspects of strategic behaviour in collective decision making, with the special focus on voting mechanisms. I investigate two manners of manipulation: (1) strategic selection of candidates from groups of potential representatives and (2) influence on voters located in a social network.
BibTeX
@inproceedings{lisowski2020coalitional,
  author = {Grzegorz Lisowski},
  title = {{Coalitional Strategic Behaviour in Collective Decision Making}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=we6CtLgbiT},
}
Figure