| paper | A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation |
| authors | Redha Taguelmimt, Samir Aknine, Djamila Boukredera, Narayan Changder, Tuomas Sandholm |
| venue | AAAI 2025 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper has no numbered Theorem, Lemma, Corollary, or Proposition classifying a computational problem; its observations are structural, and the MAPF hardness claim is imported from prior work. The typed high-multiplicity LP is a sensible new research question, but it is not anchored in a qualifying result from this paper. Therefore the mandatory computational bit fails and the grade is red.
fails bit a — no named computational result to mirror
The proposed mirror imposes exchangeability, \(v(C)=w(a(C))\), and does not preserve the paper’s arbitrary characteristic-function input or SALDAE’s path-search contribution.
fatal: False
The mirror covers only the underlying CSG welfare-maximization objective in Section 2; it leaves SALDAE’s anytime search, path heuristics, conflict resolution, memory management, and empirical comparisons untouched.
The strongest honest positive case is that the paper has a good semantic mirror, but no qualifying named computational anchor.
The paper contains no numbered Theorem, Lemma, Corollary, or Proposition asserting that CSG or SALDAE is in \(P\), NP-hard, FPT, or otherwise classifying a computational problem. “Observation 1” and “Observation 2” concern reachability and path length in the coalition-structure graph, not complexity. Algorithm 1 is pseudocode, not a complexity theorem. The statement that MAPF is NP-hard is cited from Yu and LaValle, and concerns MAPF rather than this paper’s CSG problem. Thus, under the programme’s strict rule, there are zero eligible anchors.
If the paper’s formal CSG objective in Section 2 is allowed as a semantic anchor, the best mirror is:
\[ \textsc{Typed-CSG}_{\infty}. \]
An instance consists of a finite set of complete agent types \(T=\{1,\ldots,\tau\}\), a rational population-mass vector \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\), and a finite catalogue \(\mathcal K\) of admissible whole-coalition templates. A template \(k\in\mathcal K\) is an integer composition \(a^k\in\mathbb{Z}_{\ge0}^{\tau}\setminus\{0\}\), together with a rational value \(w_k\). Agents of the same type are interchangeable in every respect relevant to coalition formation: skills, location class, availability, equipment, and valuation parameters are all part of the type.
The decision variable is \(\lambda_k\ge0\), the normalized mass of complete coalitions of template \(k\). It is not fractional membership inside a coalition: an atom of \(\lambda_k\) represents an entire coalition with composition \(a^k\). The problem is
\[ \max_{\lambda\ge0}\ \sum_{k\in\mathcal K}w_k\lambda_k \]
subject to
\[ \sum_{k\in\mathcal K}a^k_t\lambda_k=\mu_t \qquad\text{for every }t\in T. \]
A solution is an optimal rational vector \(\lambda\), or a certificate of infeasibility.
This is a natural high-multiplicity version of the paper’s CSG problem. For \(N\) finite agents with \(N\mu_t\in\mathbb Z\), an ordinary typed coalition structure uses integer counts \(x_k\) satisfying
\[ \sum_k a^k_t x_k=N\mu_t. \]
Setting \(\lambda_k=x_k/N\) gives the continuous solution. Conversely, rational \(\lambda\) can be scaled to an integer clone population. Thus the mirror has a genuine high-multiplicity bridge, provided coalition values depend on type composition rather than on named-agent identity.
The most convincing regime is a large disaster-response or electric-vehicle population with repeated role types: for example, thousands of responders or vehicles but only a few dozen complete skill/location/equipment profiles. The paper itself emphasizes hundreds and thousands of agents and includes disaster-response and electric-vehicle benchmarks. The continuous version makes that advertised large-scale setting mathematically explicit: \(N\) is very large while \(\tau\ll N\).
For an explicit catalogue \(\mathcal K\), this is Class A immediately: it is a linear program. The more interesting version gives \(\mathcal K\) implicitly through a type-composition rule. Then the LP has potentially exponentially many columns, and its pricing problem is
\[ \max_{k\in\mathcal K}\left(w_k-y\cdot a^k\right), \]
for dual prices \(y\). This directly exposes the computational issue hidden by the paper’s search over individual coalition structures. Structured composition values may give polynomial pricing and hence a polynomial-time continuous algorithm; arbitrary succinct values may preserve hardness. The natural follow-up questions are whether common disaster-response and vehicle-allocation valuations admit efficient pricing, when continuous optima can be rounded with bounded loss, and when the LP is integral for finite clone populations.
The authors would probably recognize this as their CSG optimization problem under an anonymity assumption. They would not necessarily recognize it as a continuization of SALDAE itself: SALDAE’s path heuristics, conflict resolution, memory lists, and empirical anytime performance are not preserved. The mirror covers only the underlying welfare-maximization problem in Section 2, not the claimed superiority of SALDAE.
The weakest point is therefore decisive for the rubric: the paper never proves a named computational result to anchor. Moreover, collapsing arbitrary characteristic functions \(v(C)\) to composition values \(w_k\) adds a substantive exchangeability assumption, and allowing coalition mass can remove some finite-agent integrality effects. So this is a credible continuous research problem inspired by the paper, probably tractable in useful structured regimes, but strictly speaking it is a no-anchor case rather than a formally anchor-compliant positive mirror.
On the programme’s strict admissibility rule, there are no eligible anchors. This paper formulates CSG and presents SALDAE, but it does not state a numbered theorem, lemma, corollary, or proposition classifying the complexity of either. Observations 1 and 2 concern reachability and path length in the coalition-structure graph, not computational complexity. Algorithm 1 is pseudocode without a proved running-time, approximation, or optimality theorem. The NP-hardness statement belongs to MAPF and is cited from other work. The empirical claims about solution quality and gain rate are not named computational results. Thus any continuous CSG question is a new research problem inspired by the paper, not a mirror of one of its results.
Even granting the proponent’s semantic anchor, \( \textsc{Typed-CSG}_{\infty} \) does not preserve what this paper contributes. The paper’s formal input is an arbitrary characteristic function \(v(C)\) over individual coalitions. To obtain the proposed model, one must impose \(v(C)=w(a(C))\), where value depends only on type composition. That is a substantial exchangeability assumption. If arbitrary interactions are retained, a complete type must encode an agent’s entire coalition-interaction profile, and the number of types can grow with the population. Then there is no useful high-multiplicity compression. If exchangeability is imposed, the resulting problem is sensible, but it is a different valuation model rather than a continuization of SALDAE’s stated problem.
The proposed LP is also best understood as a standard high-multiplicity configuration or set-partitioning formulation. With an explicit catalogue \( \mathcal K \), it is simply an LP whose columns are supplied in the input. With an implicit catalogue, its central question is the pricing problem
\[ \max_{k\in\mathcal K}\bigl(w_k-y\cdot a^k\bigr). \]
That could certainly be worthwhile in its own right. But the paper supplies no structure on \(w\), no pricing theorem, and no computational claim suggesting that this is the relevant hidden bottleneck. One would be inventing a new valuation language and then asking whether that language has tractable pricing. I am not objecting that the answer might be tractability; that would be a valuable result. The objection is that the proposed question is not anchored in the paper’s result, because the paper has no such result.
The bridge to finite CSG is only asymptotic as well. A rational \( \lambda \) can be scaled to an integer population, but generally not to the particular finite population from which \( \mu \) was obtained. The continuous object therefore convexifies counts of whole coalition templates. That is a legitimate high-multiplicity relaxation, but it is not the coalition-structure graph explored by SALDAE. In that graph, a split or merge changes one indivisible coalition. Under normalization, such a move changes vanishing mass as the population grows; if positive mass is allowed to split at once, the adjacency relation and path length must be newly defined. The paper’s path-search, bridging paths, conflict resolution, and memory heuristics have no canonical continuum limit.
Nor can SALDAE’s empirical claims be mirrored by \( \mu \). An anytime quality curve would additionally require a distribution over valuation functions, a search-time model, memory limits, parallelism, random seeds, and an incumbent-quality metric. Two populations with the same \( \mu \) can induce entirely different distributions of coalition values. A continuum of coalition participants therefore does not produce a meaningful analogue of SALDAE’s reported success rates or gain rates.
The repeated-role disaster-response scenario is the strongest point for the positive case, and it should not be dismissed: it makes a high-multiplicity CSG problem plausible. But it supports an independent configuration-LP research programme, not a continuous mirror of this paper’s named contributions. The negative case is therefore decisive under the programme’s strict anchor rule and strong as a paper-specific objection. It is not an airtight universal claim about CSG: if semantic anchors are allowed, the role-based high-multiplicity model is genuinely sensible, and its failure is one of attribution and fit rather than of mathematical legitimacy.
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.