REVIEW 3 major objections 4 minor
Control by Deleting Players from Weighted Voting Games Is NP^PP-Complete for the Penrose-Banzhaf Power Index
T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read The paper proves that control-by-deleting problems in weighted voting games, measured by the Penrose-Banzhaf index, are complete for NP^PP, settling an open question and giving the optimal hardness bound.
desk verdict Likely correct NP^PP-completeness for the deletion variant of weighted voting game control; the proof needs a careful referee because the abstract alone cannot establish oracle tightness. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the PP oracle for Penrose-Banzhaf power evaluation. The Penrose-Banzhaf index of a player is the probability that the player is pivotal in a random coalition; for weighted voting games, deciding whether this probability exceeds a threshold is a counting problem that can be posed to a PP oracle. The NP part guesses a deletion set, and the oracle decides whether the post-deletion power satisfies the target relation. The completeness proof must encode a known NP^PP-complete problem into this guess-and-oracle pattern and show the reduction runs in polynomial time.
What would settle it
Exhibit a polynomial-time algorithm for deciding whether a weighted voting game has a deletion set of size at most k that pushes a given player's Penrose-Banzhaf index above a threshold (or below, for destructive control). Such an algorithm would place the problem in P, directly contradicting the NP^PP-completeness theorem unless NP^PP = P.
Extended reading notes
Core claim
The authors establish NP^PP-completeness for the constructive and destructive control-by-deleting problems in weighted voting games under the Penrose-Banzhaf index. That is, deciding whether deleting up to k players can make a given player's power exceed (or fall below) a target threshold—or keep it above a threshold—is exactly as hard as the class NP^PP. The proof combines an existential guess of the deletion set (the NP part) with a PP oracle that evaluates the probabilistic Banzhaf power comparison. This resolves the open case left by the corresponding control-by-adding results and, because NP^PP contains NP, the lower bound is optimal in the sense that no smaller deterministic or nondete
Load-bearing premise
The completeness proof depends on a polynomial-time reduction from some known NP^PP-complete problem to the deletion-control problem, with the PP oracle exactly matching the complexity of Penrose-Banzhaf evaluation; if that reduction is not tight, the NP^PP-completeness claim collapses.
Editorial extensions
If this is right
- The deletion-control problems are at least as hard as every problem in NP^PP, so they resist algorithms built purely on SAT solvers or integer programming for NP-hard cases.
- These are the first optimal completeness results for deletion control under the Penrose-Banzhaf index, improving on earlier hardness results for smaller classes.
- The result closes the deletion counterpart to the recently settled control-by-adding problems, giving a unified complexity picture for player control in weighted voting games.
- Because NP^PP contains PP, exact computation of Banzhaf power comparisons is embedded in the lower bound, so approximations or heuristics would be needed in practice.
- The lower bounds are optimal within the counting hierarchy, meaning no smaller complexity class can contain these problems unless the hierarchy collapses.
Reading between the lines
- The same guess-and-oracle schema may extend to control by deleting players under the Shapley-Shubik index, since its evaluation is also count-based; the paper does not address this.
- If the reduction is explicit and checkable, the NP^PP-completeness implies that even approximate power manipulation is hard, suggesting that real-world weighted voting bodies are computationally safe from deletion attacks.
- One testable extension is to quota-control combined with deletion; the paper's techniques might transfer, but that is not claimed.
- The result also suggests that auditing deletion attacks in electronic voting would require oracles of counting type, which are not available in practice, so oversight must rely on structural constraints.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the computational complexity of control by deleting players from weighted voting games, where the goal is to change or maintain a given player's power measured by the probabilistic Penrose-Banzhaf index. The abstract announces that some of these control problems are complete for NP^PP, the class of problems solvable by NP machines with a PP oracle, and that these results optimally improve previously known lower bounds from smaller complexity classes. The full text was not available for review; this report is based solely on the abstract.
Significance. If the completeness results are correct, they settle an open problem and provide an exact complexity classification for the control-by-deletion problems. The target class NP^PP is a natural and nontrivial benchmark: an NP guess of a deletion set paired with a PP oracle for evaluating the Banzhaf comparison is a plausible and interesting upper-bound mechanism. The stated improvement over lower bounds for smaller classes has practical relevance, as it indicates resistance to SAT-solving techniques. The paper also positions itself as building on recently settled control-by-adding-players results, which is a sensible and active research context. However, because the abstract alone does not provide the proof structure, the significance is contingent on the correctness and tightness of the reduction, which cannot be verified at this stage.
major comments (3)
- [Abstract] The membership direction of the NP^PP-completeness claim is not specified. The abstract does not state how the problem is shown to lie in NP^PP, in particular whether an NP machine guesses a deletion set and a single PP oracle call decides whether the player's power has changed. Since the Penrose-Banzhaf index is defined via a counting argument, the PP oracle's ability to decide the relevant comparison for weighted voting games is a load-bearing point. Without this detail, the upper bound cannot be verified.
- [Abstract] The hardness direction is unstated. The abstract names no NP^PP-complete source problem and gives no outline of the reduction. The tightness of the oracle interaction is the main proof burden; if the reduction requires more than one PP query or a non-standard oracle usage, the completeness argument may fail. This is not a detected error but a missing verification point, and it is essential to the central claim.
- [Abstract] The phrase 'some of these problems' is vague. The paper appears to consider several control problems (changing vs. maintaining a player's power, possibly with different thresholds), and the abstract does not identify which ones are NP^PP-complete and which are not. A precise enumeration of the statements is needed to assess the scope of the contribution.
minor comments (4)
- [Abstract] The abstract uses 'probabilistic Penrose-Banzhaf index' and 'Penrose-Banzhaf power index' without explaining whether these are synonymous. The terminology should be consistent.
- [Abstract] The 'recently settled' control-by-adding-players results are mentioned but not referenced or described. A citation or a short statement of the prior results would help position the paper.
- [Abstract] The claim of 'optimally improving currently known lower bounds' should be made concrete by naming the earlier lower-bound complexity classes and explaining how the new bounds improve them.
- [Abstract] If 'some' means a subset of the studied problems, the abstract should briefly state why the other variants are not complete (e.g., they may be easier, harder, or open).
Circularity Check
No circularity detected in the abstract-only claim; the NP^PP-completeness result is benchmarked against an external complexity class and no fitted inputs or self-citation load-bearing steps are visible.
full rationale
This is an abstract-only review, and no circular derivation chain is visible from the available text. The paper's central claim is that control-by-deleting problems for weighted voting games under the Penrose-Banzhaf index are complete for NP^PP. This is a statement about membership in, and hardness for, an external complexity class, not a quantity fitted to the data it then predicts. The abstract does not define the target problems in terms of the claimed conclusion, does not rename a known empirical pattern, and does not invoke a self-citation to justify the central premise. The skeptical concerns about unstated reduction details and oracle tightness are about proof burden and verification, not about circularity: a proof can be incomplete or underspecified without being circular. No equation or construction is available that would let me exhibit a reduction of the conclusion to an input. Under the hard rule that circularity requires quoting the paper and exhibiting the specific reduction, none can be identified. Therefore the appropriate finding is no significant circularity, score 0.
Assumptions & free parameters
assumptions (3)
- standard math Standard definitions of the complexity classes NP, PP, and the oracle class NP^PP, including polynomial-time reducibility.
- domain assumption Weighted voting game model and the probabilistic Penrose-Banzhaf power index.
- standard math Existence of a known NP^PP-complete (or harder) source problem used in the hardness reductions.
Cite this review
Pith. "Pith review of Control by Deleting Players from Weighted Voting Games Is NP^PP-Complete for the Penrose-Banzhaf Power Index." pith.science (2026). https://pith.science/paper/SZTG7346
@misc{pith2026250813868,
author = {Pith},
title = {Pith review of: Control by Deleting Players from Weighted Voting Games Is NP^PP-Complete for the Penrose-Banzhaf Power Index},
year = {2026},
howpublished = {\url{https://pith.science/paper/SZTG7346}},
note = {Machine review of arXiv:2508.13868}
}
read the original 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 -- the class of problems solvable by NP machines equipped with a 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.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.