| paper | d4-conf-atal-2009-0006 |
| 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 (\(\mathrm{P}\)); merging is beneficial exactly when \(q<1-A_S+A_S^2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 6.4
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), positive rational per-capita weights \(a_t\) normalized by \(\sum_{t\in T}\mu_ta_t=1\), a quota fraction \(q\in(1/2,1)\), and a cohort \(S\subset T\) with \(0<A_S<1\), where \(A_S=\sum_{t\in S}\mu_ta_t\), consider replication games with \(N\mu_t\) voters of type \(t\), each of weight \(a_t/N\). Determine whether, in the limit along replication sizes with integral \(N\mu_t\), the Shapley–Shubik index of the bloc formed by merging every voter in \(S\) exceeds the pre-merge sum of Shapley–Shubik indices of those voters. The pre-merge limit is \(\alpha_S=\sum_{t\in S}\mu_t\); the post-merge limit is \(\bigl(\min(q,1-A_S)-\max(0,q-A_S)\bigr)/(1-A_S)\).
Types are voting-weight and eligibility classes with masses \(\mu_t\); each type-\(t\) voter has weight \(a_t/N\) in a finite replication. The decision merges all voters of types in \(S\) into one bloc of weight \(A_S\), then compares that bloc's limiting Shapley–Shubik index with the cohort's pre-merge total index \(\alpha_S\).
The proponent's pre-merge formula uses voting-weight share where the limiting Shapley–Shubik power is the cohort's population share when all per-capita weights are positive.
fatal: False
Covers Proposition 6.4 for merging an entire positive-mass cohort; it leaves the paper's Banzhaf results and its splitting and annexation results aside.
The strongest mirror I believe in is the paper’s Shapley–Shubik merging result, extended from a small coalition to a large homogeneous cohort. That extension keeps the paper’s central question intact: does a group gain Shapley–Shubik power by becoming one bloc?
The anchor is Proposition 6.4, proved in this paper by reduction from PARTITION. It says BENEFICIAL-SS-MERGE is NP-hard: given a weighted voting game \(v=[q;w_1,\ldots,w_n]\) and a coalition \(S\), replace the members of \(S\) with one player whose weight is their combined weight. Decide whether that bloc’s Shapley–Shubik index in the new game exceeds the sum of the original Shapley–Shubik indices of the members of \(S\).
Consider a member-owned organization with many voters but only a few voting-weight classes. A type \(t\) is a complete class: its members have the same voting weight and the same eligibility to join a bloc. Its mass \(\mu_t\) is its fraction of the population, with \(\sum_t\mu_t=1\). Write \(a_t\) for the type’s per-capita weight, normalized so \(\sum_t\mu_ta_t=1\), and let \(q\in(1/2,1)\) be the quota as a fraction of total weight. A natural high-multiplicity regime has \(N\) very large and support size \(\tau\) much smaller than \(N\): for example, many members distributed across a handful of membership classes, with a class or alliance able to coordinate through one representative.
My proposed problem is Continuous Cohort Shapley Merge. Its input is \((T,\mu,a,q,S)\), where \(T\) is the finite type support, \(\mu_t\) and \(a_t\) are binary rationals, and \(S\subseteq T\) is the cohort coalition to be tested. For each suitable replication size \(N\), form a finite game with \(N\mu_t\) members of type \(t\), each of weight \(a_t/N\). Compare the sum of the members’ Shapley–Shubik indices before the merge with the merged bloc’s index after every member in \(S\) becomes one player. The continuous problem asks whether the limiting post-merge index is strictly greater than the limiting pre-merge sum; its solution is the exact YES or NO answer.
Let \(A_S=\sum_{t\in S}\mu_ta_t\), the cohort’s fraction of total voting weight. In the large-population limit, the pre-merge cohort’s Shapley–Shubik power is \(A_S\): the pivotal infinitesimal voter at the quota crossing is selected in proportion to voting weight. After the merge, the bloc has macroscopic weight \(A_S\), while the other voters remain infinitesimal. Its limiting index is
\[ \frac{\min(q,1-A_S)-\max(0,q-A_S)}{1-A_S}, \]
for \(0<A_S<1\). This is the fraction of the bloc’s possible positions in a random ordering for which the preceding weight is below quota and the bloc takes the total to quota or beyond. Thus the decision reduces to comparing this rational expression with \(A_S\), in time polynomial in \(\tau\) and the input bit length. I expect this mirror to be tractable: it gives a closed-form limit for the paper’s hardness anchor. That is a substantive answer to whether discrete merge hardness survives this high-multiplicity regime.
I think the authors would recognize the question: their problem already asks whether a coalition gains by replacing its members with one bloc, and this preserves that comparison while making the coalition a positive-mass cohort. The paper’s stated examples include coalition formation and joint-stock voting, where repeated classes of holders make the regime plausible. This mirror covers Proposition 6.4; it does not claim to continue the paper’s Banzhaf split, merge, or annexation results.
My weakest point is the scale of the action. The paper proves hardness when the coalition being merged can be small; this mirror merges an entire type cohort, which becomes a macroscopic player. That can change Shapley power sharply, so a referee could regard it as a broader cohort-merger problem rather than the direct limit of the paper’s individual-player instances. I think it remains a credible mirror because the underlying operation and payoff comparison are unchanged, but that scale change is the part the positive case has to defend.
Proposition 6.4 is a numbered NP-hardness result, so the “no computational result to mirror” objection does not apply. The strongest challenge is that the proposed limit is wrong for heterogeneous voting weights. Before the merge, the Shapley–Shubik index is the probability a voter is pivotal in a random ordering. With many infinitesimal positive-weight voters, the pivotal voter’s type is sampled by population frequency, not by voting-weight share. If \(\alpha_S=\sum_{t\in S}\mu_t\) and \(A_S=\sum_{t\in S}\mu_ta_t\), the pre-merge cohort’s limiting index is \(\alpha_S\), assuming all types have positive weight—not \(A_S\). The proposed post-merge expression can still be right, so the corrected comparison is between \(\alpha_S\) and
\[
\frac{\min(q,1-A_S)-\max(0,q-A_S)}{1-A_S}.
\]
With zero-weight types, the pre-merge quantity must be adjusted to count only positive-weight voters.
There is also a scale problem. If \(S\) remains a fixed finite coalition as the population grows, its pre-merge power and the merged player’s power both vanish; the limiting strict comparison loses the signal. The proponent avoids that degeneration by merging a positive-mass cohort. That is a coherent model, but it changes the operation from merging a small set of named players to turning a macroscopic share of the electorate into one player. The resulting bloc has finite voting weight despite having vanishing population mass, so it is a special atom in an otherwise atomless society.
That distinction weakens the claim that this is a direct high-multiplicity mirror of Proposition 6.4. Still, it does not defeat the repaired version: the paper studies coalitions merging into blocs, and a large cohort with common weight and eligibility is a plausible coalition. Its mass-level merger is a computational question the authors could recognize. I can make a strong case against the formula as stated and against treating the finite-coalition limit as informative, but I cannot honestly rule out the positive-mass cohort mirror. Under the programme’s stated gate, this anchor survives in corrected form, so the universal negative case is 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.