| paper | d4-journals-jair-2014-0005 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Both theorems are computational hardness results, but the proposed models require \(N\mu_a\) to be integral and still compute power from finite-player orderings or subsets. Dropping the \(1/N\) atoms makes these fixed-size merges vanish and provides no canonical Shapley–Shubik or Banzhaf index; merging positive mass instead creates a distinguished bloc and changes the anchored operation. A large assembly with repeated weights is a plausible high-multiplicity regime, but the stated question remains a compressed finite roster rather than a continuous-population problem.
fails bit b-changes — the continuum limit changes the question
For fixed \(r\in\{2,3\}\), the merge changes only \(r/N\) of the society and vanishes as \(N\to\infty\); retaining the player-order and coalition-sampling indices keeps the model finite.
fatal: True
The proposed models cover beneficial merging for the Shapley–Shubik and probabilistic Banzhaf indices; they leave splitting, unbounded splitting, normalized Banzhaf, and extensions to other simple games unaddressed.
The strongest case I see is a high-multiplicity version of weighted-voting manipulation, with the population represented by masses of players grouped by voting weight. A natural setting is a large membership organization or shareholder assembly: many people hold one of a few recurring voting entitlements, and some want to combine accounts or split one account into false identities.
Let a type be a player’s voting weight \(a\), and let \(N\) be the number of players. The society is a distribution \(\mu\) with \(N\mu_a\in\mathbb Z_{\ge 0}\): there are \(n_a=N\mu_a\) players of weight \(a\), and \(\sum_a n_a=N\). The quota \(q\) is also part of the instance. In the intended regime, \(N\) may be very large compared with the number \(\tau\) of distinct weights. The scale \(N\) must remain explicit: the distribution \(\mu\) alone does not determine either power index, since two games with the same proportions but different numbers of players can have different indices.
For a merge of \(r\) players of weight \(a\), the operation removes mass \(r/N\) from type \(a\), replaces those players with one player of weight \(ra\), and changes the population size to \(N-r+1\). The question compares the merged player’s power with the sum of the original \(r\) players’ powers. This retains the identity-changing action the paper studies while expressing the rest of society by type masses.
My lead is Theorem 3.9, proved in this paper: deciding whether a coalition can beneficially merge for the Shapley–Shubik index is PP-complete, even when the coalition consists of just two equal-weight players. The paper notes that the PP upper bound was already observed by Faliszewski and Hemaspaandra [FH09]; the hardness result is proved here.
The corresponding mass-profile problem is: given \(N\), \(\mu\), \(q\), and a positive weight \(a\) with \(N\mu_a\ge 2\), let \(G\) be the weighted voting game with \(N\mu_w\) players of each weight \(w\). Decide whether merging two players of weight \(a\) increases their combined Shapley–Shubik power:
\[
\operatorname{SS}(G_{\&S},1)>2\operatorname{SS}(G,i),
\]
where \(S\) is any two such players and \(i\in S\). Here
\[
\operatorname{SS}(G,i)=
\sum_{C\subseteq P\setminus\{i\}}
\frac{|C|!(N-1-|C|)!}{N!}
\mathbf{1}\!\left[w(C)<q\le w(C)+w_i\right].
\]
The answer is yes exactly when the merged player’s index exceeds the two original indices’ sum. Theorem 3.9 makes this an especially direct anchor: the manipulation remains the paper’s own two-player merge, and the mass representation simply groups indistinguishable players.
A second anchor, also worth keeping, is Theorem 3.5, proved in this paper: Banzhaf-BENEFICIALMERGE is PP-complete even when only three equal-weight players merge. The paper says its PP-membership argument was already observed in Rey and Rothe [RR10, Theorem 3]; this paper proves the hardness.
Its mass-profile mirror takes \(N,\mu,q\), and a positive weight \(a\) with \(N\mu_a\ge 3\), and asks whether merging three players of weight \(a\) is beneficial for the probabilistic Banzhaf index:
\[
\operatorname{Bz}(G_{\&S},1)>3\operatorname{Bz}(G,i),
\qquad
\operatorname{Bz}(G,i)=
2^{-(N-1)}
\#\{C\subseteq P\setminus\{i\}:w(C)<q\le w(C)+w_i\}.
\]
Again, the merging coalition can be specified by its type and size because players of that type are interchangeable. This is a separate result about a different power index, rather than another formulation of the Shapley–Shubik question.
On an explicit finite profile, both mirrors inherit the paper’s PP-completeness results exactly. If \(N\) and the rational masses are instead given in binary as a compressed high-multiplicity input, the paper’s PP upper bounds do not automatically carry over: the number of players, and the Banzhaf denominator \(2^{N-1}\), can be exponentially large in the input length. The safe classification is therefore hardness transfers (Class B): ordinary finite instances embed directly as mass profiles, so the PP-hardness carries over. Whether compressed scale makes either problem harder still is a further question, not something these theorems establish.
The weakest point is also the main modeling choice. These are mass-distribution models with an identity quantum of \(1/N\), rather than atomless limits: removing that quantum would remove the finite players whose identities are merged, along with the stated power-index comparisons. I think that co-modification is plausible here because identities are central to the authors’ question. The other limitation is that the paper’s reductions use growing numbers of distinct weights. They establish hardness for the unrestricted mirror, but not for the particularly compelling regime \(N\gg\tau\) with a fixed or very small number of weight classes.
That leaves useful follow-up questions: does either mirror remain hard for bounded \(\tau\)? What is the right complexity bound when \(N\) is binary-encoded? And what happens if a positive fraction of a type class merges, rather than a fixed number of identity units? The last question may define a genuinely different, more asymptotic power-manipulation problem.
The strongest objection is not that the paper lacks a computational result: Theorems 3.5 and 3.9 give exactly such results. It is that both power indices measure the influence of individual players, while the proposed continuous input describes type masses.
For Shapley–Shubik, the random experiment orders the \(N\) players; for probabilistic Banzhaf, it samples subsets of those \(N\) players. Thus a mass profile \(\mu\) alone cannot specify either index. The proponent supplies \(N\) and requires \(N\mu_a\) to be integral, which makes the mirror well-defined—but it is then a compressed finite roster, not yet a continuous population model. If the masses become genuinely divisible, there is no longer a canonical finite-player order or subset experiment. Choosing a continuum extension would add modeling choices about how orders or coalitions are sampled.
That problem is especially sharp for the anchors as stated. Merging two or three players changes only \(O(1/N)\) of the population. In an atomless limit, those players have zero mass, so the operation disappears from the society. Under ordinary regular scaling, their individual power also vanishes; the strict comparison can depend on finite-size details that the limiting mass profile forgets. This is a genuine degeneracy, not an objection that the continuous answer might differ. It applies to Theorem 3.9’s two-player Shapley–Shubik merge and Theorem 3.5’s three-player Banzhaf merge alike.
The best rescue is to merge a positive fraction of a type into one bloc. That avoids a vanishing manipulation and preserves a nonzero strategic effect. But after merging, the bloc is one player with weight proportional to \(N\), not a positive mass of ordinary players. The limit must retain that distinguished, macroscopic player alongside the continuous background. It becomes a hybrid large-player power-index problem, with an explicit identity and a diverging weight. That may be worth studying, but it does not show that the paper’s manipulation question has been absorbed into a continuous society model.
This case still does not establish the requested universal negative. A large assembly with many members in a few weight classes is a plausible high-multiplicity regime, and the paper’s operation remains recognizable there. The programme’s own standard treats high-multiplicity work as support, not collision. So the argument substantially weakens the proposed mass-only mirrors and explains why their continuum limits may lose the manipulation, but I cannot honestly rule out a worthwhile mirror in every scenario.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.