| paper | d4-conf-atal-2009-0276 |
| 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: continuous NONDUMMY belongs to \(\mathrm{P}\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given supported types \(T\) with rational masses \(\mu_t\), nonnegative rational per-unit committee weights \(a_{tj}\), rational quotas \(q_j\), and a tested type \(t^\star\), decide whether there are coalition masses \(y_t\in[0,\mu_t]\) and some \(\delta>0\), with \(y_{t^\star}+\delta\le\mu_{t^\star}\), such that \(\sum_t a_{tj}y_t<q_j\) for at least one committee \(j\), while \(\sum_t a_{tj}(y_t+\delta\mathbf{1}[t=t^\star])\ge q_j\) for every committee.
A nonatomic conjunctive weighted voting game over types whose complete descriptions are their committee-weight vectors. The variables are coalition masses \(y_t\) and added tested-type mass \(\delta\); feasibility asks for a losing coalition that becomes winning after adding \(\delta\). Equivalently, test each potentially failing committee with a rational LP that maximizes a common positive slack for its loss and for \(\delta\).
Allowing any \(\delta>0\) can make the answer turn on an arbitrarily small intervention near a quota, without measuring whether a policy-relevant bloc can swing the outcome.
fatal: False
The mirror covers Theorem 7’s DUMMY hardness in the conjunctive subfamily; it leaves the paper’s arbitrary-formula results, Shapley-value results, and core results aside.
The strongest mirror I see is a fractional type-dummy problem for the paper’s conjunctive games. It asks whether a whole type of members can ever be pivotal when coalitions may contain any fraction of each type.
Take a large federation whose members participate in several committees. A type \(t\) is a complete vector of that member’s weights across the committees; members with the same vector are indistinguishable for this problem. The society is a rational distribution \(\mu\) over the supported types, with many members but relatively few distinct weight vectors. A coalition is represented by masses \(y_t\in[0,\mu_t]\). Committee \(j\) passes its issue when \(\sum_t a_{tj}y_t\ge q_j\), and the overall goal is that every committee passes.
Here is the precise decision problem. The instance consists of the supported types \(T\), their masses \(\mu_t\), nonnegative rational per-unit weights \(a_{tj}\), rational quotas \(q_j\), and a tested type \(t^\star\). Is there a coalition mass vector \(y\) and a further positive mass \(\delta\) of type \(t^\star\), with \(y_{t^\star}+\delta\le\mu_{t^\star}\), such that \(y\) loses the overall game but \(y+\delta e_{t^\star}\) wins? A yes-instance has a witness \((y,\delta)\); otherwise type \(t^\star\) is dummy. This is a group-level power question: can adding some available mass of this type ever change the outcome?
My anchor is Theorem 7, proved in this paper. It states that DUMMY is coNP-hard even when every component-game weight is in \(\{0,1\}\) and the Boolean weighted voting game is an \(m\)-vector weighted voting game—that is, its goal is a conjunction of component-game variables. The reduction is from X3C. This is a useful anchor because it is a hardness result, and the mirror keeps the same underlying question—whether a participant can be pivotal—in the paper’s own conjunctive subfamily.
I expect this mirror to be in Class A, tractable by linear programming. For each committee \(j\), test whether it can be the committee that the original coalition fails while the enlarged coalition passes every committee. The constraints are linear in \(y\) and \(\delta\). The strict conditions “fails” and “adds positive mass” can be handled by maximizing a common positive slack. Doing this for each \(j\) takes polynomially many rational LPs, with running time polynomial in the number of committees, supported types, and input bit length. In the X3C construction behind Theorem 7, discrete choices of set-players carry the exact-cover combinatorics; fractional coalition masses can erase that integrality. Whether this particular mirror makes the hardness disappear, and how broadly it does so, is the question worth studying.
The authors could reasonably recognize this as a continuous counterpart to their dummy and swing-player questions: the tested entity still has a vector of weights across committees, and the question is still whether adding it can change a coalition’s outcome. The paper’s resource-allocation motivation also fits naturally: types can encode which committees an organization’s members contribute to, and the goal can encode a package of requirements.
The weakest point is that Theorem 7 asks about adding one named player, while this mirror asks about adding a positive mass of a type. A nonatomic model has no positive-mass individual, so the change of scale needs justification; this is a cohort-level influence question, not automatically a limit of individual dummy status. Also, the X3C reduction uses many distinct set-types, so its hard instances do not themselves establish a regime with population size much larger than support size. I think the mirror remains plausible because the paper’s object is power in a coalitional game, and a cohort’s ability to swing an outcome is a direct power question. But I would present it as a deliberate high-multiplicity extension, not claim a two-way identity with the paper’s discrete DUMMY problem.
The scope is deliberately narrow: it covers Theorem 7’s conjunctive-game result, not the paper’s arbitrary Boolean goals, Shapley-value computation, or core questions. It generates natural follow-ups: what happens for arbitrary goal formulas or negative weights; how the answer changes if the added mass is fixed to one member’s share; and whether a finite-population/type-count formulation gives a useful dictionary to this fractional version.
Theorem 7 is the proponent’s only anchor, and its hardness is specifically about whether one indivisible player can be a swing in some coalition. In the X3C reduction, each set is a player whose membership is needed to cover elements. The proposed mirror changes that object: it asks whether a *positive mass* of a type can swing the outcome. Fractional coalition masses can split the set-players’ contributions, so this is not a high-multiplicity version that preserves the reduction’s source of difficulty. The reduction also gives each set-player a distinct weight vector, so it supplies no evidence that the hard instances themselves have many agents per type.
The gap matters most for the literal type-dummy question. A single member’s share tends to zero as the population grows; in a nonatomic society, adding that member changes no mass at all. Asking whether *any positive amount* of a type can swing instead allows arbitrarily small interventions and may turn on whether a coalition can approach a quota boundary. Requiring a fixed positive amount, such as a specified fraction of the type, avoids that vanishing intervention. But it asks whether a bloc can swing an outcome, not whether an individual is dummy. Keeping the individual question would require retaining finite granularity—or adding a distinguished atom to the continuous population—so the paper’s player-level result would not have a clean population-continuum limit.
That is the strongest case against this anchor: Theorem 7 does not itself motivate the proposed continuum question, and the most faithful individual-level limit loses the individual’s influence. Still, it does not establish that the bloc question is unworthy. Bloc influence is recognizable in a paper about coalitional power, and a fixed-mass version could be a sensible continuous question. The honest negative case is therefore weak on the universal claim: it can challenge whether this is truly a mirror of Theorem 7, but it cannot rule out a worthwhile, author-recognizable continuous extension.
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.