| paper | Hedonic Games with Fixed-Size Coalitions |
| authors | Vittorio Bilò, Gianpiero Monaco, Luca Moscardelli |
| venue | AAAI 2022 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 12
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), rational capacities \(\beta_1,\beta_2>0\) summing to \(1\), and a symmetric matrix \(A\in\{0,1\}^{|T|\times|T|}\), find \(x_{ti}\ge0\) with \(\sum_i x_{ti}=\mu_t\) and \(\sum_t x_{ti}=\beta_i\) maximizing \(\operatorname{SW}_\infty(x)=\sum_{i=1}^{2}\sum_{t,u\in T}a_{tu}x_{ti}x_{ui}\), or decide whether the optimum is at least a rational threshold \(q\).
A high-multiplicity symmetric hedonic game in which types carry masses \(\mu\), types may be split fractionally across fixed-capacity coalitions, \(A\) gives pairwise additive affinities, and \(x\) maximizes normalized utilitarian welfare.
It directly mirrors Theorem 12 and the \(k=2\), simple-game version of \( extsc{SOCIAL\ OPTIMUM}\); it leaves the PLS stability results, price bounds, existence results, and broader approximation theorems untouched.
The strongest honest case is a high-multiplicity, type-block version of the paper’s \( \textsc{Social Optimum} \) problem. My lead anchor is Theorem 12, proved in this paper: \( \textsc{Social Optimum} \) is NP-hard even for simple games with \(k=2\).
Call the continuous problem \( \textsc{Role\text{-}Block\ Social\ Optimum}_{\infty} \). An instance consists of a finite set of agent types \(T=\{1,\ldots,\tau\}\), rational masses \(\mu_t\) summing to \(1\), two or more rational coalition capacities \(\beta_1,\ldots,\beta_k\) summing to \(1\), and a symmetric rational affinity matrix \(A=(a_{tu})\). In the simple subclass, \(a_{tu}\in\{0,1\}\). A type completely specifies an agent’s additive contribution to every other type: an agent of type \(t\) receives contribution \(a_{tu}\) from each member of type \(u\) in her coalition.
The decision variable is a mass assignment \(x=(x_{ti})\), where \(x_{ti}\) is the mass of type \(t\) placed in coalition \(i\). It must satisfy
\[ x_{ti}\ge 0,\qquad \sum_i x_{ti}=\mu_t,\qquad \sum_t x_{ti}=\beta_i. \]
The utility of type \(t\) in coalition \(i\) is
\[ u_t(i;x)=\sum_{u\in T}a_{tu}x_{ui}, \]
and the continuous utilitarian welfare is
\[ \operatorname{SW}_{\infty}(x) = \sum_{i=1}^k\sum_{t,u\in T}a_{tu}x_{ti}x_{ui}. \]
The problem asks for a feasible \(x\) maximizing this quantity. Its decision form asks whether \(\operatorname{SW}_{\infty}(x)\ge q\) is achievable for a given rational threshold \(q\); an approximation form asks for an \(x\) within a prescribed additive error of the optimum.
This is not merely replacing an integer by a real number. Take rational masses \(\mu_t=n_t/N\), create \(n_t\) agents of each type, and connect every pair of type-\(t\) and type-\(u\) agents according to \(a_{tu}\). A rational mass assignment \(x\) lifts to assigning \(Nx_{ti}\) clone agents of type \(t\) to coalition \(i\). After normalizing welfare by \(N^2\), the finite games converge to the displayed quadratic objective; the missing self-pair correction is \(O(1/N)\). Conversely, every finite high-multiplicity assignment induces such an \(x\).
A convincing regime is large-scale project-team formation or office allocation: tens or hundreds of thousands of employees, but only a modest number of recurring role profiles, with compatibility determined by role pairs and teams having fixed proportional capacities. Thus \(N\gg \tau\), while the fixed-size-coalition structure remains exactly the one studied in the paper. The authors should recognize this as the type-quotient or complete blow-up of their symmetric additively separable hedonic game, not as a different welfare concept.
I would expect \( \textsc{Role\text{-}Block\ Social Optimum}_{\infty} \) to be Class C, although this is precisely an open problem rather than a claim already proved by Theorem 12. For \(k=2\), the objective is a nonconvex quadratic function over a transportation polytope. Splitting a type across coalitions can destroy the discrete bisection reduction, so Theorem 12’s NP-hardness does not automatically transfer. But the mass model retains the difficult interaction structure: it is a balanced quadratic clustering problem, not a linear averaging problem. The key question is whether that structure admits a polynomial optimization or separation method, or whether the continuous quadratic problem remains hard for reasons specific to the continuum relaxation.
The main follow-up questions are whether hardness survives for \(k=2\) and \(a_{tu}\in\{0,1\}\), whether it survives with bounded \(\tau\), whether rational optima can be rounded to finite clone assignments with controlled welfare loss, and whether special matrices \(A\) yield flow, min-cut, or convex formulations.
A worthwhile secondary anchor is Theorem 2, also proved in this paper: \( \textsc{Stable} \) is PLS-complete for each of SSS, SS, and SSTU, using a reinterpretation of the cited MAX-CUT local-search reduction. The corresponding continuous problem, \( \textsc{Stable}_{\infty}^{X} \), uses the same \(x\), \(A\), \(\mu\), and \(\beta\), and asks for a feasible assignment with no improving infinitesimal swap. Concretely, for types \(t,u\) occupying coalitions \(i\neq j\), a swap exchanges an infinitesimal mass of \(t\) and \(u\). For strict swap stability, it is forbidden that
\[ u_t(j;x)>u_t(i;x) \quad\text{and}\quad u_u(i;x)>u_u(j;x). \]
For ordinary swap stability, replace the second inequality by \( \ge \); for transferable utilities, forbid
\[ u_t(j;x)+u_u(i;x) > u_t(i;x)+u_u(j;x). \]
A solution is any feasible mass assignment satisfying the chosen condition. I would again expect continuum-specific difficulty, but not literal PLS-hardness transfer: the finite paper has discrete improving swaps and an integer potential increase, whereas the continuum has infinitesimal exchanges and a real-valued quadratic potential. Determining whether a stable mass assignment can be computed efficiently is therefore a genuine new computational question closely tied to Theorem 2.
The weakest point is clear: Theorem 12’s reduction uses arbitrary individual graphs, while the high-multiplicity mirror restricts attention to graphs with many interchangeable agents and block-constant interactions. Fractionally splitting a type may also eliminate the original bisection gap. Thus I would not claim that the paper has already established hardness for the mirror. The positive case is instead that the mirror is faithful, natural, and mathematically nontrivial: it preserves the paper’s exact coalition capacities, symmetric additive utilities, swap deviations, and welfare objective, while exposing whether the paper’s discrete hardness survives, disappears, or is replaced by a new continuum-specific obstruction.
The strongest negative case is against the proposed \( \textsc{Stable}_\infty \) anchor. In the continuous model, the discrete PLS phenomenon largely disappears.
Let \(d_t=\sum_u a_{tu}\mu_u\) and assign each type proportionally across coalitions:
\[
x_{ti}=\beta_i\mu_t.
\]
Then a type-\(t\) agent in coalition \(i\) has utility \(u_t(i)=\beta_i d_t\). If type \(t\) in \(i\) swaps with type \(u\) in \(j\), the two utility changes are
\[
(\beta_j-\beta_i)d_t
\quad\text{and}\quad
(\beta_i-\beta_j)d_u.
\]
They have opposite signs. Consequently this assignment is strictly swap stable for every nonnegative symmetric affinity matrix, every coalition-size vector, and every instance. It is produced immediately from \(\mu\) and \(\beta\). If all \(d_t>0\), it is also swap stable in the paper’s weak sense. Thus the continuous analogue of the paper’s \( \textsc{PLS} \)-complete STABLE problem is trivial for at least one of its three central stability notions, and often for two.
This is a genuine continuum degeneration: allowing each type to be divided fractionally lets every coalition have the same type composition, eliminating mutually beneficial strict exchanges. Preventing that by requiring whole type blocks to remain together restores a discrete assignment problem, not a continuous society. Normalising utilities by coalition size would restore the same-composition equilibrium for unequal capacities, but that changes the paper’s utility model. Transferable-utility stability is the only plausible rescue, and it becomes a new nonconvex local-optimum problem whose connection to the paper’s PLS reduction is not established.
The lead anchor, Theorem 12, is harder to defeat. Its hardness is built on an arbitrary individual graph. Under the programme’s exact notion of type, a high-multiplicity type-block instance requires every clone of a type to have the same relation to every other type. Hence the graph must be a complete blow-up of a quotient graph. The proposed objective
\[
\sum_i x_i^\top A x_i
\]
is mathematically legitimate, but it is a fractional balanced quadratic-clustering problem, not simply the paper’s arbitrary-graph SOCIAL OPTIMUM problem with more agents. Theorem 12 supplies neither a reduction nor a hardness gap for this relaxation.
The most favorable repair is to duplicate every vertex of an arbitrary hard graph many times. That does create high multiplicity, but the entire interaction structure remains in the quotient matrix \(A\); the additional population disappears in the limit. The resulting problem may be interesting, but it is an independent continuous quadratic optimisation problem rather than a consequence of the paper’s theorem. A role-based team-formation interpretation makes it sensible, but also confirms that the paper has been replaced by a new structured model.
So the negative case is decisive against Theorem 2 as a faithful anchor, but not against Theorem 12. I cannot honestly claim a universal “no scenario” verdict: the role-block social-welfare problem is a defensible high-multiplicity mirror. The strongest criticism is that the proponent should present it as a new open quadratic problem, not as a computational continuation already motivated by the paper’s NP-hardness 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.