Equilibria in Strategic Nominee Selection

Grzegorz LisowskiIJCAI 2022 · OpenReview

Abstract

In this research, I explore the game-theoretic problems related to the strategic selection of party nominees. I aim at establishing the complexity of computational problems in this setting. I further study aspects of opinion diffusion protocols related to this problem.

Introduction

In democratic systems, the "primary" election serves as a critical gatekeeping phase. For a political party, selecting a nominee is not merely a matter of internal preference; it is a strategic calculation designed to field a candidate who can win the general election. This research addresses the lack of a rigorous computational understanding of these processes by applying tools from Computational Social Choice and Algorithmic Game Theory to model how parties choose nominees and how voter opinions evolve.

Strategic Selection and Tournament Theory

One of the primary pillars of this research is the analysis of elections modeled as knockout tournaments. In these scenarios, candidates are seeded into a binary tree structure. The study investigates the computational complexity of finding a Nash Equilibrium (NE) when coalitions or parties can strategically choose their representatives to influence the outcome.

Key findings in tournament theory include:

  • Strategic Flexibility: The complexity of finding a stable strategy depends on whether parties can change their nominee between rounds or must commit to one for the duration of the tournament.
  • Computational Bounds: Finding a Nash Equilibrium for coalitions aiming to win the entire tournament can be solved in quasi-polynomial time. If the goal is simply to advance to a certain stage, the problem is solvable in polynomial time.

Spatial Modeling: The Party-Based Hotelling-Downs Model

The research also adapts the classic Hotelling-Downs model of spatial competition. In the traditional model, players choose any point on a 1D spectrum to attract the most voters, and a pure Nash Equilibrium is guaranteed for two players.

This work introduces a more realistic constraint: parties must choose from a finite, fixed set of politicians rather than an infinite spectrum. This restriction fundamentally changes the game's dynamics. The research discovers that in this "primary" scenario, a Nash Equilibrium might not exist at all, even with only two parties. Furthermore, checking for the existence of an NE in this modified model is NP-complete in the general case, though it remains tractable for two-party systems.

Opinion Diffusion and the Majority Illusion

Beyond the mechanics of selection, the research explores how opinions spread within social networks using threshold-based protocols. A significant focus is placed on the "majority illusion"—a social network quirk where a minority opinion appears to be the majority because of the strategic distribution of influencers.

This phenomenon can cause an entire network to adopt a minority opinion after just one round of communication. The research establishes that predicting whether these opinion shifts will ever stabilize into a "steady state" is PSPACE-complete. This high computational bar suggests that predicting the long-term outcomes of social influence is significantly more complex than standard NP-hard problems.

Conclusion and Future Directions

This research establishes that many strategic selection and opinion diffusion problems are computationally intractable (NP-complete or PSPACE-complete) for large-scale systems. This "hardness" suggests that while strategic selection is vital, it is often mathematically difficult to predict or solve optimally.

Future work will focus on:

  • Identifying specific network structures or party constraints where these problems become tractable.
  • Expanding analysis to alternative tournament rules, such as the "Uncovered Set" rule.
  • Investigating the computational difficulty of manipulating or "fixing" a network to eliminate the majority illusion.

Summary updated

Abstract

In my PhD project I explore the game-theoretic problems related to the strategic selection of party nominees. I aim at establishing the complexity of computational problems in this setting. I further study aspects of opinion diffusion protocols related to this problem.
BibTeX
@inproceedings{lisowski2022equilibria,
  author = {Grzegorz Lisowski},
  title = {{Equilibria in Strategic Nominee Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=CtSARftAiJ},
}
Figure