| paper | Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search |
| authors | Redha Taguelmimt, Samir Aknine, Djamila Boukredera, Narayan Changder, Tuomas Sandholm |
| venue | IJCAI 2024 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given \( \tau \) exchangeable types, rational population proportions \( \mu\in\mathbb{Q}_+^\tau \) with \( \sum_t\mu_t=1 \), and a finite catalogue of anonymous coalition templates \( (q^k,w_k) \) with \( q^k\in\mathbb{Z}_+^\tau \), find \( \lambda_k\ge0 \) maximizing \( \sum_k w_k\lambda_k \) subject to \( \sum_k q^k_t\lambda_k=\mu_t \) for every type \(t\).
A typed high-multiplicity configuration LP: \( \mu \) is population supply, \(q^k\) is a coalition’s type-count template, \( \lambda_k \) is coalition density, and \(w_k\) is value per coalition; implicit templates lead to pricing over \( w(q)-\pi\cdot q \).
The paper does not specify type-invariant valuations, fixed template sizes, per-capita welfare scaling, or an implicit representation for \(w\), so the mirror’s computational boundary is supplied by additional modelling choices.
fatal: False
The mirror covers the exact typed CSG optimization content behind Theorem 3, but not SMART’s CDP, GRAD, or DIPS machinery, Theorem 1, Lemma 1, Theorem 2, runtime analysis, or empirical comparisons.
The strongest positive case is a deliberately narrow one: coalition structure generation in a genuinely high-multiplicity environment. My lead anchor is Theorem 3, proved in this paper: “The SMART algorithm always finds the optimal solution.” It is the right anchor because it concerns the semantic core of the paper—exact maximization of additive welfare over exhaustive partitions—not merely the empirical speed claims. I would not anchor on Theorem 2: its comparison with ODP-IP, ODSS, and BOSS is tied to this particular \(n\)-agent implementation.
The mirror is Continuous High-Multiplicity Coalition Structure Generation, \( \mathrm{CCSG}_\infty \).
There are \( \tau \) agent types and a population-mass vector \( \mu\in\mathbb{Q}_+^\tau \) with \( \sum_t\mu_t=1 \). A type includes every attribute relevant to coalition formation: capacity, location, availability, sensor quality, cost, and so on. Thus agents of one type are exchangeable. A plausible regime is a logistics or sensor network with thousands or millions of interchangeable units but only a few dozen capability-location classes, so \(N\gg\tau\).
A coalition profile is a vector \(q\in\mathbb{Q}_+^\tau\), where \(q_t\) is the mass of type \(t\) placed in one coalition. Let the input contain a finite catalogue
\[ \mathcal K=\{(q^1,w_1),\ldots,(q^r,w_r)\}, \]
where \(w_k\) is the value of a coalition with profile \(q^k\). The values may contain arbitrary complementarities; they need not be additive across types. The catalogue can represent, for example, all operationally meaningful compositions of a delivery team or sensor coalition.
The decision variable is \( \lambda_k\in\mathbb{R}_+ \), the number-density of coalitions of profile \(q^k\). The problem is
\[ \max_{\lambda\ge 0}\ \sum_{k=1}^r w_k\lambda_k \]
subject to
\[ \sum_{k=1}^r q^k_t\lambda_k=\mu_t \qquad\text{for every }t\in\{1,\ldots,\tau\}. \]
A solution is an optimal vector \( \lambda^\star \). The equalities say that every unit of population mass belongs to exactly one coalition, and the objective is precisely the continuous analogue of the paper’s
\[ V(CS)=\sum_{C\in CS}v(C). \]
This is not merely fractionalizing an outcome. The society itself is the continuous object: \( \mu_t \) is the fraction of the population of type \(t\). The coalition structure is a measure over coalition compositions.
The high-multiplicity bridge is direct. For a discrete population of \(N\) agents, take \(N\mu_t\) agents of type \(t\), require \(Nq^k_t\) to be integral, and require \( \lambda_k\in\mathbb{Z}_+ \). Then the constraints describe an ordinary typed coalition partition. Releasing integrality gives \( \mathrm{CCSG}_\infty \). The only semantic change is exactly the one high multiplicity requires: agents with the same complete type description become indistinguishable.
The stated finite-catalogue problem is Class A: it is a linear program. The more interesting version makes \( \mathcal K \) implicit, containing all feasible coalition compositions. Its dual is
\[ \min_{\pi\in\mathbb{R}^\tau}\ \pi\cdot\mu \]
subject to
\[ \pi\cdot q^k\ge w_k \qquad\text{for every coalition profile }q^k. \]
Thus its pricing problem is to maximize \(w(q)-\pi\cdot q\) over coalition profiles. This is exactly the kind of configuration-LP/column-generation question that the continuous programme is meant to expose. For structured coalition values—capacity constraints, separable costs, or piecewise-linear complementarities—I would expect tractable pricing and hence a Class A result. For succinct arbitrary values, continuum-specific hardness remains a legitimate possibility.
The authors should recognise this as their problem rather than as a softened surrogate. It preserves exhaustive coalition formation, arbitrary coalition synergies, additive welfare across coalitions, and exact optimization. What disappears is only the irrelevant identity of agents within a type. The integer partition graph is an algorithmic organization of the discrete search space; it is not the definition of CSG. In the mirror, its role is taken by the space of coalition-composition columns and their pricing problem.
The further questions are substantial: which composition-based valuation classes admit polynomial pricing; how many types are needed before hardness returns; can an optimal continuous solution be rounded to an \(N\)-agent coalition structure with controlled additive loss; and is there a continuous counterpart of SMART’s offline coalition-selection phase?
The weakest point is that the paper permits a completely arbitrary characteristic function \(v(C)\) on named subsets. Such a function need not have any meaningful type-invariant limit. Moreover, real-valued coalition counts and arbitrarily divisible coalition profiles can erase indivisibility effects, especially fixed coalition-formation costs. I would therefore not claim that every CSG instance has a useful mirror. The positive claim is narrower: in fleet, sensor, or other cohort-based settings where coalition value depends on type composition and scales sensibly with mass, \( \mathrm{CCSG}_\infty \) is a faithful high-multiplicity form of the exact problem anchored by Theorem 3, and it opens a genuine continuous-optimization and pricing landscape.
The strongest case against the proposed mirror is that Theorem 3 is a completeness theorem for a particular discrete search procedure, not a complexity theorem for coalition formation. “SMART always finds an optimum” is proved by covering the integer-partition graph of named-agent coalition structures. In the proposed finite-catalogue model, optimality follows immediately from linear programming duality. That is a new configuration problem, not a continuization of the theorem’s computational content.
The direct high-multiplicity quotient also fails for the paper’s stated input model. The characteristic function \(v\) is arbitrary on named subsets. If two agents share a type, a type-composition value \(w(q)\) requires that replacing one by the other never change a coalition’s value. The paper assumes nothing of the sort. A value function could distinguish \(v(\{a_i,b\})\) from \(v(\{a_j,b\})\) even when \(a_i\) and \(a_j\) have identical individual attributes. To preserve that information, one must refine types until \(\tau\) is essentially the number of agents, or encode coalition-specific history into the type. Either repair destroys the intended high-multiplicity compression.
The proponent’s stronger construction avoids this by imposing an anonymous valuation \(w(q)\). That is coherent, but it restricts the primitive problem to composition-invariant coalition games. It is therefore an extension, not a rational-clone reformulation of the paper’s arbitrary-\(v\) CSG problem. The distinction matters particularly for scaling. In ordinary applications, coalitions are fixed-size teams. With \(N\) agents, a team profile is an integer vector \(k\), or normalized \(q=k/N\), which tends to zero as \(N\) grows. A fixed catalogue of positive-mass profiles instead describes macroscopic coalitions containing \(\Theta(N)\) agents. Moving between these regimes requires new assumptions about coalition value scaling and welfare normalization.
There is also a basic dichotomy. If coalition templates remain integral, the faithful high-multiplicity model is an integer configuration problem over typed team profiles. If \(\lambda\) is allowed to be arbitrary real-valued, the model convexifies the number of coalitions and their profiles. The latter may be useful, but the continuous gain then comes from fractionalizing the coalition-structure outcome, not simply from making the population continuous. That is outside the programme’s stated scope and changes the feasible-object semantics that Theorem 3 certifies.
The implicit-catalogue version does not repair the attribution problem. With an explicit catalogue, the problem is an ordinary LP whose columns have already been supplied. With an implicit catalogue, complexity depends entirely on a newly specified representation or oracle for \(w(q)\). Under arbitrary composition values, pricing can encode unrestricted search; under structured values, tractability is a theorem about that added valuation class, not a consequence of SMART. The paper supplies no such pricing structure.
This is a serious objection to calling the construction a mirror of Theorem 3, and it defeats the claimed direct connection to SMART’s result. It does not, however, establish the universal negative honestly. A bounded-team logistics or sensor setting with anonymous type-composition values and scaled welfare is plausible and could support a worthwhile configuration-LP research programme. Under a permissive “author-recognizable extension” standard, the proponent’s anchor probably survives; under a strict mirror standard, it is at most a new typed configuration problem rather than a continuous mirror of this paper.
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.