Control by Deleting Players from Weighted Voting Games Is NP PP {}^{\text{PP}} -Complete for the Penrose–Banzhaf Power Index
Joanna Kaczmarek, Jörg Rothe · 2025
Read Control by Deleting Players from Weighted Voting Games Is NP PP {}^{\text{PP}} -Complete for the Penrose–Banzhaf Power Index by Joanna Kaczmarek, Jörg Rothe (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13868.txt.
Introduction
Joanna Kaczmarek and Jörg Rothe settled in 2025 how computationally hard it is to rig a weighted voting game by removing players. In such games, players hold different vote weights and power is measured by the Penrose-Banzhaf index, the chance a player swings the outcome. Earlier work had resolved the difficulty of adding players but left deletion open.
They prove several deletion problems are complete for a high complexity class that sits above ordinary NP, using oracles for probabilistic counting. That jumps well past the previously known lower bounds. Practically, such hardness shields real voting systems against solver-based manipulation attacks. The result closes a gap in the theory of control in coalitional games.
Catalog record
| CREATOR | Joanna Kaczmarek, Jörg Rothe |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 136 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13868
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Control by Deleting Players from Weighted Voting Games Is NP PP {}^{\text{PP}} -Complete for the Penrose–Banzhaf Power Index Joanna Kaczmarek, Jörg Rothe Abstract Weighted voting games are a popular class of coalitional games that are widely used to model real-life situations of decision-making. They can be applied, for instance, to analyze legislative processes in parliaments or voting in corporate structures. Various ways of tampering with these games have been studied, among them merging or splitting players, fiddling with the quota, and controlling weighted voting games by adding or deleting players. While the complexity of control by adding players to such games so as to change or maintain a given player’s power has been recently settled, the complexity of control by deleting players from such games (with the same goals) remained open. We show that when the players’ power is measured by the probabilistic Penrose–Banzhaf index, some of these problems are complete for NP PP \mathrm{NP}^{\mathrm{PP}} —the class of problems solvable by NP \mathrm{NP} machines equipped with a PP \mathrm{PP} (“probabilistic polynomial time”) oracle. Our results optimally improve the currently known lower bounds of hardness for much smaller complexity classes, thus providing protection against SAT-solving techniques in practical applications. † † paperid: 3527 † † orcid: 0000-0001-6652-6433 † † orcid: 0000-0002-0589-3616 1 Introduction Due to their numerous applications in real-life decision-making, weighted voting games (WVGs), a popular class of simple coalitional games, have been studied intensively for the last decades (see the book chapters by Bullinger et al. [ Bullinger et al.(2024)Bullinger, Elkind, and Rothe ] and Chalkiadakis and Wooldridge [ Chalkiadakis and Wooldridge(2016) ] ). WVGs have been applied to model and analyze collective decision-making in legislative processes and for voting in parliaments [ Shapley(1981) ] (e.g., the parliament of the European Union) or in corporate structures (such as the International Monetary Fund [ Gambarelli(1994) ] ); it can also be used for making decisions in joint stock companies where the shareholders’ stock values specify their weights, etc. A central question with regard to WVGs is how significant the players in them are, that is, how much influence they have when it comes to forming winning coalitions. This is typically measured by so-called power indices. We focus on the probabilistic Penrose–Banzhaf index , which is due to Dubey and Shapley [ Dubey and Shapley(1979) ] who were seeking to avoid certain disadvantages of the normalized Penrose–Banzhaf index , originally proposed by Penrose [ Penrose(1946) ] and later re-invented by Banzhaf [ Banzhaf III(1965) ] . Prasad and Kelly [ Prasad and Kelly(1990) ] showed that computing the probabilistic Penrose–Banzhaf index is \#\mathrm{P} -complete even under parsimonious reductions (which preserve the number of solutions). Here, \#\mathrm{P} denotes Valiant’s “counting class” of functions that give the number of solutions of \mathrm{NP} problems [ Valiant(1979) ] . Certain ways of how to tamper with the outcome of WVGs have been studied. For example, Zuckerman et al. [ Zuckerman et al.(2012)Zuckerman, Faliszewski, Bachrach, and Elkind ] considered the consequences of manipulating the quota of a given WVG. Aziz et al. [ Aziz et al.(2011)Aziz, Bachrach, Elkind, and Paterson ] introduced the notions of merging, splitting, 1 1 1 “Splitting players” is also known as “false-name manipulation.” and annexing players in WVGs and studied the complexity of whether such actions can be beneficial in terms of raising a distinguished player’s power for the Shapley–Shubik [ Shapley and Shubik(1954) ] and the normalized Penrose–Banzhaf index. Later on, Rey and Rothe [ Rey and Rothe(2014) ] improved their \mathrm{NP} -hardness lower bounds to \mathrm{PP} -hardness for merging and splitting players with respect to the Shapley–Shubik index (and established \mathrm{PP} -hardness of these problems also for the probabilistic Penrose–Banzhaf index), where \mathrm{PP} denotes the complexity class “probabilistic polynomial time,” which is due to Gill [ Gill(1977) ] and contains both \mathrm{NP} and \mathrm{coNP} , and even \mathrm{P}^{\mathrm{NP}[\mathcal{O}(\log n)]} [ Beigel et al.(1991)Beigel, Hemachandra, and Wechsung ] , a.k.a. \Theta_{2}^{p} , the class of problems solvable in deterministic polynomial time with at most logarithmically many queries to an \mathrm{NP} oracle. Faliszewski and Hemaspaandra [ Faliszewski and Hemaspaandra(2009) ] proved that comparing a given player’s Shapley–Shubik or probabilistic Penrose–Banzhaf index in two given WVGs is \mathrm{PP} -complete. Rey and Rothe [ Rey and Rothe(2018) ] introduced control by either adding players to or removing them from a given WVG, and they established the first complexity results for the corresponding problems. Their work was continued by Kaczmarek and Rothe [ Kaczmarek and Rothe(2024b) , Kaczmarek and Rothe(2024a) , Kaczmarek and Rothe(2024c) ] who, in particular, improved some of their complexity results (and also introduced another type of these problems where the game’s quota is changed proportionally with the number of players that is changed by adding or deleting them). In particular, control by adding players to a given WVG with the goal of either changing or maintaining a distinguished player’s Shapley–Shubik or probabilistic Penrose–Banzhaf index was recently shown to be even \mathrm{NP}^{\mathrm{PP}} -complete [ Kaczmarek and Rothe(2024a) , Kaczmarek and Rothe(2024c) ] , where \mathrm{NP}^{\mathrm{PP}} is the class of problems solvable by a nondeterministic Turing machine having access to a \mathrm{PP} oracle. \mathrm{NP}^{\mathrm{PP}} is an extraordinarily large complexity class; for example, the entire polynomial hierarchy is contained in it by Toda’s celebrated result [ Toda(1991) ] . So, while the complexity of control by adding players to WVGs with the goal of increasing, nonincreasing, decreasing, nondecreasing, or maintaining a given player’s power has been settled already for both the Shapley–Shubik and the probabilistic Penrose–Banzhaf index, the complexity of control by deleting players from such games (with the same goals) has remained open by now. Building on the proof technique of Kaczmarek and Rothe [ Kaczmarek and Rothe(2024a) , Kaczmarek and Rothe(2024c) ] , we establish optimal (i.e., \mathrm{NP}^{\mathrm{PP}} -completeness) results for some of these problems (specifically, for the goals of decreasing, nonincreasing, and maintaining a given player’s probabilistic Penrose–Banzhaf index). Note, however, that the constructions needed for the case of deleting players are way more involved than in the case of adding players. In order to motivate these problems, recall that WVGs are the default framework to model decision-making in legislative bodies such as the EU parliament, 2 2 2 A bit more precisely speaking, decision-making in the EU parliament can be described as a three-dimensional vector weighted voting game (see, e.g., the book by Chalkiadakis et al. [ Chalkiadakis et al.(2011)Chalkiadakis, Elkind, and Wooldridge ] and the book chapter by Bullinger et al. [ Bullinger et al.(2024)Bullinger, Elkind, and Rothe ] ). with population sizes roughly specifying the countries’ weights. Specifically, to motivate control by adding players, Kaczmarek and Rothe [ Kaczmarek and Rothe(2024a) , p. 1] write, ‘The EU is constantly expanding: New members join in (or, rarely, they leave), which is exactly control by adding players, raising the question of if and how the power of old EU members is changed by adding new ones to the EU—just one clear-cut case of motivation among various others. If new members join, an old one may insist on having the same power afterwards (motivating the goal of “maintaining one’s power”), or at least not lose power (“nondecreasing one’s power”), or Poland may insist that Germany’s power does not increase when