| paper | d4-conf-atal-2009-0091 |
| 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 one resource, unit goal requirements, identical integer per-person endowments, and exactly two acceptable goals per type. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.8
statement extracted from the paper’s text layer
Given finite goal and resource sets \(G\) and \(R\), a finite support \(T\) with masses \(\mu_t>0\) summing to one, acceptable-goal sets \(A_t\subseteq G\), per-person endowments \(e_t\in\mathbb{Q}_{\ge0}^{R}\), and per-capita goal requirements \(q(g,r)\in\mathbb{Q}_{\ge0}\), decide whether there is a set \(H\subseteq G\) such that \(H\cap A_t\ne\varnothing\) for every \(t\in T\) and \(\sum_{g\in H}q(g,r)\le\sum_{t\in T}\mu_t e_t(r)\) for every \(r\in R\).
Types carry acceptable goals and per-person resource endowments; their masses form the society. The decision variable is the discrete achieved-goal set \(H\), and the question is whether it satisfies every positive-mass type while meeting each resource’s population-scaled requirement within the society’s average endowment.
Each selected goal is charged at a rate proportional to the whole population, even when only some types accept it; this treats the goal as a population-scaled service or production cost rather than a one-time project cost. The proponent gives a plausible consortium setting but does not establish that the authors would accept this interpretation.
fatal: False
The mirror covers Theorem 3.8’s successful-coalition decision problem. It leaves the results on successful-coalition algorithms, coalition size, maximality, and other parameterizations unaddressed.
The strongest mirror is Continuous Successful Coalition (CSC), for checking whether a specified coalition can be satisfied. Let \(G\) be the goals and \(R\) the resources. A type \(t\) records both its acceptable goals \(A_t\subseteq G\) and its per-person resource endowment \(e_t\in\mathbb{Q}_{\ge 0}^{R}\). The coalition is a distribution \(\mu\) over a finite support \(T\), with \(\sum_t\mu_t=1\). A goal \(g\) requires resource density \(q(g,r)\): in a realization with \(N\) coalition members, that means a total requirement of \(Nq(g,r)\).
CSC asks whether there is a set of achieved goals \(H\subseteq G\) such that every positive-mass type accepts at least one goal and the resources suffice:
\[
H\cap A_t\ne\varnothing\quad\text{for every }t\text{ with }\mu_t>0,
\qquad
\sum_{g\in H}q(g,r)\le\sum_{t\in T}\mu_t e_t(r)\quad\text{for every }r\in R.
\]
A solution is the goal set \(H\). This keeps the paper’s decision question intact: the coalition pools its resources to achieve goals that satisfy every member. The continuous object is the population; goals remain discrete.
The anchor is Theorem 3.8, proved in this paper: deciding whether a specified coalition \(C\) is a Successful Coalition is para-NP-hard parameterized by \(|R|\), with NP-hardness already when \(|R|=1\). The proof reduces from Hitting Set: agents represent sets, goals represent elements, and each agent accepts the goals corresponding to its set. A single agent supplies \(k\) units of one resource, each goal costs one unit, and the coalition is all agents. A feasible goal set is therefore a hitting set of size at most \(k\).
The mirror fits a large virtual organization or production consortium made up of many standardized units. Units of the same type have the same acceptable projects and the same per-person endowment; their mass is their fraction of the coalition. Thus \(N\) can be much larger than the number \(\tau\) of types. The paper itself identifies virtual organizations as a CRG application. For a discrete coalition of \(N\) agents with \(n_t\) members of each type, set \(\mu_t=n_t/N\) and \(q(g,r)=\mathrm{req}(g,r)/N\). Then the continuous inequalities are exactly the discrete feasibility conditions divided by \(N\). Repeating each type any number of times leaves the distribution unchanged while increasing the population.
I expect CSC to be Class B: hardness transfers. The hitting-set choice among goals survives the move to population masses; the hardness is in the goal agenda, not in counting individual agents. This does not establish hardness when \(\tau\) is fixed: the paper’s reduction grows the number of types and goals with the Hitting Set instance. The mirror covers the paper’s successful-coalition checking result, not its maximal-coalition or coalition-size problems. Natural next questions are how CSC behaves when parameterized by \(\tau\) and whether related optimization questions—such as finding the largest satisfiable submass—have tractable cases.
My weakest point is the resource scaling. The paper describes goal requirements as shared project costs, which need not grow with coalition size. CSC treats them as per-person densities, so an author might regard that as a substantive modeling choice. It is most convincing for goals whose required capacity scales with the consortium they serve. The exact discrete-to-continuous correspondence and the paper’s own virtual-organization setting make that choice plausible, but do not make it compulsory.
Theorem 3.8 is a real computational result, so the negative case cannot rest on the paper lacking an anchor. The weak point is the resource scaling needed to make the proposed CSC preserve its Hitting Set reduction.
In the CRG, agents’ endowments add up, while each achieved goal has a fixed resource requirement. If we replicate every agent \(M\) times, total endowment grows by \(M\), but the cost of achieving a goal stays fixed. In the paper’s reduction, that eventually removes the resource bound that encodes the Hitting Set size. The proposed mirror preserves that bound by making each goal require a fixed amount *per person*, so replication also multiplies the goal’s total cost by \(M\). That gives a coherent model of per-person service capacity, but it changes a one-time shared project into a population-scaled demand.
There may be a good production-consortium scenario for that change. The paper’s CRG, though, treats a goal as achieved once, and asks whether every agent accepts at least one achieved goal. A per-person service interpretation would need to say how resources are assigned to the types that want each goal; charging every selected goal against the whole population may not match that interpretation. Adding such assignments could yield a worthwhile model, but it would be a further change to the problem behind Theorem 3.8.
The reduction also has a distinct acceptability set for each Hitting Set element and a special resource-supplying agent, so its support grows with the hardness instance. Replicating agents makes the population large relative to the number of people, but does not show what happens when the number of types is small.
This is a serious objection to the proposed mirror’s fidelity, but it does not establish the universal negative. If the authors regard goals as per-capita services in a large organization, CSC is well-posed and Theorem 3.8 is a strong anchor. The paper alone does not settle whether they would accept that semantics, so the case against is weaker than the proponent’s case for.
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.