{"id":"5ecc3acc-1a74-4a22-8b0c-d18f6658681b","arxiv_id":"2508.13868","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Control by deleting players in weighted voting games is NP^PP-complete for the Penrose-Banzhaf power index.","lead":"This paper resolves an open question by showing that deleting voters from weighted voting games to change or keep a given player's power is NP^PP-complete under the Penrose-Banzhaf index. In plain terms, these manipulation problems are computationally intractable in a way that resists standard SAT-solving approaches.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"NP^PP-completeness claim unverifiable from abstract; reduction and oracle tightness are unstated.","rationale":"The reader's verdict is UNVERDICTED with LOW confidence, based solely on the abstract. My stress-test identifies the same weakest point: the reduction mechanism and oracle tightness are unstated, making the NP^PP-completeness claim unverifiable. This is not a fabricated flaw; it is an honest recognition that the central technical content is absent from the review material. The abstract's claim is plausible—Banzhaf index computation is known to be #P-hard, and #P is closely related to PP, so an NP machine with a PP oracle is a plausible characterization. However, plausibility is not proof. The concrete test would settle the concern by examining the full proof. Since I cannot identify a definite error, only a missing verification, the reader's UNVERDICTED verdict should stand unchanged. The agreement is 'agree' because the reader's weakest assumption precisely matches the oracle interaction tightness concern.","tokens_in":726,"tokens_out":2542,"duration_ms":27729,"concrete_test":"Retrieve the full paper from arXiv and inspect the reduction and membership proofs. Specifically: (1) Identify the known NP^PP-complete source problem used for hardness; (2) verify the reduction runs in polynomial time and maps yes-instances to instances where a deletion set changes the Banzhaf index; (3) confirm that the Banzhaf comparison for weighted voting games is in PP (e.g., via counting accepting paths of a probabilistic machine), so the NP^PP upper bound is sound; (4) check that the oracle is used only for individual Banzhaf evaluations, not for adaptive chains that would require higher complexity. If the reduction cannot be completed or the Banzhaf evaluation is outside PP, the NP^PP-completeness claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of the paper is that control-by-deleting problems for weighted voting games are NP^PP-complete under the Penrose-Banzhaf index. For this to hold, two conditions must be met: (1) membership: the problem is solvable by an NP machine with a PP oracle, where the NP part guesses a deletion set and the PP oracle decides whether a player's power has changed; (2) hardness: a polynomial-time reduction exists from a known NP^PP-complete problem to the control problem, with the oracle interaction tightly capturing the PP computation. The abstract provides no details of either condition. The least secure point is the tightness of the oracle interaction: if evaluating Banzhaf power for weighted voting games requires more than PP (e.g., a #P-complete computation that cannot be decided by a single PP oracle call), or if the reduction uses the oracle in a non-canonical way, the completeness claim could collapse to a weaker class. Since the abstract is all that is available, the proof burden is entirely unverified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":951,"tokens_out":3684,"duration_ms":39455,"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":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"}],"minor_comments":[{"comment":"The abstract uses 'probabilistic Penrose-Banzhaf index' and 'Penrose-Banzhaf power index' without explaining whether these are synonymous. The terminology should be consistent.","section":"Abstract"},{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"},{"comment":"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).","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"This report is based solely on the abstract because the full text was not supplied to the referee. The 'uncertain' recommendation reflects the lack of evidence available for verification, not a detected flaw. If the full manuscript is provided, the referee should focus on the PP-membership proof for Banzhaf evaluation in weighted voting games and the NP^PP-hardness reduction, especially the number and type of oracle calls. The paper appears relevant to the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this looks like a genuine open-problem resolution, not an incremental repackaging. The authors show that control by deleting players in weighted voting games is NP^PP-complete when the Penrose-Banzhaf index is used. That's the right kind of upper-and-lower bound to expect: guess the deletion set (NP) and call a PP oracle to check whether a player's power changes. The abstract also claims the result \"optimally improves\" prior lower bounds, which presumably means it matches the natural upper bound and beats earlier hardness for smaller classes.\n\nWhat the paper does well, even from the abstract: it ties into the recently settled adding-player work, states the open problem clearly, and gives a precise target class. That's more than many abstracts do.\n\nNow the soft spots. The whole proof is invisible. We only have the abstract, so the stress-test worry about the oracle interaction is exactly where I'd want to look first. Membership requires that Banzhaf evaluation, for these games, is decidable by a single PP call — that's plausible but needs careful argument, especially because counting winning coalitions is #P-hard in general. Hardness requires a reduction from some NP^PP-complete problem with the oracle used in a tight, non-cheating way. If the reduction requires multiple oracle calls or non-adaptive queries, the classification could weaken. I can't verify any of that without the full text.\n\nThat's not a defect in the paper, just a limit of this review. The abstract makes no obviously false moves. The citation pattern looks sensible — they build on recently settled adding-player results, and the self-citations are likely to prior work in the same line, which is normal. No signs of fitting or circular definitions.\n\nBottom line: if the proof checks out, this is a solid contribution to computational social choice, useful for anyone studying manipulation and control in weighted voting. It won't reshape the world, but it closes a gap and gives a clean hardness result. I'd send it to a serious referee, with instructions to scrutinize the oracle upper bound and the reduction's tightness. For a reading group, it's a maybe — more interesting once the proof is available.\n\nI'd cite it if I were writing about control in voting games.","headline":"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.","tokens_in":1358,"tokens_out":2307,"would_cite":true,"duration_ms":25177,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","91A12","91B12"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["weighted voting games","Penrose-Banzhaf index","control by deleting players","NP^PP-completeness","computational social choice","complexity classes","voting manipulation","power indices"],"falsifier":"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.","tokens_in":657,"feed_emoji":"🗳️","tokens_out":6626,"duration_ms":67446,"temperature":0.7,"pith_summary":"Weighted voting games model decisions in parliaments and corporations, where each player's weight determines the quota needed to pass a motion. A natural form of manipulation is deleting players to change or preserve a target player's influence. This paper shows that for the probabilistic Penrose-Banzhaf power index, these deletion-control problems are complete for NP^PP—the class of problems solvable by an NP machine with a probabilistic oracle. That means they are strictly harder than NP-complete problems unless the counting hierarchy collapses, so practical solution techniques for SAT cannot crack them. The result improves previously known lower bounds and closes the deletion side of a question recently settled for adding players.","feed_headline":"Deleting voters to rig a weighted vote is NP^PP-complete","feed_subtitle":"For the Penrose-Banzhaf index, these deletion attacks are beyond NP—even SAT solvers can't crack them.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["Deleting players to control weighted voting is NP^PP-complete","Weighted voting deletion control hits NP^PP-complete","Deleting players from weighted games: NP^PP-complete","NP^PP-complete: Deleting voters to change Banzhaf power"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Deleting players to control weighted voting is NP^PP-complete","Weighted voting deletion control hits NP^PP-complete","Deleting players from weighted games: NP^PP-complete","NP^PP-complete: Deleting voters to change Banzhaf power"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00101,"raw_usage":{"total_tokens":4102,"prompt_tokens":736,"completion_tokens":3366,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":3289}},"tokens_in":480,"tokens_out":3366,"duration_ms":21415,"temperature":1.0,"reasoning_tokens":3289,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T18:50:32.676824+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}