| paper | d4-conf-atal-2010-0190 |
| 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 and \(\mathrm{W}[1]\)-hard parameterized by \(\tau\); therefore not FPT unless \(\mathrm{FPT}=\mathrm{W}[1]\). An XP algorithm runs in \((m+1)^\tau\operatorname{poly}(m,\tau,d,L)\) time. · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 5.3
statement extracted from the paper’s text layer
Given a finite support of CRG types with masses \(\mu_t\), each type’s accepted goals and per-agent resource endowments \(e(t,r)\), per-population goal demands \(q(g,r)\), and target mass \(\kappa\), does there exist a mass vector \(x\) and goal set \(S\subseteq G\) such that \(0\le x_t\le\mu_t\), \(\sum_t x_t=\kappa\), every type with \(x_t>0\) accepts at least one goal in \(S\), and \(\sum_t x_t e(t,r)\ge\sum_{g\in S}q(g,r)\) for every resource \(r\)?
A decision problem over a society distribution \(\mu\) on complete CRG types. The decision variables are selected type masses \(x_t\) and a discrete achieved-goal set \(S\); pooled supplies and goal demands are measured per unit of population, so both scale with population size. The question is feasibility for an exact target coalition mass \(\kappa\), with no separate optimization objective.
The mirror covers Theorem 5.3’s exact-size successful-coalition decision problem in CRGs; it leaves the paper’s other CRG results, its core and Shapley results, and Theorem 5.1’s strategic-equivalence hardness result aside.
The strongest mirror I see is Mass-ESCK, the continuous version of exact-size successful coalition formation in CRGs.
The anchor is Theorem 5.3, proved in this paper: for a CRG with at most \(t\) agent types and an integer \(k\), deciding whether there is a successful coalition of exactly \(k\) agents is polynomial-time tractable for every fixed \(t\). The paper proves this by considering coalition types and checking whether each can succeed.
In Mass-ESCK, the society is a distribution \(\mu\) over \(\tau\) complete CRG types. A type records both the goals its members accept and their resource endowment profile. Its mass \(\mu_t\) is the fraction of the population with that profile. Given a target mass \(\kappa\), ask whether there is a coalition mass vector \(x\), with \(0\le x_t\le\mu_t\) and \(\sum_t x_t=\kappa\), and a set of achieved goals \(S\), such that every selected type accepts at least one goal in \(S\), and the coalition’s aggregate resources cover the requirements of \(S\). The solution is \((x,S)\). For normalized mass, resource endowments and goal requirements are expressed in per-capita units; at population size \(N\), the corresponding totals scale with \(N\).
This is the paper’s problem in mass terms: it still asks whether a coalition of a specified size can satisfy all its members using resources pooled from those members. A plausible regime is a large workforce or service organization with standardized roles: many people, but a fixed set of role profiles describing goal eligibility and resource endowments. The paper itself motivates its results with precisely the case where the population grows while the number of types stays small. Its fixed-type results are supporting evidence for this regime, not a novelty collision: the theorem treats integer coalitions, while this mirror asks about rational masses and fractional coalition compositions.
I expect Mass-ESCK to be tractable for fixed \(\tau\). In any successful coalition, one can choose one acceptable goal per selected type, so some witness goal set has size at most \(\tau\). Enumerate those sets; for each one, testing whether a feasible mass vector \(x\) exists is a linear feasibility problem. This gives a polynomial algorithm for fixed \(\tau\), with a bound of roughly \(|G|^\tau\) times a polynomial in the input size. That is polynomial for fixed support, not an FPT bound in \(\tau\). A useful next question is whether the largest successful coalition mass, possibly with type-dependent recruitment costs, can be optimized efficiently. The discrete-to-continuous bridge also needs a rounding result: a fractional solution need not correspond to an exactly sized finite coalition without some resource slack.
The paper’s Theorem 5.1 is a proved NP-hardness result for deciding whether two CRG agents are strategically equivalent. I would not use it as a second mirror anchor. Its reduction gives the element agents distinct resource profiles, so the support grows with the Exact-3-Cover instance; it does not supply the same strong small-support population regime as Theorem 5.3.
The scope of this case is deliberately narrow: it mirrors Theorem 5.3’s exact-size successful-coalition problem in CRGs. It makes no claim about the paper’s core, Shapley-value, or other representation results.
The weakest point is the resource normalization. The original CRG model has discrete agents and resource quantities, while the mirror allows rational type masses and aggregate resource totals. That change is credible for a large population with pooled resources and per-capita requirements, but an author studying indivisible resources for small coalitions might reject it as a different regime. The society is still the continuous object, and the goal set remains discrete.
The strongest objection to the proposed Mass-ESCK mirror is a scaling mismatch in what counts as a goal. Theorem 5.3 concerns finite coalitions with finite resource endowments and fixed resource requirements. If a population grows to \(N\) agents, a coalition of mass \(\kappa>0\) contains about \(\kappa N\) agents, so its available resources grow with \(N\) while a fixed requirement \(\operatorname{req}(g,r)\) does not. In normalized units, that requirement tends to zero. The limiting feasibility test can therefore lose the resource bottleneck that makes coalition success meaningful: any positive mass of a resource-bearing type may eventually suffice.
Avoiding that collapse means scaling goal requirements with \(N\), so goals express population-level or per-capita obligations. That is a coherent model for a large workforce, but it changes the goals from fixed tasks in the paper’s CRG instance to tasks whose resource demand grows with the population. The paper’s exact-size theorem does not itself establish that authors studying CRGs would regard this scaled-goal question as the same problem.
That objection does not defeat the best mirror, though. The programme explicitly allows co-modifications needed to make a continuous society meaningful, and population-proportional goals are plausible in large service organizations. With those goals, the mirror is well-posed: types can record eligibility and per-capita resources, and the target coalition mass can be tested against aggregate supplies. Optimizing successful coalition mass or recruitment cost would make the question more useful still. The fact that these versions may reduce to enumeration plus linear feasibility is not a reason to reject them under the programme’s stated standard.
The proponent raised only Theorem 5.3 as an anchor. Theorem 5.1’s hardness result was explicitly not offered as one, and its growing type space does not undermine the fixed-type scenario in Theorem 5.3. So the honest negative case is weak: the scaling issue is a real modeling seam, but a plausible continuization closes it. Mass-ESCK survives as a worthwhile mirror.
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.