| paper | False-Name Manipulations in Weighted Voting Games |
| authors | H. Aziz, Yoram Bachrach, Edith Elkind, M. Paterson |
| venue | JAIR 2011 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: In $\mathrm{P}$. A beneficial split exists exactly when $w_{t^\star}>0$ and $2q\ne\sum_t\mu_tw_t$. The decision takes $O((\tau+m)L^2)$ bit operations, with $m=2$. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational weights \(w_t\), a quota rate \(q\), and a designated type \(t^\star\) with \(\mu_{t^\star}>0\), decide whether there exist rational \(0<\alpha\le\mu_{t^\star}\) and \(u,v>0\) with \(u+v=w_{t^\star}\) such that replacing mass \(\alpha\) of \(t^\star\) by mass \(\alpha\) of each of two labelled identity types of weights \(u\) and \(v\) makes their limiting total normalized Banzhaf power exceed \((\alpha/\mu_{t^\star})\) times the original limiting Banzhaf power of type \(t^\star\). The limit is taken over denominator-compatible \(N\)-player games with \(N\mu_t\) copies and quota \(Nq\), with the post-split finite measure of total mass \(1+\alpha\) normalized together with its quota.
A high-multiplicity weighted voting game with type masses \(\mu\), per-block weights \(w_t\), and quota \(Nq\); the decision variables are the controlled mass \(\alpha\) and split weights \(u,v\), and the objective compares the aggregate limiting Banzhaf power of the two new identity types with the original power of the split subcohort.
The strongest objection is that a positive-mass cohort must coordinate the split, whereas the theorems give that decision to one named player, and the paper does not establish such collective control in its general model.
fatal: False
The mirror covers Theorems 11 and 12 through continuous beneficial splitting, while leaving the bounds, merging, annexation, unanimity-game results, and experiments untreated.
The strongest honest positive case is a high-multiplicity false-name problem. The continuum should not assign a nonzero Shapley–Shubik or Banzhaf index to an individual infinitesimal agent; instead, it should assign the index to a positive-mass class of interchangeable identities.
Consider a large federation of \(N\) institutional voting blocks—municipalities, union locals, shareholder blocs, or political caucuses. Each block has a voting weight from a small menu of weights, so a type is its weight together with the label needed to identify a controlled bloc. Let \(\mu_t\) be the fraction of blocks of type \(t\), with \(N\gg\tau\), where \(\tau\) is the number of distinct types. The quota is \(Nq\).
For rational \(\mu\), form \(G_N(\mu,q)\) with \(N\mu_t\) players of type \(t\), each having weight \(w_t\). Define the continuum Banzhaf power of type \(t\) as the high-multiplicity limit of the total normalized Banzhaf power of all its copies:
\[
\mathsf{B}_\infty(t;\mu,q)
=
\lim_{N\to\infty}
\frac{\sum_{i\text{ of type }t}\eta_i(G_N)}
{\sum_j\eta_j(G_N)}.
\]
Define \(\mathsf{S}_\infty(t;\mu,q)\) analogously as the limit of the total Shapley–Shubik power of the copies of \(t\). These are not newly invented power measures: they are precisely the paper’s indices aggregated over a high-multiplicity type class. The instance can restrict attention to rational inputs for which the canonical denominator-clearing limits exist.
The lead anchor is Theorem 11, proved in this paper. It states: “Beneficial-BI-Split is NP-hard, and remains NP-hard even if the player can only split into two players with equal weights.” The underlying problem is: given \(G=[q;w_1,\ldots,w_n]\) and a player \(\ell\), decide whether \(\ell\) can replace weight \(w_\ell\) by weights \(w_{\ell_1},\ldots,w_{\ell_m}\) summing to \(w_\ell\) so that
\[
\sum_j\beta_{\ell_j}(G')>\beta_\ell(G).
\]
The theorem is proved here by reduction from Partition; in fact, the reduction remains hard when there are exactly two new identities with equal weights. The paper does not claim NP-completeness, since even verifying a proposed split may involve hard power-index computations.
My continuous problem is Continuous High-Multiplicity Beneficial Banzhaf Split. An instance consists of rational type masses \(\mu\), rational weights \(w_t\), a quota rate \(q\), a designated type \(t^\star\) with \(\mu_{t^\star}>0\), and the requirement that the split use exactly two new identities. A solution chooses a rational mass \(0<\alpha\le\mu_{t^\star}\) and rational \(u,v>0\) with \(u+v=w_{t^\star}\). Replace mass \(\alpha\) of type \(t^\star\) by mass \(\alpha\) of a fresh identity type of weight \(u\) and mass \(\alpha\) of a fresh identity type of weight \(v\). The quota remains \(Nq\), because the total voting weight of every split block is preserved. The split is successful if
\[
\mathsf{B}_\infty(t_u;\lambda,q)
+
\mathsf{B}_\infty(t_v;\lambda,q)
>
\frac{\alpha}{\mu_{t^\star}}
\mathsf{B}_\infty(t^\star;\mu,q),
\]
where \(\lambda\) is the post-split mass measure. The right-hand side is the original Banzhaf power of the selected \(\alpha\)-mass subcohort; symmetry makes it proportional to the power of the entire \(t^\star\)-class. The equal-split restriction \(u=v=w_{t^\star}/2\) gives the direct continuous counterpart of the restricted case in Theorem 11. A solution is the witness \((\alpha,u,v)\).
This is a genuine population continuization. The action is a mass transfer between identity types, the objective is the same total power that the paper assigns to false identities, and the weighted threshold rule remains discrete. What changes is that many interchangeable voting blocks can make the same split. I would expect the bounded-\(\tau\), regular high-multiplicity version to be Class A: the Partition obstruction in the proof is driven by one distinct player per item and an exact subset sum, whereas repeated weight classes should permit fixed-dimensional generating-function or local-limit calculations. The unrestricted-\(\tau\) version may retain hardness, so the natural boundary question is whether the result is polynomial in \(\tau\), rather than merely tractable for fixed \(\tau\).
The second anchor is Theorem 12, also proved in this paper. It states: “Beneficial-SS-Split is NP-hard, and remains NP-hard even if the player can only split into two players with equal weights.” Here the underlying question is identical except that the payoff comparison uses Shapley–Shubik power:
\[
\sum_j\phi_{\ell_j}(G')>\phi_\ell(G).
\]
The corresponding problem is Continuous High-Multiplicity Beneficial Shapley–Shubik Split. It has exactly the same instance, action, and post-split mass measure as above, but asks whether
\[
\mathsf{S}_\infty(t_u;\lambda,q)
+
\mathsf{S}_\infty(t_v;\lambda,q)
>
\frac{\alpha}{\mu_{t^\star}}
\mathsf{S}_\infty(t^\star;\mu,q).
\]
This is not merely the same problem under different notation: the continuum functional comes from random arrival orders rather than uniformly random coalitions, so its asymptotic analysis is separate. I would again expect a Class A result for fixed \(\tau\), with a different and probably more delicate limit calculation. Further questions include whether the Banzhaf and Shapley–Shubik continuum problems have the same complexity, how fast finite-\(N\) values converge, and whether a vanishing \(1/N\)-mass unilateral manipulation has a meaningful first-order limit.
These mirrors cover only Theorems 11 and 12 and do not claim to continuize the paper’s bounds, merging results, annexation results, or experiments. That is deliberate: the two hardness theorems already give a focused question about whether a discrete manipulation barrier survives population continuization.
The weakest point is that the paper studies one named player splitting, while the proposed continuum model studies a positive-mass cohort of identical players splitting together. A literal single infinitesimal player has zero aggregate power in the limit, so preserving the paper’s payoff comparison forces this co-modification. I think it is defensible in the paper’s own political interpretation—many standardized institutional blocs can coordinate a registration split—but it is the point most vulnerable to objection. If a referee insists on unilateral manipulation by one named individual only, this positive case becomes substantially weaker; if high multiplicity is accepted as the regime, the cohort formulation is the natural continuous analogue rather than a change of objective.
The negative case is that both anchors fail for the same fundamental reason: false-name manipulation is inherently a manipulation by one named player, whereas a genuine high-multiplicity limit makes every named player negligible.
For a game with \(N\) players drawn from finitely many bounded-weight types, an individual’s normalized Banzhaf or Shapley–Shubik power is typically \(O(1/N)\) (or zero). Splitting that one player into two identities therefore changes neither the limiting society nor the limiting payoff in any nonzero way. The paper’s comparison
\[
\sum_j \beta_{\ell_j}(G')>\beta_\ell(G)
\]
collapses to \(0>0\) in the continuum. The same holds for the Shapley–Shubik comparison. This is not a claim that the continuous answer is easy; it is a degeneration of the paper’s objective itself.
The proponent avoids that degeneration by letting a positive mass \(\alpha N\) of identical players split simultaneously. But this is no longer Theorem 11 or Theorem 12. Those theorems concern one player choosing a split, with the other players remaining unchanged. A mass of players coordinating the same split is a new collective manipulation problem. The paper does not study whether a positive fraction of a population can jointly create new identities, nor does it give that cohort a common payoff or decision right.
Calling the cohort a “selected subcohort” does not repair this. In a high-multiplicity model, members of a type are indistinguishable. Either the cohort is anonymous and its coordinated action is an additional coalition-formation assumption, or it is marked as controlled by one party, in which case that control label is part of the type and the model is no longer the paper’s anonymous false-name setting. A single controlled player can be represented, but then it has zero mass and zero limiting power.
There is also a genuine normalization problem. Replacing mass \(\alpha\) by mass \(\alpha\) of each of two new identity types increases the total identity mass from \(1\) to \(1+\alpha\). If the quota is kept at \(Nq\), the model uses an absolute quota; if the population is renormalized back to one, the quota rate changes as well. Either convention can be made coherent, but each is an additional population-level modelling choice. The resulting operation is not merely “the paper’s split with fractional players”; it changes the size and composition of the voting body.
In ordinary regular high-multiplicity regimes, the asymptotics further weaken the proposed mirror. Banzhaf power is determined by the probability that a random coalition lies in a narrow pivotal interval, while Shapley–Shubik power is determined by the analogous pivotal event in a random ordering. With bounded weights and many repeated copies, these events become aggregate limit phenomena. In common majority-type regimes, the total power of a type is governed essentially by its mass and aggregate voting weight. Splitting a positive cohort while preserving its total weight then has no leading-order “false-name” effect; any remaining effect comes from changing the population’s type distribution or total number of identities. That is a mean-field voting-composition question, not the manipulation studied in the paper.
The Partition reductions in Theorems 11 and 12 reinforce the mismatch. They use one distinct player for each item \(a_i\), with pivotality arising from an exact subset of those individually represented weights summing to \(4X\). Repeating each item into a high-multiplicity type turns that witness into a bulk coefficient or local-limit calculation. This may be an interesting new asymptotic problem, but it is not a continuous version of the named-player split problem. Conversely, retaining one type per item with multiplicity growing merely pads the original finite instance; it does not produce a meaningful fixed-type population limit.
One could rescue the proposal by studying first-order effects of a single split, retaining \(1/N\)-scale corrections, or by explicitly defining a coordinated positive-mass coalition. The former is a finite-size sensitivity analysis, not the limiting power-index problem. The latter is a new collective manipulation model whose computational value would have to be justified independently. Neither is forced by the paper.
So the strongest negative conclusion is not that weighted voting has no sensible high-multiplicity theory. It plainly does. The point is narrower: neither Theorem 11 nor Theorem 12 yields a worthwhile continuous mirror of the paper’s false-name manipulation. The only nondegenerate version changes the manipulator from one identity into a macroscopic coalition, and that changes the problem’s agent, objective, and operation simultaneously.
This negative case is not airtight in the absolute sense. A researcher could reasonably decide that coordinated splitting by a positive-mass class of institutional blocs is itself worth studying. But that would be a new mean-field coalition-manipulation programme, not a faithful continuization of either theorem.
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.