| paper | Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size |
| authors | Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos |
| 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 | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to one, symmetric pair utilities \(w_{tu}\), and coalition capacity \(C\), choose nonnegative densities \(y_q\) for every integer type composition \(q\) with \(1 \le |q| \le C\), satisfying \(\sum_q q_t y_q = \mu_t\), to maximize \(\sum_q v(q)y_q\), where \(v(q) = \sum_{t<u} w_{tu} q_t q_u + \sum_t w_{tt} \binom{q_t}{2}\); decide whether the optimum is at least a rational threshold \(B\).
A high-multiplicity additive hedonic coalition model: types are complete compatibility profiles, \(\mu\) gives population mass, \(q\) gives an integer team composition, \(y_q\) gives team density, and welfare is total normalized pair utility. The natural structural extension uses a vertex cover of the type-interaction graph, not the paper's individual-agent vertex cover.
The fixed-C configuration LP is tractable without the paper's matching argument, and a type-interaction vertex cover is not the individual-agent vertex cover of Theorem 3, so the theorem-level parameterized transfer remains unestablished.
fatal: False
The mirror covers weighted bounded-coalition welfare maximization and a fixed-C analogue of Theorem 3; it leaves the unweighted hardness and FPT results, ETH lower bound, kernel results, and other structural-parameter theorems untreated.
There is a credible, though deliberately limited, continuous mirror here. The strongest anchor is the paper’s proved Theorem 3:
“\(C\)-\(CF_w\) can be solved in time \(vc^{O(vc)}n^{O(1)}\).”
The theorem is proved in this paper, using a vertex-cover decomposition and a reduction to maximum-weight matching.
The mirror I would propose is Mass-\(C\)-\(CF_w\). A type is a complete compatibility profile: two agents of type \(t\) have the same utility toward every type \(u\), and the same within-type utility. The instance consists of:
A coalition configuration is an integer vector \(q\in\mathbb Z_{\ge0}^{T}\) with \(1\le |q|\le C\). Its welfare is
\[ v(q)= \sum_{t<u}w_{tu}q_tq_u+ \sum_t w_{tt}\binom{q_t}{2}. \]
The solution chooses a nonnegative mass \(y_q\) of coalitions of each configuration, subject to
\[ \sum_q q_t y_q=\mu_t \qquad\text{for every type }t, \]
and maximizes
\[ \sum_q v(q)y_q. \]
The decision version asks whether the optimum is at least \(B\). The \(y_q\)'s are densities of teams per unit population; agents are not fractionally split inside a team, but the population contains a divisible mass of teams of each integer composition.
This is a genuine high-multiplicity version of the paper’s problem. If \(\mu_t=n_t/N\) is rational, clearing denominators gives \(n_t\) ordinary agents of type \(t\). If the optimal \(y_q\) is rational, clearing its denominators gives an ordinary finite partition with exactly the same normalized welfare. Thus the continuous problem is not merely “weighted coalition formation”; it is the rational-clone limit of \(C\)-\(CF_w\).
The regime is plausible in exactly the settings the paper mentions: large firms forming project teams, recurring training cohorts, or large pools of wireless/task-allocation agents. There may be \(10^4\)–\(10^6\) agents but only a few dozen role or compatibility types. For example, agents may be classified by skill, schedule, location, and collaboration profile. The high-multiplicity assumption is that agents with the same complete profile are interchangeable; it does not require every named agent to have identical preferences.
I would expect this mirror to be Class A at least for fixed \(C\). There are only
\[ \binom{\tau+C}{C} \]
coalition configurations, so the problem is an ordinary rational LP of polynomial size for every fixed team capacity. More interestingly, suppose the type-compatibility graph has a vertex cover \(K\) of size \(k\). Types outside \(K\) have no mutual utility, so once the configurations of the \(K\)-types are fixed, assigning peripheral mass to the remaining team slots is a transportation or matching LP. Enumerating the possible core compositions gives an algorithm fixed-parameter in \(k+C\), with polynomial dependence on \(\tau\) and the encoding length.
That is the continuous analogue of the structural idea behind Theorem 3: a small interaction core controls all valuable pairings, while the large independent remainder can be handled by matching. It also exposes a useful boundary. For unrestricted \(C\), the LP has exponentially many configurations, and its pricing problem becomes
\[ \max_{|q|\le C} \left(v(q)-\sum_t p_tq_t\right), \]
which is a quadratic optimization problem over team compositions. Hardness may then survive through the type-interaction graph rather than through population multiplicity. So the expected classification is:
The mirror is author-recognizable: it preserves the bounded coalition size, pairwise additive utilities, graph-derived compatibility, and utilitarian welfare objective. It does not replace coalitions by fractional bundles or change the welfare criterion. It only replaces a large multiplicity of interchangeable agents by rational masses and replaces integer counts of repeated team configurations by their high-multiplicity LP limit.
The weakest point is precisely the parameter transfer. The paper’s \(vc\) is the vertex-cover number of an individual-agent graph. In the proposed mirror, a small vertex cover of the type graph may expand to many interacting agents, so the paper’s exact \(vc^{O(vc)}n^{O(1)}\) theorem does not automatically apply. I would therefore present the configuration LP and its fixed-\(C\) tractability as the firm part of the case, and the role-level vertex-cover extension as the research question generated by Theorem 3—not as an already-established consequence.
I would not add the paper’s hardness and kernel theorems as positive anchors: their transfer under fractional team densities is genuinely uncertain. This one anchor is enough because it already gives a natural continuous population problem, a credible high-multiplicity regime, a concrete LP, and a nontrivial tractability boundary.
The strongest negative case is that the proponent’s construction does not actually mirror Theorem 3. It replaces the paper’s parameter by a new type-level parameter and obtains a generic high-multiplicity configuration LP.
Theorem 3 exploits a small vertex cover of the *individual-agent graph*. That structure disappears under any nondegenerate cloning limit. If types \(t\) and \(u\), both of positive mass, have positive interaction, their clones form a complete bipartite graph. Every vertex cover must then contain all agents of one side, so its size is \(\Omega(N)\). A small vertex cover of the type graph therefore does not induce a small vertex cover in the paper’s graph.
Conversely, preserving \(vc=O(1)\) forces the interacting core to contain only \(O(1)\) named agents. With fixed \(C\) and fixed type-level weights, those agents can participate in only \(O(C)\) valuable pairs. After normalizing welfare by population size, the entire objective tends to zero. Thus the parameter regime that makes Theorem 3 interesting either explodes under continuization or degenerates into a zero-welfare limit.
The proposed LP is nevertheless mathematically valid. For fixed \(C\), enumerating all type compositions and optimizing coalition densities is a standard high-multiplicity relaxation, and denominator clearing gives the expected finite cloned instance. But that observation is independent of Theorem 3 and does not use its matching argument. It would apply to essentially any bounded-size additive packing problem. The fixed-\(C\) tractability is also obtained simply by making the number of configurations \(\binom{\tau+C}{C}\) polynomial; it does not reveal what the paper’s vertex-cover theorem becomes in the continuum.
The suggested repair—using a vertex cover of the type-interaction graph—is a plausible and perhaps worthwhile new problem. But it is not a parameter-preserving mirror: it changes individual vertex cover into a role-level parameter and changes the question from “does the paper’s sparse-core algorithm survive high multiplicity?” to “what can be done for a new finite-type configuration LP?” The possible \(k+C\)-parameter algorithm is consequently evidence for a related research direction, not for a continuous counterpart of the paper’s main result.
Still, this negative case cannot honestly establish the universal claim requested. Large pools of interchangeable role types—project teams, training cohorts, or recurring task-allocation populations—are plausible high-multiplicity societies, and the configuration LP preserves the paper’s capacity, pairwise utilities, and welfare objective. Nor can existing fractional hedonic-game work be invoked as a continuous collision, since it concerns outcome utilities rather than a continuous population.
So the anchor is weakened as a mirror of Theorem 3, but it is not defeated as a legitimate continuous problem. The honest verdict is that the universal negative case is weak: this paper does support at least one credible continuous mirror, even if the proponent overstates its connection to the stated vertex-cover theorem.
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.