| paper | Online Coalition Structure Generation in Graph Games |
| authors | M. Flammini, G. Monaco, Luca Moscardelli, Mordechai Shalom, S. Zaks |
| venue | ATAL 2018 |
| filed under | coalition · hedonic |
| judged by | gpt-5.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: Every finite-factor polynomial-time multiplicative approximation is impossible unless \(\mathrm{P}=\mathrm{NP}\), already for every fixed \(k\ge3\), equal dyadic masses, and nonzero weights in \(\{-1,+1\}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.4
statement extracted from the paper’s text layer
Given finite types \(T\), rational masses \(\mu_i \ge 0\) with \(\sum_i \mu_i = 1\), an integer \(k \ge 3\), and symmetric rational interaction weights \(\omega_{ij}\) with \(\omega_{ii}=0\), choose \(x_{ir} \ge 0\) satisfying \(\sum_{r=1}^{k} x_{ir} = \mu_i\) to maximize \(\operatorname{TW}(x)=\sum_{r=1}^{k}\sum_{i<j}\omega_{ij}x_{ir}x_{jr}\), or decide whether the optimum is positive.
A population consists of recurring agent types with masses \(\mu_i\); \(x_{ir}\) is the mass of type \(i\) assigned to coalition \(r\), and welfare is the sum of pairwise type interactions within coalitions. Replicating each type \(N\) times gives the finite graph-game objective scaled by \(N^2\).
The reduction uses one type per original graph vertex and \(\omega_{ii}=0\), so optimal allocations purify and the construction tests high multiplicity more than genuinely fractional coalition formation; this limits richness but not legitimacy.
fatal: False
The mirror directly covers Theorem 3.4 and formulates an open continuous analogue of Theorem 4.10; it leaves the other online competitive-ratio bounds and parameter variants untreated.
There is a credible positive mirror, and my strongest anchor is the paper’s offline hardness result.
The lead anchor is Theorem 3.4, proved in this paper. It states that the offline variant of MaxWC is inapproximable for every \(k\ge3\), unless \(P=NP\). The reduction starts from \(k\)-Colorability: given \(G'\), it constructs a complete weighted graph on the same vertices, assigning weight \(1\) to nonedges of \(G'\) and a large negative weight, printed as \(-|E(G')|\), to edges of \(G'\). The claimed property is that \(G'\) is \(k\)-colorable exactly when the optimum coalition structure has positive weight. Thus a multiplicative approximation would distinguish positive from zero optimum.
A natural continuous version is Continuous Type-Graph MaxWC\(_k\). An instance consists of a finite set of types \(T\), a rational mass vector \(\mu\) with \(\sum_i\mu_i=1\), an integer \(k\ge3\), and a symmetric rational compatibility matrix \(\omega_{ij}\), with \(\omega_{ii}=0\). A type is a complete teamwork profile: all agents of type \(i\) have the same pairwise weight \(\omega_{ij}\) against every agent of type \(j\). The population contains mass \(\mu_i\) of type \(i\).
A solution assigns every infinitesimal agent to one of at most \(k\) coalitions. Let \(x_{ir}\) be the mass of type \(i\) assigned to coalition \(r\), so \(\sum_r x_{ir}=\mu_i\). Its value is
\[ \operatorname{TW}(x) = \sum_{r=1}^{k}\sum_{i<j}\omega_{ij}x_{ir}x_{jr}. \]
The problem is to maximize this value, or decide whether some feasible \(x\) has \(\operatorname{TW}(x)>0\).
This is genuinely a high-multiplicity version of the paper’s problem. For an integer \(N\), replace mass \(\mu_i\) by \(N\mu_i\) indistinguishable agents of type \(i\), give every cross-type pair weight \(\omega_{ij}\), and give same-type pairs weight zero. Then \(x_{ir}=n_{ir}/N\), and the continuous objective is exactly the finite total coalition weight divided by \(N^2\). We may take \(N\gg |T|\), for example many thousands of employees in each of \(n=|T|\) recurring skill or behavioural classes, assigned to at most \(k\) departments or teams.
Here the hardness should transfer, making this a Class B mirror. The \(k\)-Colorability combinatorics live in the type-interaction graph, not in the number of individual agents. Moreover, because \(\omega_{ii}=0\), the objective is linear in each row \(x_i\) when all other rows are fixed. A global optimum can therefore be purified one type at a time until every type is assigned wholly to one coalition. Consequently, allowing continuous mass splitting does not improve the optimum in this natural subfamily. The reduction from Theorem 3.4 survives while the population itself has arbitrarily high multiplicity.
A second, more online-specific mirror comes from Theorem 4.10, established in this paper by adapting the argument for Theorem 3.3. It states that, for every \(k\ge2\), no deterministic online algorithm is strictly competitive for MaxFWC, even when \(W=1\) and the number of coalitions is bounded by \(k\). “Strictly competitive” means that no finite constant \(c\) guarantees \(A(I)\ge \operatorname{OPT}(I)/c\) on every input, with no additive slack.
The corresponding problem is Continuous Online Fractional-Weight Clustering. An input is a finite stream of cohorts \((t_1,b_1),\ldots,(t_q,b_q)\), where cohort \(\ell\) brings mass \(b_\ell\) of type \(t_\ell\), and the total mass is \(1\). Types again have a symmetric interaction matrix \(\omega\in\{-1,0,1\}^{T\times T}\). Upon arrival, each infinitesimal agent must irrevocably join an existing coalition or create a new one, with at most \(k\) coalitions ever allowed. Let \(x_{ir}\) be the final mass of type \(i\) in coalition \(r\), and \(s_r=\sum_i x_{ir}\). The objective is
\[ \operatorname{FW}(x) = \sum_{r:s_r>0} \frac{\sum_{i<j}\omega_{ij}x_{ir}x_{jr}}{s_r}. \]
For a finite population represented by masses \(1/N\), this is exactly the paper’s fractional weight divided by \(N\), so competitive ratios are unchanged. The offline benchmark sees the entire cohort stream and chooses the best final partition; the online algorithm does not.
I would expect the no-finite-competitive-ratio phenomenon to persist when the stream contains sufficiently many repeated cohorts. Its source is irrevocability and lack of future information, rather than the discreteness of named agents. The main open question is whether arbitrary splitting of a positive-mass cohort can defeat the paper’s adversarial pigeonhole argument when \(|T|\) is fixed. That is a substantive continuous question, not a defect in the formulation.
The weakest point is therefore the online mirror: its theorem does not transfer automatically once identical arriving agents may divide their mass among coalitions. The offline mirror is stronger. It is a clean, type-homogeneous high-multiplicity formulation of exactly the paper’s coalition-value problem, and Theorem 3.4 gives a direct reason to expect hardness to transfer. It does not cover every result in the paper—particularly the \(\Omega(\log^2 W)\) online bound—but one convincing mirror is enough.
The strongest negative case is that the online anchor depends on indivisibility, while the offline anchor survives continuization too well to defeat honestly.
For Theorem 4.10, the paper’s adversary uses an integral pigeonhole: after enough independent vertices arrive, two of \(k+1\) named vertices must occupy the same one of \(k\) coalitions. A genuine continuous population has no such implication. If type \(i\) has mass \(\mu_i\), the online algorithm can distribute it according to a vector \(p_i\in\Delta^{k-1}\). The \(k+1\) vectors \(p_i\) may all be distinct, or may give every type positive mass in every coalition. Thus the adversary’s final \(+1/-1\) vertex is not guaranteed to have zero value, and the proof of unbounded competitive ratio disappears.
One can restore the argument only by requiring an entire type-mass cohort to remain together. That makes the cohorts indivisible super-agents, so the population is no longer genuinely continuous. Alternatively, one can give every arriving mass a bespoke interaction profile, but then the construction has abandoned high multiplicity. A more sophisticated fractional adversary might still exist, but that would be a new online problem rather than a consequence of Theorem 4.10.
The offline anchor, Theorem 3.4, is much harder to reject. Its proposed mirror is a legitimate high-multiplicity blow-up: take many agents of each type, set same-type interaction to zero, and use the type-interaction matrix for cross-type edges. The objective
\[ \sum_{r=1}^{k}\sum_{i<j}\omega_{ij}x_{ir}x_{jr} \]
is linear in the mass allocation of any one type when all other allocations are fixed. Hence an optimum can be purified type by type, so the optimum is attained by assigning each type wholly to one coalition. This gives a valid continuous Type-Graph MaxWC problem, and the coloring reduction survives it.
The best objection is that this construction makes every original graph vertex its own type, chooses equal masses, and sets the diagonal to zero solely to preserve the reduction. The “continuous” population then contributes multiplicity but no substantive fractional structure. Yet that is not an admissible objection under the programme’s rules: a high-multiplicity blow-up with recurring compatibility profiles is still a sensible regime, and unchanged hardness is explicitly a valuable Class B outcome.
So the negative case can seriously challenge the online mirror, but it cannot defeat the offline one. Claiming that no worthwhile continuous mirror exists would therefore be overstated. The honest assessment is a strong continuous mirror via Theorem 3.4, with the online mirror remaining genuinely open rather than ruled out.
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.