| paper | d4-conf-aaai-2014-0282 |
| 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: for \(m=2\), exact classification uses \(O(\tau+m)\) integer arithmetic operations and \(O((\tau+m)L^2)=O(\tau L^2)\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), per-capita weights \(w_t\), two indivisible blocs of weights \(a,b>0\), and quota \(Q\), take finite approximants with \(N\mu_t\) background agents of type \(t\), each of weight \(w_t/N\), along values of \(N\) for which all counts are integral. Let \(W=\sum_{t\in T}\mu_t w_t\) and \(F_W(z)=\min\{1,\max\{0,z/W\}\}\). What is the sign of the limiting difference between the Shapley value of the second bloc when the first commits IN and when it commits OUT? The limit is \(\Delta=F_W(Q-a)-F_W(Q-a-b)-F_W(Q)+F_W(Q-b)\); classify it as positive, negative, or zero.
A mixed weighted voting game with a continuous background distribution \(\mu\) over voter types and two indivisible macroscopic blocs. Each background type has per-capita weight \(w_t/N\) in the finite approximants, keeping aggregate background weight \(W=\sum_t\mu_t w_t\) fixed. The quantity to classify is the sign of the limiting IN/OUT Shapley difference, computed from the four clipped values of \(F_W\).
The tested blocs remain exceptional atoms rather than members of the same high-multiplicity type distribution, so the mirror covers macro-bloc interactions rather than ordinary within-population pairs.
fatal: False
The mirror covers Theorem 2's weighted-voting pair-classification results. It leaves Theorem 1's realization result for arbitrary cooperative games and the empirical analyses untouched.
The best case I see is a continuous limit of the paper’s weighted-voting synergy test, in a regime with many small participants and a few large voting blocs. The anchor is Theorem 2, proved in the paper: in weighted voting games, deciding whether a given pair is synergistic is NP-hard, deciding whether it is antagonistic is NP-hard, and deciding whether it is indifferent is coNP-hard. The paper proves these claims with reductions from SUBSET-SUM-EQ; the Shapley-value hardness cited in the discussion is background, not the proof of this theorem.
My lead mirror is Atomless Weighted-Voting Pair-Synergy. Its instance is a finite set of background types \(T\), a rational mass distribution \(\mu\) over them, a per-capita voting weight \(w_t\) for each type, two designated bloc agents \(i,j\) with weights \(a,b>0\), and a rational quota \(Q\). The background has total weight \(W=\sum_{t\in T}\mu_t w_t>0\). A coalition wins when its weight, including any participating blocs, reaches \(Q\). The background is atomless: it can be viewed as the limit of \(N\) participants, with \(N\mu_t\) participants of type \(t\), each carrying weight \(w_t/N\). The blocs remain indivisible agents with weights \(a\) and \(b\).
As in the paper, the actions are IN or OUT commitments, and the question is the sign of the change in \(j\)’s Shapley value when \(i\) commits IN rather than OUT. Define \(F_W(z)=\min(1,\max(0,z/W))\). In the continuum limit, \(j\)’s Shapley value with \(i\) fixed IN is \(F_W(Q-a)-F_W(Q-a-b)\); with \(i\) fixed OUT it is \(F_W(Q)-F_W(Q-b)\). Thus the output is the sign of
\[
\Delta(i,j)=F_W(Q-a)-F_W(Q-a-b)-F_W(Q)+F_W(Q-b).
\]
A positive, negative, or zero answer means synergistic, antagonistic, or indifferent, respectively. This is an exact classification problem, not an optimization over an encoding. Its rational input permits a polynomial-time algorithm: compute \(W\), evaluate the four clipped rational values, and compare their difference with zero.
A plausible regime is a large mutual organization with many small account-holders in a few voting-weight classes, alongside two large institutional blockholders whose members act together. The number of small participants can be enormous while the number of background types \(\tau=|T|\) stays modest. Each small participant’s vote weight scales down as the population grows, while aggregate class weights stay fixed. The two tested blocs remain macroscopic because the question concerns their interaction with the rest of the organization. That scaling is a natural co-modification of the voting model for a continuum population.
The paper’s authors should recognize the mirror’s core question: it uses the same threshold game, the same IN/OUT commitments, and the same Shapley comparison. The continuous Shapley values are defined as limits of the finite-replica Shapley values, rather than by substituting a different influence measure. In the limit, the background weight preceding a bloc at random rank \(r\) is \(rW\). That concentration makes the sign computable from the quota and bloc weights. The expected classification is tractable; the finite-game hardness need not survive.
This mirror covers Theorem 2’s WVG pair-classification results, not Theorem 1’s realization theorem for arbitrary cooperative games or the empirical analysis. It suggests follow-up questions: how do exact finite-population corrections affect the sign; what happens with several designated blocs and higher-order synergy; and does hardness persist when the number of agents per background type grows but remains finite?
My weakest point is that the two tested agents remain atomic blocs while the rest of the population becomes continuous. A fully atomless population makes individual agents infinitesimal, and their pairwise Shapley interaction can disappear altogether. So this is a credible mirror for a mixed regime of large blocs and many small participants, not a claim that every cooperative game has a useful continuum synergy notion. The theorem’s subset-sum hardness may rely precisely on finite pivotal-coalition fluctuations that this limit removes; that is a substantive prediction of the mirror, and also its main limitation.
The serious anchor is Theorem 2: its three named computational results ask whether a pair is synergistic, antagonistic, or indifferent in a weighted voting game. There is no “no result to mirror” objection here. The paper supplies a precise decision problem, and the proposed clipped-rational calculation addresses all three outcomes.
The strongest objection is that pairwise Shapley synergy belongs to a game of distinct players. In a genuinely atomless population limit, a designated pair of ordinary members has vanishing individual weight, so its unscaled interaction can disappear. Rescaling that interaction or defining an interaction between whole types might recover a nontrivial object, but it changes the target from the paper’s relation between two agents to a local or group-level interaction.
The proposed mirror avoids that problem by retaining two macroscopic, named blocs while making only the background atomless. That is mathematically coherent, but it is a hybrid: the blocs’ weights stay fixed as each background member’s weight shrinks with population size. They are not ordinary members of the same fixed type distribution. Calling them coordinated institutions could make the scenario plausible, but it also makes the result about two exceptional players’ interaction with a continuum, rather than the high-multiplicity version of pair-synergy across the population. The mirror’s dependence only on aggregate background weight further narrows what it captures, though that alone is not a reason to reject it.
This is the best negative case I can make, and it does not defeat the mirror decisively. The hybrid scenario may be one the authors recognize, and its exact classification is a valid computational question even if its answer is simple. I cannot honestly support the universal claim that no worthwhile continuous mirror exists.
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.