| paper | On the Online Coalition Structure Generation Problem |
| authors | M. Flammini, G. Monaco, Luca Moscardelli, Mordechai Shalom, S. Zaks |
| venue | JAIR 2021 |
| filed under | coalition · hedonic |
| judged by | gpt-5.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: Every finite multiplicative approximation is \(\mathrm{NP}\)-hard, already for \(k=3\), and for every fixed \(k\ge3\). No polynomial-time algorithm with any finite factor \(\rho(\tau,k,L)\) exists unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.5
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\ge0\) summing to \(1\), integer \(k\ge3\), symmetric rational interactions \(w_{tu}\), and rational threshold \(\theta\), choose \(x_{tq}\ge0\) with \(\sum_{q=1}^{k}x_{tq}=\mu_t\) for every \(t\), and compute an assignment maximizing \(F(x)=\frac12\sum_{q=1}^{k}\sum_{t,u\in T}w_{tu}x_{tq}x_{uq}\), or decide whether \(\max_x F(x)\ge\theta\).
A high-multiplicity offline MaxW-CSG model with finite complete types \(T\), masses \(\mu\), at most \(k\) coalition labels, mass variables \(x_{tq}\), and quadratic within-coalition welfare \(F(x)=\frac12\sum_{q,t,u}w_{tu}x_{tq}x_{uq}\).
The split-mass formulation does not preserve the paper’s \(k\)-colorability equivalence, while a positive-cohesion repair can force whole-type placement and make the continuum resemble finite weighted \(k\)-partitioning.
fatal: False
The mirror covers only the offline \(k\)-coalition MaxW-CSG inapproximability result, Theorem 3.5; it leaves the online competitive-ratio results, MaxFW-CSG, and bounded-coalition-size analyses untouched.
The strongest mirror I believe in is an offline, high-multiplicity version of the paper’s \(k\)-coalition problem. It is enough to establish a serious continuous mirror; I would not stretch the case to cover every online theorem.
Call it HM-\(k\)-MaxW-CSG. An instance consists of a finite set of agent types \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), an integer \(k\ge 3\), and a symmetric rational compatibility matrix \(w:T\times T\to\mathbb{Q}\). A type is complete: agents of type \(t\) have exactly the same interaction weight with every type \(u\), including other agents of type \(t\).
A solution is a mass assignment \(x_{tq}\ge 0\), where \(x_{tq}\) is the mass of type \(t\) placed in coalition \(q\), satisfying
\[ \sum_{q=1}^{k}x_{tq}=\mu_t \]
for every \(t\). Letting \(w_{tu}\) denote the weight between two agents of types \(t\) and \(u\), its continuous total welfare is
\[ F(x)=\sum_{q=1}^{k}\frac12\sum_{t,u\in T}w_{tu}x_{tq}x_{uq}. \]
The question is to compute an assignment \(x\) maximizing \(F(x)\), or, in decision form, to determine whether \(\max_x F(x)\ge \theta\) for a given rational threshold \(\theta\). This is a question about the underlying coalition problem, not about a quadratic-programming encoding.
The regime is natural in exactly the sense required by the programme. Think of a large employer assigning a very large workforce to at most \(k\) departments. Workers belong to a finite catalogue of role, skill, and location types; two workers of the same type are interchangeable for the model’s purposes, and the collaboration value of a department depends on the pairwise compatibility of its types. There may be millions of workers but only tens or hundreds of types. Splitting \(x_{tq}\) across departments does not split an individual: it represents assigning different members of a large homogeneous cohort to different departments.
This is genuinely a population continuization. The coalitions remain discrete groups, and the graph-based welfare function remains the same. Only the population is represented by mass. If a finite instance has \(N_t\) agents of type \(t\), then \(x_{tq}=X_{tq}/N\) is its normalized count assignment, and the displayed objective is the leading \(N^2\)-scaled limit of the discrete total edge weight. Thus this is a high-multiplicity relaxation, not merely an outcome-space relaxation.
My anchor is Theorem 3.5, proved in this paper. It states:
The offline variant of MaxW-CSG is inapproximable for any \(k\ge 3\), unless \(P=NP\).
The proof reduces \(k\)-Colorability. Given an unweighted graph \(G'\), the paper constructs a complete weighted graph \(G\) on the same vertices: an edge has weight \(1\) when it is a non-edge of \(G'\), and weight \(-|E(G')|\) when it is an edge of \(G'\). For \(k<n\), \(G'\) is \(k\)-colorable if and only if the optimum coalition structure in \(G\), using at most \(k\) coalitions, has positive total weight. A \(k\)-coloring gives coalitions that are independent sets of \(G'\), hence positive weight; conversely, any coalition containing an edge of \(G'\) incurs a penalty large enough to make the total welfare non-positive. The case \(k=n\) is trivially positive.
The continuous question above is therefore my lead mirror of Theorem 3.5. I expect it to be hard, most plausibly in Class B, because the reduction’s combinatorics live in the compatibility structure among types, not in the number of separately named agents. We can give every vertex of \(G'\) a type and then give that type an arbitrarily large multiplicity. The number of agents can be made enormous while the hard object remains the type-interaction graph.
There is one important complication: continuous mass can split a type between coalitions, whereas the paper’s reduction assigns each vertex integrally. That means Theorem 3.5 does not transfer automatically. A plausible hardness lift is to give each type a sufficiently strong positive within-type interaction. Splitting type \(t\)’s mass then loses diagonal cohesion, and a sufficiently large same-type weight forces an optimum to keep each type together. The remaining choice is precisely which of at most \(k\) coalitions receives each type, recovering the coloring reduction. This would make the hardness genuinely high-multiplicity: the replicated agents are interchangeable, while the reduction lives in the finite type graph.
I would not claim that lift as already proved by the paper. If within-type cohesion is disallowed, or if unrestricted fractional splitting produces a substantially easier quadratic optimization problem, that is itself an interesting outcome: the mirror could become Class C, or even tractable, because continuization has changed the combinatorics. Either way, the stated HM-\(k\)-MaxW-CSG problem is a legitimate computational question the authors would recognize as their coalition-structure problem.
The scope is deliberately narrow: it covers Theorem 3.5’s offline inapproximability result, not the paper’s online competitive-ratio theorems. The main weakness is therefore clear: the paper’s most distinctive online aspect is not being mirrored, and the hardness transfer requires dealing honestly with fractional type splitting. But that weakness does not undermine the mirror itself. A large, typed workforce assigned to a small number of departments is a convincing continuous population regime, and whether the paper’s discrete hardness survives that regime is exactly the kind of computational question the continuization programme is meant to expose.
The strongest negative case attacks the only anchor, Theorem 3.5. Its reduction fundamentally uses indivisible vertices: every vertex must be assigned wholly to one of \(k\) coalitions. In the proposed model, a type may split, so the reduction no longer gives an equivalence. The penalty edge contributes
\[ -|E(G')|\sum_{q=1}^{k}x_{tq}x_{uq}, \]
rather than imposing a discrete penalty whenever two vertices receive the same colour. A fractional assignment need not make any coalition an independent set, so \(F(x)>0\) need not characterize \(k\)-colourability. The theorem therefore does not transfer automatically.
The proposed repair—adding strong positive within-type cohesion—creates a deeper problem. With all other rows fixed, the objective’s dependence on type \(t\) has the form
\[ \frac{M}{2}\sum_q x_{tq}^{2}+\sum_q b_qx_{tq}. \]
For \(M>0\), this is strictly convex on the mass simplex, so a maximizer assigns all of type \(t\) to one coalition. Directly imposing unsplittable types has the same effect. The continuous population then disappears: the problem is simply weighted \(k\)-partitioning on the finite type set \(T\), with \(\mu_t\) acting as a vertex weight. The hardness has been recovered by reintroducing discrete type placement, not by a substantive continuum phenomenon.
The alternative—retain \(w_{tt}=0\) and permit splitting—is mathematically coherent, but it is a new mean-field block-graph problem rather than a faithful lift of the paper’s reduction. Its computational information sits in the explicit compatibility matrix on types, while the large population merely supplies divisible mass. That is a reasonable research question, but it is no longer clear why it belongs to this paper rather than to continuous quadratic graph partitioning. The paper’s distinctive online content is even less transferable: in an atomless arrival process, an individual arrival has zero mass, so irrevocable online decisions become vacuous unless one introduces positive-mass batches or a measure-valued arrival process, which changes the model.
This is the best case against the mirror: the hardness anchor depends on integrality, and the natural ways to restore that integrality either collapse the continuum or introduce new structure. But the negative case is ultimately weak. A large typed workforce with divisible cohort mass is a sensible high-multiplicity regime, and whether fractional splitting preserves, destroys, or changes the colouring obstruction is itself a legitimate computational question. I therefore could not honestly defend the universal claim that no worthwhile mirror exists. The proponent’s formulation should survive, albeit as a qualified open mirror rather than as an established hardness transfer.
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.