| paper | An Anytime Algorithm for Optimal Coalition Structure Generation |
| authors | Talal Rahwan, S. Ramchurn, N. Jennings, Andrea Giovannucci |
| venue | JAIR 2009 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Exactly solvable in polynomial time in the explicit input length \(L\); every instance satisfying the stated hypotheses is feasible. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given \(\tau\) complete agent types with population distribution \(\mu\), a team-size bound \(K\), an explicit coalition welfare table \(w(z)\) for \(z\in\mathcal Z_K=\{z\in\mathbb Z_{\ge0}^{\tau}:1\le\|z\|_1\le K\}\), and a size-intensity vector \(h\) satisfying \(\sum_k kh_k=1\), find \(x_z\ge0\) maximizing \(\sum_z w(z)x_z\) subject to \(\sum_z z_t x_z=\mu_t\) for every type \(t\) and \(\sum_{\|z\|_1=k}x_z=h_k\) for every \(k\).
A high-multiplicity configuration LP: types carry population mass \(\mu\), \(x_z\) is the per-capita intensity of coalitions with type profile \(z\), and the objective maximizes anonymous welfare \(w(z)\) while assigning every unit of type mass exactly once.
Theorem 4's identity-sensitive canonical ordering and exact-once guarantee have no literal continuum counterpart; the proposed LP mirrors the paper's broader optimization task rather than that theorem's precise enumeration property.
fatal: False
The mirror covers high-multiplicity coalition-structure optimization and fixed coalition-size subspaces through type-profile intensities; it leaves aside identity-sensitive characteristic functions, the literal FCP enumeration guarantee, finite-agent runtime claims, and the empirical distribution theorems.
Strictly, this paper contains no numbered theorem asserting NP-hardness, membership in \(P\), or another complexity classification. Its statement that CSG is NP-complete appears in Section 1 as prose attributed to Sandholm et al. (1999). The strongest numbered anchor available is therefore an algorithmic one.
My lead anchor is Theorem 4, proved in this paper in Appendix E. It states that, for every integer partition \(G\) of \(n\), the final cyclation process (FCP) generates every coalition structure in the subspace \(P_G\) exactly once. Here \(P_G\) is the set of exhaustive, disjoint coalition structures whose coalition cardinalities are the parts of \(G\). FCP modifies the preceding enumeration procedure when coalition sizes repeat, imposing an ordering condition that removes duplicate orderings of the same unordered coalition structure.
A natural continuous-population mirror is high-multiplicity coalition structure generation.
Take a large population divided into finitely many complete agent types \(T=\{1,\ldots,\tau\}\). For example, in a sensor-fusion system, a type records location class, sensor modality, reliability, battery class, and communication capability. There are \(N\) sensors but only \(\tau\) types, with \(N\gg\tau\); agents of the same type are interchangeable for coalition formation. Let \(\mu_t\) be the fraction of the population of type \(t\), with \(\sum_t\mu_t=1\).
A coalition profile is an integer vector \(z\in\mathbb Z_{\ge0}^{\tau}\), where \(z_t\) is the number of agents of type \(t\) in the coalition. Let
\[ \mathcal Z_K=\{z\in\mathbb Z_{\ge0}^{\tau}:1\le \|z\|_1\le K\}, \]
where \(K\) is a natural team-size limit. The value \(w(z)\) is the welfare generated by one coalition with profile \(z\); it may contain arbitrary complementarities between types and need not be additive.
The continuous decision variable is \(x_z\ge0\), the number of coalitions of profile \(z\) per unit population. The continuous problem is
\[ \operatorname{HM\text{-}CSG}_{\infty}(\mu,w,K): \qquad \max_{x\ge0}\ \sum_{z\in\mathcal Z_K} w(z)x_z \]
subject to
\[ \sum_{z\in\mathcal Z_K} z_t x_z=\mu_t \qquad\text{for every }t\in T. \]
A solution is the vector \(x\), interpreted as a mass-balanced coalition structure: every unit of population is assigned to exactly one coalition, while the aggregate number of coalitions of each profile may be fractional because the population is continuous.
To mirror Theorem 4’s fixed subspace \(P_G\), one can additionally prescribe a continuous coalition-size profile \(h=(h_1,\ldots,h_K)\), where \(h_k\) is the number of size-\(k\) coalitions per unit population and \(\sum_k kh_k=1\). Then impose
\[ \sum_{\|z\|_1=k}x_z=h_k \qquad\text{for every }k. \]
This is the direct high-multiplicity analogue of optimizing over all coalition structures with a fixed integer partition \(G\). Removing the \(h\)-constraints gives the full coalition structure problem.
The discrete bridge is exact. If \(n_t=N\mu_t\) and \(y_z=Nx_z\) is integral, then \(y_z\) is the number of coalitions of profile \(z\). Conversely, every anonymous discrete coalition structure gives such a vector \(y\). Thus the continuous problem is not a lottery over outcomes and does not fractionalize individual coalitions: coalition membership remains integral, while the number of repeated coalition profiles becomes a mass variable.
This is a plausible mirror of the authors’ problem. The paper itself motivates CSG with sensor networks, electronic marketplaces, and other settings containing many interchangeable agents. A population of repeated hardware or buyer types is a sensible high-multiplicity regime. The value function remains genuinely coalition-valued and nonlinear; only irrelevant identities disappear. The paper also explicitly discusses restricting coalition sizes, so the \(K\)-bounded version is recognizably within its model rather than an unrelated optimization problem.
For explicit \(w(z)\), the continuous problem is a finite linear program, hence Class A. Its size depends on the number of type profiles,
\[ |\mathcal Z_K|=\binom{\tau+K}{\tau}-1, \]
rather than on the number \(N\) of named agents. The dual exposes the same pricing structure central to the continuization programme. Without a fixed size profile, the dual is
\[ \min_{p}\ \sum_t \mu_t p_t \]
subject to
\[ \sum_t z_t p_t\ge w(z) \qquad\text{for every }z\in\mathcal Z_K. \]
With a fixed \(h\), an additional dual price is attached to each coalition size. If \(w\) is given compactly, tractability depends on the pricing problem
\[ \max_{z\in\mathcal Z_K} \bigl(w(z)-p\cdot z\bigr), \]
or its size-priced variant. Polynomial pricing would yield a column-generation or separation-based algorithm; hard pricing would give a natural continuum-specific boundary. The finite-agent hardness can also reappear if \(\tau\) grows to \(N\), but that is precisely the regime in which high multiplicity has disappeared.
This mirror covers the underlying exact CSG optimization represented by Theorem 4, not the literal finite enumeration guarantee. FCP’s “exactly once” statement cannot survive verbatim for a continuum, since there is no finite list of continuum coalition structures to enumerate. The meaningful continuization is the mass-balanced optimization problem that FCP searches in finite instances. It should therefore be judged as a Class A reformulation of the underlying problem, not as a continuous version of the enumeration procedure itself.
The weakest point is that Theorem 4 is not a complexity theorem, and the paper’s arbitrary characteristic function \(v(C)\) permits identity-specific values. My mirror restricts to anonymous type-profile values \(w(z)\) and uses a natural team-size bound. If those restrictions are regarded as changing the problem rather than selecting its high-multiplicity regime, the case weakens substantially. Also, for a succinctly represented \(w\), tractability is not automatic: the pricing problem may itself be hard.
So the positive claim is deliberately limited: the paper supports a credible continuous-population mirror of its core coalition-structure optimization in a repeated-type regime, with an LP formulation and a clear pricing boundary. It does not support the stronger claim that every arbitrary characteristic-function CSG instance has a useful continuum analogue, nor does it supply a numbered hardness anchor of the kind requested.
The negative case is strongest against the proponent’s sole anchor, Theorem 4, and it is substantial, though not airtight.
The paper contains no numbered theorem giving a complexity classification. Its statement that CSG is NP-complete is prose attributed to earlier work. Theorem 4 instead proves a correctness property of a finite enumerator: for a fixed finite set of named agents and a fixed integer partition \(G\), FCP generates every set partition in \(P_G\) exactly once. The proof depends essentially on agent identities, a total order on those identities, and canonical ordering among coalitions of equal size.
The proposed continuous model does not continuize that result. Its variable \(x_z\) records how much mass is assigned to each type-profile \(z\). It deliberately identifies all named coalition structures having the same profile histogram. Under the assumed anonymous value \(w(z)\), that identification is sensible, but it removes the very duplication problem Theorem 4 solves. There are no alternative orderings of identical profile-coalitions for FCP to eliminate, and a continuum contains no finite collection of structures that can be generated “exactly once.” The size-profile constraints \(h_k\) restore aggregate coalition sizes, not the individual set partitions or FCP’s canonical representatives.
This produces a genuine dilemma. If arbitrary characteristic-function values \(v(C)\) are retained, then two agents of the same proposed type may have different values in coalitions with particular named agents. A finite type profile cannot represent the input, and the identity-sensitive finite problem remains. If values are instead required to depend only on type composition, then the model becomes a new anonymous configuration problem. That may be a sensible high-multiplicity problem, but it is not a continuous version of the theorem the paper proves.
The proponent’s stronger repair does not remove this mismatch. One could include every coalition-relevant attribute in the type, remove the artificial bound \(K\), or give \(w\) a succinct representation and study the pricing problem
\[ \max_z \bigl(w(z)-p\cdot z\bigr). \]
Those are legitimate questions. But their computational content comes from the chosen representation of \(w\) and from column generation for an anonymous configuration LP, not from FCP, integer partitions, or the paper’s exact-once enumeration theorem. With explicitly listed \(w(z)\), the model is simply a finite LP; with succinct \(w\), the interesting hardness or tractability lies in the newly imposed pricing language. The paper supplies no result about either.
Thus the proponent has shown a credible high-multiplicity mirror of the paper’s underlying optimization problem, not of its named theorem. I would not treat existing high-multiplicity work as a collision—if anything, it supports the regime’s legitimacy. But legitimacy is not enough here: the only anchored result is an identity-dependent enumeration theorem whose substance disappears under aggregation.
The honest limitation is important. I cannot claim that anonymous high-multiplicity coalition-structure generation is intrinsically unworthy. Repeated sensor or buyer types can make the LP and its pricing boundary a worthwhile research problem. The negative case is instead that this paper does not provide a strong anchor for it: preserving Theorem 4 preserves the finite identity problem, while aggregating agents discards the theorem and replaces it with a different configuration-optimization programme.
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.