| paper | d4-conf-atal-2008-0256 |
| 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}\)-hard under polynomial-time Turing reductions; more precisely, \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given finite skills \(S\), tasks \(J\) with required sets \(R_j\subseteq S\), a threshold \(q\), supported types \(\Theta\) with bundles \(A_\theta\subseteq S\) and positive rational masses \(\mu_\theta\) summing to \(1\), and a target type \(\theta^\star\), decide whether for every subdistribution \(x\le\mu\) with \(x_{\theta^\star}=0\), \(V(x+\delta e_{\theta^\star})=V(x)\) for every \(0<\delta\le\mu_{\theta^\star}\). Here \(V(x)=1\) iff at least \(q\) tasks each have every required skill supplied by positive selected mass, and \(V(x)=0\) otherwise.
A distribution over complete skill-bundle types; coalitions choose submass \(x\le\mu\), task coverage depends on positive supply of each required skill, and DUMMY asks whether adding positive mass of a target type ever crosses the task-count threshold.
Because any positive selected mass supplies the full skill bundle, the mirror has no mass-sensitive notion of marginality; the proponent acknowledges support sensitivity but does not remove this limit.
fatal: False
Covers the TCSG-T part of Theorem 5; it leaves the WTSG-T part and the paper’s other dummy, core, Shapley, and Banzhaf results aside.
I would lead with Continuous Type-Dummy for Threshold Task Count Skill Games. The anchor is Theorem 5, proved in this paper: DUMMY is coNP-complete for TCSG-T and WTSG-T. In these games, an agent is dummy if adding it to any coalition never changes that coalition’s value. The theorem says it is coNP-complete to decide whether this holds, even when the game is restricted to task-count threshold games. The paper proves the hardness by reducing 3SAT to the existence of a coalition for which the target agent is pivotal.
Here is the continuous problem I would hand to a prover. An instance has a finite skill set \(S\), tasks \(J\) with required skill sets \(R_j\subseteq S\), a threshold \(q\), and a support \(\Theta\) of voter-like worker types. Each type \(\theta\) has a complete skill bundle \(A_\theta\subseteq S\) and positive rational mass \(\mu_\theta\), with \(\sum_{\theta\in\Theta}\mu_\theta=1\). A coalition is a subdistribution \(x\), where \(0\le x_\theta\le\mu_\theta\). It can perform task \(j\) exactly when every required skill has positive supply:
\[
\sum_{\theta:\,s\in A_\theta}x_\theta>0
\quad\text{for every }s\in R_j.
\]
Write \(V(x)=1\) if the coalition performs at least \(q\) tasks, and \(V(x)=0\) otherwise. Given a target type \(\theta^\star\), ask whether it is dummy: for every coalition with \(x_{\theta^\star}=0\), does adding any positive available mass of that type leave the value unchanged? In symbols, is
\[
V(x+\delta e_{\theta^\star})=V(x)
\]
for all such \(x\) and all \(0<\delta\le\mu_{\theta^\star}\)? The answer is the decision solution; a non-dummy witness is a coalition mass vector and a positive \(\delta\).
The regime is a large project-based workforce or contractor pool with a finite catalogue of skill profiles: many workers share the same relevant certifications, and tasks require specified bundles of those skills. The population size \(N\) can be far larger than the number \(\tau=|\Theta|\) of supported profiles. The question is whether a cohort with one profile can make some otherwise losing collaboration winning. That is close to the paper’s dummy question: it preserves the task-coverage rule and the counterfactual over coalitions, replacing the addition of one agent with the addition of positive mass of a type.
The paper’s reduction lifts directly. For a formula with \(m\) clauses, create a type for each clause-literal agent, carrying the clause skill and that literal’s skill. Make one task per clause, and for each variable make \(m+1\) copies of a task requiring both its positive and negative skills. Add a target type with a unique skill required by one further task, and set the winning threshold to \(m+1\). Give every type positive rational mass. A coalition is made winning by adding target mass exactly when it can perform all \(m\) clause tasks without already performing a variable-task family. Such a coalition exists exactly when the formula is satisfiable. Partial mass does not alter the reduction: a skill bundle is present precisely when the selected mass of its type is positive. Non-dummy has a polynomial certificate—the support of the coalition—so this mirror is expected to remain coNP-complete. I classify it as hardness transfers (Class B).
The important qualification is that this is type-level marginality. The continuum has no positive-mass individual, so “add this agent” becomes “add positive mass of this complete type.” Also, because tasks depend on skill coverage, the value sees which types have positive selected mass, not how much mass they contribute. Thus the action is continuous, but the hard combinatorics still live in the support. That is the weakest point: a referee might regard the type-level question as too different from individual DUMMY. I think the mirror remains plausible because it keeps the paper’s coalition, skill-coverage, and pivotality semantics intact, and the population itself is genuinely a distribution over types. The support sensitivity is a property of the original task model, not an artificial simplification.
This mirror covers Theorem 5’s TCSG-T result, rather than claiming to continuize every result in the paper. It also leaves useful questions: does hardness persist with bounded skill occurrence or bounded threshold \(q\)? What is the parameterized complexity in the number of skills or types? Could one ask for the minimum target mass needed to make some coalition winning?
Theorem 5 is a real obstacle to a negative verdict: it gives a named computational result, and a large workforce with repeated skill profiles is a plausible high-multiplicity setting for CSGs. The strongest objection is that the proposed mirror’s masses do no work. In a TCSG-T game, a task is completed as soon as each required skill is present. For any selected type, an arbitrarily small positive mass supplies all its skills; increasing that mass changes nothing. Thus the type-dummy question depends only on which types are selected, not on their proportions, population size, or rational bit lengths.
That creates a singular limit for individual pivotality. A worker’s discrete contribution corresponds to mass \(1/N\), which vanishes as the workforce grows, yet it can still complete a task. The proposed mirror handles this by asking whether *any* positive mass changes the value. That is coherent as a support-based type question, but it is not a continuous marginal effect. Requiring a positive population fraction before a skill counts would avoid the singularity, but it would replace the paper’s qualitative skill coverage with quantitative production requirements—a different game, not a modification forced by making the population continuous.
This is a meaningful limitation for the programme: the mirror offers no mass optimization or approximation problem, and its “continuous” decision turns entirely on the finite support. But I cannot honestly claim that this defeats the anchor. Support-based type pivotality preserves the paper’s coalition and task semantics, and the workforce scenario makes the high-multiplicity regime plausible. The objection narrows the mirror’s value; it does not establish that the question is unrecognizable or not worth asking. The negative case is therefore weak against this anchor.
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.