| paper | d4-conf-atal-2014-0420 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even with equal type masses and all per-unit vote weights equal to \(1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite supported type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), per-unit vote weights \(a_t>0\), a quota \(Q\), a compatibility graph \(H\) on \(T\), and a target type \(t^\star\), decide whether there are masses \(x_t\in[0,\mu_t]\) for \(t\ne t^\star\) and \(\delta\in(0,\mu_{t^\star}]\) such that the types with \(x_t>0\) form a clique in \(H\), each is compatible with \(t^\star\), and \(\sum_{t\ne t^\star}a_tx_t<Q\le\sum_{t\ne t^\star}a_tx_t+a_{t^\star}\delta\).
A society is a rational distribution \(\mu\) over types that share vote weights and compatibility relations. A feasible coalition selects mass \(x_t\) from each type, with positive-mass support forming a clique; the question is whether adding some positive mass \(\delta\) of a designated target type can turn a losing coalition into a winning one.
The mirror asks whether a cohort can swing the outcome, rather than whether an individual has positive Banzhaf power; this changes the unit whose power is measured, even though it preserves the existence-of-a-swing question.
fatal: False
Covers Theorem 2’s pivotality-existence decision question. It leaves the numerical Banzhaf and Shapley–Shubik indices, their algorithms and approximation results, and the simulation findings without a continuous mirror.
The strongest honest mirror is the paper’s Theorem 2, proved in the paper by a reduction from Clique. It states: for every \(M\ge 1\), RawBz(\(M\)) is NP-complete. Its input is a Compatibility Weighted Voting Game with maximum agent weight at most \(M\); it asks whether the raw Banzhaf index of agent \(n\) is positive. Since \(\eta_n>0\) exactly when there is a feasible coalition in which \(n\) is critical, this is a hardness result about whether an agent can ever swing the outcome. The paper’s reduction gives every agent weight \(1\), makes the target compatible with everyone, and makes the other agents’ compatibility graph the input graph. The target is critical in some feasible coalition exactly when that graph has a clique of the required size.
A plausible high-multiplicity setting is a large assembly of delegates grouped into recurring caucus types. Members of a type have the same voting weight and the same compatibility relations to every other type; members of a type are mutually compatible. There may be \(N=K\tau\) delegates across \(\tau\) types, with \(K\) large. Pairwise compatibility between types can be nontransitive, as in the paper’s motivating examples. The continuous society records each type’s population fraction \(\mu_t\), rather than the number of named delegates in it.
Here is the continuous decision problem I would hand to a prover: Mass-Pivotality for Compatibility Weighted Voting Games. An instance consists of a finite supported type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), rational vote weights per unit mass \(a_t>0\), a rational quota \(Q\), a compatibility graph \(H\) on the types, and a target type \(t^\star\). A coalition is a vector of selected masses \(x_t\in[0,\mu_t]\); it is feasible when its positive-mass support is a clique in \(H\), and wins when \(\sum_t a_tx_t\ge Q\).
The question is whether there are selected masses \(x_t\) for types other than \(t^\star\), and an amount \(\delta\in(0,\mu_{t^\star}]\), such that the other types form a feasible coalition, are compatible with \(t^\star\), and
\[ \sum_{t\ne t^\star} a_tx_t \;<\; Q \;\le\; \sum_{t\ne t^\star} a_tx_t+a_{t^\star}\delta. \]
A yes-instance has the selected coalition and \(\delta\) as its solution: adding that much target-type mass turns a losing coalition into a winning one. This is a type-level, mass-based version of the raw Banzhaf positivity question.
The Clique reduction adapts directly. Given \(G=(V,E)\) and \(k\), make one type for each vertex and a universal target type \(z\). Give every type mass \(1/(|V|+1)\) and vote weight per unit mass \(1\). Put the edges of \(G\) among the vertex types, connect \(z\) to all of them, and set \(Q=(k+1)/(|V|+1)\). A \(k\)-clique supplies a losing coalition of mass \(k/(|V|+1)\); adding all of \(z\)’s mass makes it win. Conversely, if some amount of \(z\)’s mass makes a coalition win, the supporting vertex types must form a clique with total mass at least \(k/(|V|+1)\), so there must be at least \(k\) of them. Thus this continuous problem is NP-hard in \(\tau\), and it is in NP: a clique support and rational mass witness can be checked in polynomial time. Its expected classification is hardness transfers (Class B). The combinatorics survive in the compatibility graph over types; they are not driven by how many delegates were replicated inside each type.
This covers Theorem 2’s positivity question, not the numerical Banzhaf index, the Shapley–Shubik index, or the paper’s simulation results. Natural follow-ups are whether fixed-dimensional spectral compatibility makes Mass-Pivotality tractable in \(\tau\) and the input bit length, and whether a quantitative type-level power measure can be defined as a principled limit of finite-population indices.
The soft spot is the change in granularity: the paper asks whether an individual agent is critical, while this mirror asks whether a positive mass tranche of a type can swing the quota. It therefore does not preserve the count or probability represented by the Banzhaf index. The paper’s raw-index hardness anchor is especially apt nonetheless: \(\eta_n>0\) is itself an existence question, and the mirror preserves that core question as a mass intervention. The mirror is strongest as a continuation of potential pivotality, not as a claim that the full index already has a canonical continuum analogue.
Theorem 2 is a real computational result, so the negative case cannot dismiss this paper for lacking a complexity theorem. Nor does the Clique reduction itself disqualify a mirror: hardness surviving in the type space is a legitimate Class B outcome. The objection is narrower: the proposed mirror changes what “pivotal” means.
In the finite game, \(\eta_i>0\) asks whether one agent can swing a feasible coalition. If a type contains \(K\) interchangeable agents and each person’s vote weight is scaled by \(1/K\), one person’s contribution vanishes as \(K\) grows. The interval of coalition weights that makes that person critical shrinks to zero. In a divisible-mass model, the limiting version is essentially a boundary question: can a compatible coalition be brought arbitrarily close to the quota from below? With divisible mass, that reduces to whether some compatible coalition has capacity at least the quota; the target’s own infinitesimal contribution no longer measures power.
The proposed Mass-Pivotality question avoids that collapse by letting the target type contribute a positive mass \(\delta\). But that is a cohort’s ability to swing the outcome, not an individual agent’s Banzhaf pivotality. The distinction matters in the reduction: each graph vertex becomes an entire type, and a \(k\)-clique supplies enough mass for the target *block* to cross the quota. Replicating every type many times leaves that support-clique witness unchanged. The reduction establishes a sound hardness result for block pivotality, but multiplicity does no work in it.
A stronger alternative would define each type’s power as an aggregate or per-capita limit of its members’ finite Banzhaf indices. That requires choosing how finite coalitions induce a distribution over continuous mass coalitions. The paper’s Banzhaf indices use counting measures on finite subsets; a uniform distribution over mass vectors is a different choice. Under the natural finite-subset sampling, type masses concentrate as \(K\) grows, while individual pivotality typically vanishes except near quota boundaries. Other scalings or probability measures can produce different limits. The paper provides no reason to select one as the continuous version of its index. A chosen limit could still be worth studying, but it would be a new power-index model rather than a direct mirror of Theorem 2. The same concern applies to using Theorem 2’s positivity result: preserving mere existence discards the counting measure that gives the Banzhaf index its meaning.
This is the strongest objection I can make, and it does not close the door. A large caucus with many interchangeable members is a plausible high-multiplicity setting, and the proposed block-pivotality problem is coherent. The negative case is therefore weak against the universal claim: it shows that the cleanest mirror changes from individual power to group intervention, and that a closer index limit needs extra modeling choices. It cannot honestly establish that no worthwhile continuous question exists for this paper.
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.