| paper | d4-conf-atal-2008-0151 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; every valid instance has answer NO. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 12
statement extracted from the paper’s text layer
Given a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), positive rational weights \(a_t\), a target type \(t^\star\), and a quota fraction \(\rho\in(0,1)\), consider each admissible population size \(N\) with \(N\mu_t\in\mathbb{Z}\). Set the quota to \(\lceil \rho N\bar a\rceil\), where \(\bar a=\sum_{t\in T}\mu_ta_t\). Let \(\Phi_N\) be the total Shapley–Shubik index of the \(t^\star\) players; let \(\Phi_N^{\mathrm{split}}\) be that total when every such player splits into two identities of weight \(a_{t^\star}/2\). Decide whether \(\liminf_{N\to\infty,\;N\mu_t\in\mathbb{Z}\ \forall t}(\Phi_N^{\mathrm{split}}-\Phi_N)>0\).
A type is a complete weighted-voting player description with weight \(a_t\), and \(\mu_t\) is its population fraction. The decision applies uniformly to the target type: each target player either keeps weight \(a_{t^\star}\) or is replaced by two aliases of weight \(a_{t^\star}/2\). The objective is the asymptotic change in the target type’s aggregate Shapley–Shubik power across finite realizations of the distribution.
A positive-mass target type has Θ(N) members splitting together, while Theorem 12 studies one player deviating against fixed others; the proposed faction scenario motivates this shift, but the theorem itself does not establish the collective version.
fatal: False
Covers the equal two-identity split case of Theorem 12 through its population-limit analogue. It leaves the finite-population gain and loss bounds and the paper’s algorithmic results unmirrored.
The strongest mirror I can defend is a type-wide high-multiplicity version of the paper’s equal-split problem. A type is a complete player description; here, since this is a weighted voting game, it includes the player’s voting weight and false-name permissions. The mass \(\mu_t\) of a type is the fraction of the original electorate made up of players with that description.
The anchor is Theorem 12, proved in this paper by a reduction from Partition. In the paper’s Beneficial Split problem, an instance is a binary-encoded weighted voting game and a target player; the question is whether that player can divide their weight among false identities so that the sum of those identities’ Shapley–Shubik indices exceeds the player’s original index. Theorem 12 proves this problem NP-hard, even when the only permitted manipulation is an equal split into two identities. The reduction makes the target a dummy when the Partition instance is negative, and shows that an equal split increases its power when the Partition instance is positive.
Here is a continuous-population question anchored to that restricted version. Call it Mass-Beneficial Equal Split. An instance gives a finite support \(T\), rational masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\), a positive rational voting weight \(a_t\) for each type, a distinguished target type \(t^\star\), and a quota fraction \(\rho\in(0,1)\). For each admissible population size \(N\), make \(N\mu_t\) players of type \(t\), and set the quota to \(\lceil \rho N\bar a\rceil\), where \(\bar a=\sum_t\mu_ta_t\); a common denominator can scale the weights and quota to integers. Let \(\Phi_N\) be the sum of the Shapley–Shubik indices of the \(t^\star\) players. In the split game, every player of type \(t^\star\) becomes two identities, each of weight \(a_{t^\star}/2\), while all other players stay as they were; let \(\Phi_N^{\mathrm{split}}\) be the combined index of those aliases. The question is whether
\[
\liminf_{\substack{N\to\infty\\N\mu_t\in\mathbb{Z}\ \forall t}}
\bigl(\Phi_N^{\mathrm{split}}-\Phi_N\bigr)>0.
\]
Thus mass is a fraction of the original player population, the action transfers the target type’s mass into two alias types, and the objective is the target bloc’s total power. A “yes” means there is a persistent positive asymptotic gain, not merely a finite-population fluctuation.
This has a plausible regime: a large shareholder or membership body with many players in a modest number of weight classes, where members of a class share the relevant incentives and can coordinate an identity policy. The count of players \(N\) is large relative to the type support \(\tau=|T|\). The paper itself points to splitting a political party as an interpretation of false-name manipulation. Here the party or faction is the homogeneous target bloc. Its aliases’ combined voting weight is conserved, while its identity mass rises from \(\mu_{t^\star}\) to \(2\mu_{t^\star}\).
I expect Class A in the regular interior-quota regime: the many-player limit should replace exact subset-pivotality counting with an asymptotic calculation of which type supplies the pivotal identity. In the standard regular case, that limit is proportional to total voting weight by type, so the target bloc’s limiting power is \(\mu_{t^\star}a_{t^\star}/\bar a\). Equal splitting preserves that total type weight, predicting no persistent gain. The continuous question is to establish the limit and its conditions; if that prediction holds, the finite NP-hardness does not transfer to this mass-level problem. Further questions are whether the limit law has exceptions for particular supports or quota sequences, whether endpoint quotas preserve finite-population effects, and whether a tagged, vanishing-mass manipulator has a meaningful scaled-power limit.
The mirror covers only Theorem 12’s beneficial-split decision, through its equal two-identity restriction. It does not claim to mirror the paper’s tight finite-\(n\) gain and loss bounds or its approximation algorithm.
My weakest point is the change in strategic scale: Theorem 12 concerns one player choosing a split, while this mirror has a positive-mass type acting as a bloc. I think the authors could recognize it as their problem in a high-multiplicity faction regime because it preserves the weighted quota rule, the Shapley–Shubik objective, and the weight-conserving false-name action. But if they require the manipulator to remain a single individual, this is not that mirror; the individual’s population mass vanishes, and a separate tagged-player, first-order question would be needed.
Theorem 12 is a difficult anchor to mirror because its strategic unit is one player. That player chooses a weight split to increase their own Shapley–Shubik index. In the proposed mass version, every member of a positive-mass type splits, adding \(\Theta(N)\) identities, and the objective becomes the combined index of the whole bloc. This is a coordinated group manipulation, not the high-multiplicity version of one player’s decision.
The paper’s political-party example does not fully bridge that gap. In a weighted voting game, a party can itself be a single player whose weight represents its seats. Replacing that player with many member-players changes who participates in the coalition permutations. A large group of identical shareholders who jointly optimize its combined power is a more plausible scenario, but it requires a shared objective and coordinated action that the paper’s individual manipulation problem does not specify. It may be a worthwhile group-manipulation problem; it is a weaker claim that it mirrors Theorem 12.
The closest repair is to keep one tagged manipulator in a high-multiplicity population and ask about their split. But that player has vanishing mass. A mass-only model therefore loses the action; preserving it requires a tagged-player model and a chosen normalization or asymptotic influence measure. That is a coherent possible extension, but the computational question then concerns an individual’s influence against a continuum background, rather than a manipulation of the continuous society. The paper’s own reduction—from Partition through the pivotality of one specially constructed player—does not supply a reason to treat that extension as the programme’s central mass-transfer problem.
So the negative case is strongest on fidelity: the proposed positive-mass mirror changes a unilateral manipulation into collective manipulation, while the tagged-player repair keeps the original strategic unit only by retaining information outside the mass distribution. I cannot make that a decisive universal objection. A coordinated bloc with a shared power objective is plausible, and the authors might recognize it as their problem. The case against this anchor is therefore real but ultimately weak.
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.