| paper | d4-conf-aaai-2011-0139 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even with equal masses and endowments and requirements in \(\{0,1\}\); \(\mathrm{W[1]}\)-hard parameterized by \(\tau\), hence not FPT unless \(\mathrm{FPT}=\mathrm{W[1]}\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 8.1
statement extracted from the paper’s text layer
Given goals \(G\), resources \(R\), and a distribution \(\mu\) over \(\tau\) types, where each type \(t\) has an acceptable-goal set \(A_t\subseteq G\) and per-agent endowments \(e_{t,r}\), and each goal \(g\) has population-normalized requirements \(q_{g,r}\), determine whether there is a nonempty goal set \(S\subseteq G\) such that \(A_t\cap S\neq\emptyset\) for every type with \(\mu_t>0\), and \(\sum_{g\in S}q_{g,r}\leq\sum_t\mu_t e_{t,r}\) for every resource \(r\in R\).
The specified coalition is the whole unit-mass society. Types carry masses \(\mu_t\), acceptable-goal sets \(A_t\), and per-agent endowments \(e_{t,r}\); the decision variable is a nonempty goal set \(S\). Resource requirements \(q_{g,r}\) are normalized to the population scale, and feasibility compares their sum with aggregate type-level supply.
The mirror assumes goal resource requirements scale with population, whereas the paper formulates them as fixed quantities; its virtual-organization example would need projects whose resource needs grow with the workforce.
fatal: False
The fixed-cohort mirror covers SC and Theorem 8.1; the separate quota-selection mirror in the case covers ESCK and Theorem 13.1. The other resource, bound, and conflict problems and their parameterized results are not covered.
My lead is the paper’s Theorem 13.1, proved here: ESCK—whether there is a successful coalition of exactly \(k\) agents—is para-NP-hard when parameterized by \(|G|\). The proof reduces Independent Set to instances with just one goal. This is a useful anchor because it isolates a sharp question: does that hardness survive when a coalition is a share of a population, rather than a set of individually chosen agents?
Call the mirror Continuous Quota Coalition Existence. An instance gives a finite set of goals \(G\), resources \(R\), and \(\tau\) types with masses \(\mu_t>0\) summing to \(1\). Each type \(t\) has an acceptable-goal set \(A_t\subseteq G\) and per-agent resource endowments \(e_{t,r}\). Each goal \(g\) has a resource requirement \(q_{g,r}\), measured per unit of the whole population, and the instance specifies a target coalition mass \(\alpha\in(0,1]\).
The question is whether there are a nonempty goal set \(S\subseteq G\) and selected masses \(x_t\) such that \(0\le x_t\le\mu_t\), \(\sum_t x_t=\alpha\), and \(x_t=0\) whenever \(A_t\cap S=\emptyset\). The selected coalition must also have enough resources: for every \(r\in R\), \(\sum_{g\in S}q_{g,r}\le\sum_t x_t e_{t,r}\). A solution is \(S\) and the vector \(x\); this is a feasibility question, with no optimization objective.
This is a natural high-multiplicity version of ESCK. In a large virtual organization or workforce, many interchangeable participants can share the same goal acceptances and resource profile. The coalition quota says what fraction must be assembled. Resource requirements are normalized to population scale, so a discrete instance with \(n\) agents, coalition size \(k\), and requirement \(req(g,r)\) maps to target mass \(k/n\) and requirement \(req(g,r)/n\). The goal set remains discrete; the population and coalition selection become continuous.
For any fixed \(S\), feasibility is a rational linear program in the \(x_t\). Enumerating nonempty goal sets therefore gives an exact algorithm in \(2^{|G|}\operatorname{poly}(\tau,|R|,L)\) time, where \(L\) is the input bit length. In Theorem 13.1’s one-goal setting, the mirror is just one linear program. I expect this mirror to be tractable, and the paper’s para-NP-hardness to dissolve: its reduction’s indivisible choice of agents is replaced by fractional selection from type pools. This does not claim that the theorem’s particular hard instances have few types; its reduction uses vertex-specific resource profiles. The claim is that the high-multiplicity problem is meaningful in regimes with repeated profiles and that its fractional mass formulation is efficiently solvable.
A strong boundary companion is Theorem 8.1, also proved here: SC—whether a specified coalition is successful—is W[1]-hard parameterized by \(|C|\). Its continuous mirror, Continuous Fixed-Cohort Success, takes the distribution of a specified coalition over types, with each type’s acceptable goals and per-agent resource endowments, plus per-population goal requirements. It asks for a nonempty goal set \(S\) accepted by every positive-mass type and satisfying \(\sum_{g\in S}q_{g,r}\le\sum_t\mu_t e_{t,r}\) for every resource. The solution is \(S\).
Theorem 8.1’s reduction embeds in this question. Give each of its \(k\) role types mass \(1/k\), acceptance set \(G_i\), and one unit of each resource per agent. Normalize its goal requirements by \(k\): a goal uses one unit of each resource corresponding to an incident graph edge. Each resource then has aggregate supply \(1\). Feasibility prevents choosing goals for adjacent vertices, while satisfaction requires at least one goal for every role. Thus the continuous mirror remains W[1]-hard in its support size \(\tau=k\): the hard combinatorics live in the role-to-goal choices, not in the number of copies of each role. I expect hardness to transfer for this fixed-cohort question.
The lead is Theorem 13.1; the second mirror helps locate the boundary. Together they cover two of the paper’s central coalition questions, not its entire collection of resource and conflict problems. They also show why a continuous CRG is not simply “the same model, but fractional”: some questions become linear feasibility over selected mass, while others retain combinatorial goal choice.
The weakest point is that Continuous Quota Coalition Existence lets the decision-maker select arbitrary fractional mass from each type. In a small coalition, the exact identities and indivisibility in ESCK may be central. The mirror is most convincing for large pools of interchangeable participants, where quota-based assembly and aggregate resource accounting are natural. Scaling project requirements with population is part of that model and should be stated openly.
The paper gives genuine computational anchors, so the “no named result” objection is unavailable: Theorems 13.1 and 8.1 state parameterized hardness results. The strongest case against their mirrors is about whether the proposed mass models describe high multiplicity in the paper’s CRG sense.
For Theorem 13.1, the reduction gives each graph vertex its own resource-endowment profile. Its one-goal instances therefore have up to \(n\) distinct types, and the hard coalition is chosen from individually distinct profiles. The proposed continuous quota problem turns that choice into a fractional LP. That is a coherent question, but the reduction itself does not exhibit repeated agents per type. To make a genuine high-multiplicity family, one could clone every profile. With the goal’s original fixed resource requirement, the growing coalition’s supply eventually overwhelms that demand. Keeping the constraint binding requires scaling the goal requirement with the population or quota. That is plausible for a project whose resource needs grow with its workforce, but it changes the interpretation of a goal in this paper’s model of fixed requirements. This is a real modeling gap in the bridge from the theorem to the proposed mirror.
Theorem 8.1 has a similar gap. Its \(k\) coalition members occupy distinct roles, each with a different acceptable-goal set, and the reduction uses one member per role. Giving those roles masses \(1/k\) faithfully encodes the finite construction, but does not by itself supply many interchangeable agents of each type. Cloning the roles again requires scaling resource demands to preserve the constraints. The strongest skeptical reading is that the mirror is a role-template problem over goal choices, rather than a demonstrated continuum limit of the hard instances.
Those objections do not defeat the better versions of either mirror. A large organization could have many interchangeable participants in each role, and a project could consume resources in proportion to the workforce assembled. Then a type distribution, a quota mass, and population-scaled requirements are sensible modeling choices. For fixed goal sets, feasibility is computationally well-defined; the fixed-cohort version also retains the role-to-goal choices from Theorem 8.1. The resulting tractability or hardness is not an objection under the programme’s criteria.
So the honest negative case is weak. It raises a substantive question about whether scalable goals and repeated role types belong to the authors’ intended CRG applications. The paper’s virtual-organization setting makes those choices plausible, and the formal model does not rule them out. I cannot 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.