| paper | d4-conf-aaai-2013-0193 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard even when \(|a_{st}|\leq1\), \(a_{tt}=0\), and \(1/\epsilon=4\tau^3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), a symmetric rational interaction matrix \(a\), and \(\epsilon>0\), treat each type as an atomless population of mass \(\mu_t\). For a coalition with type-mass profile \(q\), define per-capita value \(\phi(q)=\sum_{s<t}a_{st}q_sq_t+\frac12\sum_t a_{tt}q_t^2\), corresponding to pair weights scaled by \(1/N\) in an \(N\)-agent realization. Output a finite rational decomposition into coalition profiles, with residual mass assigned to infinitesimal singleton coalitions, whose welfare is within \(\epsilon\) of the supremum over measurable partitions; measure complexity in \(|T|\), input bit length \(L\), and \(1/\epsilon\).
An atomless population with finitely many complete interaction types, rational mass vector \(\mu\), and symmetric pairwise type-interaction matrix \(a\). A coalition is represented by its type-mass vector \(q\), has quadratic per-capita welfare \(\phi(q)\), and the decision is how to partition the population to maximize total coalition welfare.
With interactions determined only by types, nonzero type-pair interactions create dense blow-ups, so this mirror does not capture the paper’s sparse planar, minor-free, or bounded-degree graph regimes.
fatal: False
The mirror covers the OPT-CS-WGG optimization question anchored by Theorem 1. It does not establish continuous analogues of Theorem 1’s multiplicative inapproximability bounds, or cover Theorems 2–4, the treewidth results, or the graph-class approximation algorithms.
The strongest mirror is the paper’s main optimization problem in a role-symmetric, high-multiplicity regime. Let \(N\gg\tau\) agents share \(\tau\) complete types: a type records the agent’s role and its synergy with every other type. Many agents have each type, and every pair of types has the same interaction for all pairs of agents in those types. This fits settings such as a large production cooperative with repeated skill-and-workflow roles. A society is the rational mass vector \(\mu\), where \(\mu_t\) is type \(t\)’s population share.
The paper’s Theorem 1, proved there, says that OPT-CS-WGG is NP-complete. It also says that, assuming \(\mathrm{P}\ne\mathrm{NP}\), no polynomial-time \(O(n^{1/2-\epsilon})\)-approximation exists for any fixed \(\epsilon>0\), and that no polynomial-time \(O(n^{1-\epsilon})\)-approximation exists unless \(\mathrm{NP}=\mathrm{ZPP}\). The paper proves the hardness by reducing Independent Set to WGG coalition-structure generation; it obtains the approximation barriers from Håstad’s Independent Set bounds. This theorem concerns the decision problem of whether some coalition structure reaches a specified welfare threshold, and its approximation claims concern the corresponding optimization problem.
My lead mirror is Type-Mass OPT-CS-WGG. Its instance is a finite type set \(T\), a rational mass vector \(\mu\) with \(\sum_t\mu_t=1\), a symmetric rational matrix \(a\), and a rational accuracy \(\epsilon>0\). In a finite \(N\)-agent realization, each pair of agents of types \(s,t\) has WGG edge weight \(a_{st}/N\). The \(1/N\) scaling gives finite per-capita welfare as the population grows.
A coalition is represented by its type-mass vector \(q\). Its limiting per-capita value is
\[ \phi(q)=\sum_{s<t}a_{st}q_s q_t+\frac12\sum_t a_{tt}q_t^2. \]
The diagonal coefficient represents interactions between distinct agents of the same type. A feasible coalition structure is a finite or countable list of coalition profiles \(q^{(1)},q^{(2)},\ldots\), together with residual mass \(d\) assigned to infinitesimal singleton coalitions, such that \(\sum_jq^{(j)}+d=\mu\). Its welfare is \(\sum_j\phi(q^{(j)})\). The problem asks for a finite rational decomposition with welfare within \(\epsilon\) of the supremum over all measurable partitions of the atomless population. The natural complexity parameters are \(\tau\), the input bit length \(L\), and \(1/\epsilon\); the output size and bit length count as part of the running time.
There is a concrete reason to expect hardness to survive. The following reduction is my argument for the mirror; it is not a result proved in the paper. Given an Independent Set instance \(G=(V,E)\) with \(n\) vertices, use a special type \(s\) of mass \(\sigma=1/2\), and one type for each vertex, each of mass \(\delta=1/(2n)\). Set \(a_{ss}=3\), \(a_{sv}=1\), \(a_{uv}=-(n+1)\) when \(uv\in E\), and all other coefficients to zero. The positive same-type synergy concentrates the \(s\)-mass: the self-synergy gain from consolidation exceeds the maximum positive \(s\)-to-vertex gain available in secondary coalitions. Candidate-only coalitions have no positive value, so their mass can go to the singleton remainder.
With all \(s\)-mass in one coalition, let \(x_v\in[0,\delta]\) be the mass of vertex type \(v\) placed there. The variable part of welfare is
\[ \sigma\sum_v x_v-(n+1)\sum_{uv\in E}x_u x_v. \]
This function is linear in each \(x_v\) when the other coordinates are fixed, so a maximum occurs at a box corner. If the selected types contain an edge, dropping one endpoint improves the value because \((n+1)\delta^2>\sigma\delta\). Thus a maximizing corner selects an independent set, and the optimum is \(3/8+\alpha(G)/(4n)\), where \(\alpha(G)\) is the maximum independent-set size. This gives an exact-value hardness reduction and, with \(\epsilon<1/(8n)\), an additive-approximation hardness reduction. I therefore expect Class B: the combinatorics live in the type-interaction graph, and a mass-concentration gadget appears to preserve them despite splittable population mass.
The authors should recognize this as their core question—partition agents into teams to maximize pairwise synergy—applied to repeated interaction profiles. The paper itself discusses typed games, which supports the relevance of making \(\tau\) explicit. The mirror covers Theorem 1’s optimization problem in this high-multiplicity regime. It does not claim that the paper’s approximation ratios transfer, or cover the paper’s planar hardness and graph-class algorithms.
My weakest point is that the mirror assumes complete role symmetry: every pair’s interaction is determined by the two agents’ types. That is a real restriction, and the paper’s general graphs allow individualized edges. The reduction’s concentration argument also needs a careful formal proof. The case survives because this symmetry is exactly what makes a type a complete description in a high-multiplicity instance, and the model retains the paper’s team-partition and synergy objective.
The resulting questions include whether the proposed reduction extends to sharper approximation lower bounds; whether planar or bounded-treewidth type-interaction graphs yield algorithms; and what support-size and bit-length bounds make exact optimization or approximation efficient.
The strongest case against this mirror is that it preserves the paper’s coalition objective while replacing its central graph model with a much narrower one. Theorem 1 is a real computational result, so absence of an anchor is not a viable objection. But if agents fall into \(\tau\) complete interaction types, every pair of types with nonzero interaction creates a complete bipartite graph between their populations; a nonzero within-type interaction creates a clique. With many agents per type, these are dense blow-ups. They generally leave the planar, minor-free, and bounded-degree settings that motivate much of the paper’s graph-structure analysis.
The proponent’s Independent Set reduction shows that this restricted model can still encode hard combinatorics in the type-interaction matrix. That is a serious point in its favor, and the reduction’s claim to an inverse-polynomial additive gap appears plausible. But it shows hardness in a new, dense block model as \(\tau\) grows; it does not carry over the paper’s graph-instance structure or its results for sparse graph classes. The type masses make the population large, while the encoded instance still lives in the number of types.
A more faithful attempt would retain heterogeneous or local interactions in a continuous population, perhaps through a graph limit. That raises a different difficulty: local interactions may require agents to have distinct positions or neighborhoods, so a finite type support no longer captures the instance. A richer continuous kernel would need a finite encoding and a specified computational input model before it yields a complexity question. The finite-type formulation avoids that problem, but at the cost of the structural graph regimes that distinguish this paper.
That is the best negative argument I can make: the available mirror is narrow, and the more faithful alternatives are not yet specified as computational problems. It does not defeat the Type-Mass OPT-CS-WGG mirror itself. Repeated production roles with pairwise role synergies are a plausible high-multiplicity setting, and the paper’s discussion of typed games makes it credible that the authors would recognize the question. Theorem 1 therefore survives as a worthwhile continuous mirror; claiming that no scenario does would overstate the case.
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.