Coalition Tactics: Bribery and Control in Parliamentary Elections

Hodaya Barr, Eden Hartman, Yonatan Aumann, Sarit Kraus

Abstract

Strategic manipulation of elections is typically studied in the context of promoting individual candidates. In parliamentary elections, however, the focus shifts: voters may care more about the overall governing coalition than the individual parties' seat counts. This paper studies this new problem: manipulating parliamentary elections with the goal of promoting the collective seat count of a coalition of parties. We focus on proportional representation elections, and consider two variants of the problem; one in which the sole goal is to maximize the total number of seats held by the desired coalition, and the other with a dual objective of both promoting the coalition and promoting the relative power of some favorite party within the coalition. We examine two types of strategic manipulations: bribery, which allows modifying voters' preferences, and control, which allows changing the sets of voters and parties. We consider multiple bribery types, presenting polynomial-time algorithms for some, while proving NP-hardness for others. For control, we provide polynomial-time algorithms for control by adding and deleting voters. In contrast, control by adding and deleting parties, we show, is either impossible (i.e., the problem is immune to control) or computationally hard, in particular, W[1]-hard when parameterized by the number of parties that can be added or deleted.

Introduction

Traditional social choice theory often focuses on single-winner scenarios, such as presidential races. However, many global democracies operate under parliamentary systems using proportional representation (PR). In these systems, parties gain seats proportional to their vote share and must form coalitions to govern. This paper addresses a significant gap in the literature by exploring how a manipulator can strategically promote an entire coalition of parties, rather than just a single candidate.

Problem Definition

The authors introduce two specific objectives for a manipulator in a parliamentary context:

  1. Joint Objective (J): The goal is to ensure the coalition as a whole reaches a target fraction of seats (e.g., a 51% majority).
  2. Favored-Party Objective (F): This dual objective requires both promoting the coalition and ensuring a specific "favorite" party within that coalition maintains a certain level of relative power.
Formal definition of the Bribery in Parliamentary Elections problem.

Methods

The research employs a combination of algorithmic design and complexity theory. For polynomial-time solvable cases (P), the authors utilize Minimum-Cost Flow (MCF) networks and Dynamic Programming (DP). For example, they demonstrate that voter control can be solved by iterating through possible vote distributions and using DP to find the most cost-effective path. For cases proven to be computationally hard, reductions are made from known NP-hard and parameterized-hard problems, such as 3-4-Exact-Cover and k-Clique. The analysis covers various bribery models, including flat-rate "1-bribery," voter-specific "$-bribery," and "Swap/Shift bribery" based on the degree of preference change.

Key Insights: The Impact of Electoral Thresholds

A critical finding is the role of the electoral threshold ($\tau$). In many PR systems, a party must meet a minimum vote percentage to enter parliament. The authors show that without this threshold ($\tau=0$), many bribery problems are solvable in polynomial time. However, once a threshold is introduced ($\tau > 0$), these same problems often become NP-hard. This is because the manipulator must strategically decide which parties to "push" over the threshold and which to let fail to maximize the coalition's total share.

Key Results

The paper provides a comprehensive map of the computational complexity associated with different coalition tactics, distinguishing between those that are efficiently solvable and those that are intractable.

Summary table of complexity results for various bribery types and objectives.

Key results include:

  • Bribery: 1-bribery and $-bribery are consistently in P. Swap and Shift bribery are in P if $\tau=0$, but become NP-hard if $\tau > 0$.
  • Voter Control: Adding or deleting voters remains in P regardless of thresholds or dual objectives.
  • Party Control: This is generally much harder. Most variants (adding/deleting opposition or coalition parties) are W[1]-hard or W[2]-hard when parameterized by the number of parties changed, indicating they do not scale efficiently.

Conclusion and Future Work

This study establishes a foundational complexity analysis for coalition-based manipulation. However, it assumes coalitions are fixed before the election. Real-world coalitions are often negotiated post-election based on final results. Future research could explore dynamic coalition formation, destructive manipulation (preventing a rival coalition), and tactical moves like party mergers or splits, which are common in parliamentary politics.

Summary updated

Abstract

Strategic manipulation of elections is typically studied in the context of promoting individual candidates. In parliamentary elections, however, the focus shifts: voters may care more about the overall governing coalition than the individual parties' seat counts. This paper studies this new problem: manipulating parliamentary elections with the goal of promoting the collective seat count of a coalition of parties. We focus on proportional representation elections, and consider two variants of the problem; one in which the sole goal is to maximize the total number of seats held by the desired coalition, and the other with a dual objective of both promoting the coalition and promoting the relative power of some favorite party within the coalition. We examine two types of strategic manipulations: \emph{bribery}, which allows modifying voters' preferences, and \emph{control}, which allows changing the sets of voters and parties. We consider multiple bribery types, presenting polynomial-time algorithms for some, while proving NP-hardness for others. For control, we provide polynomial-time algorithms for control by adding and deleting voters. In contrast, control by adding and deleting parties, we show, is either impossible (i.e., the problem is immune to control) or computationally hard, in particular, W[1]-hard when parameterized by the number of parties that can be added or deleted.
BibTeX
@misc{barr2026coalition,
  author = {Hodaya Barr and Eden Hartman and Yonatan Aumann and Sarit Kraus},
  title = {{Coalition Tactics: Bribery and Control in Parliamentary Elections}},
  year = {2026},
  eprint = {2601.07279},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.07279},
}
Figure