| paper | Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation |
| authors | V. Bilò, Angelo Fanelli, M. Flammini, G. Monaco, Luca Moscardelli |
| venue | JAIR 2018 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even for symmetric \(\{0,1\}\)-valued weights with zero diagonal and strictly positive rational masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given rational type masses \mu with \sum_t \mu_t=1, a symmetric nonnegative rational compatibility matrix \(W\), and a threshold \(B\), decide whether there are finitely many positive-mass coalitions \(x^1,…,x^K\in\mathbb{R}_{\ge0}^{\tau}\), with \sum_k x_t^k=\mu_t, such that, for \(q_k=\sum_t x_t^k\), every type used in coalition \(k\) weakly prefers \(k\) to every occupied coalition \ell\), meaning \sum_r w_{tr}x_r^k/q_k \ge \sum_r w_{tr}x_r^\ell/q_\ell, and \sum_{k,t,r}w_{tr}x_t^kx_r^k/q_k\ge B\).
A nonatomic high-multiplicity fractional hedonic game with type masses \mu, compatibility matrix \(W\), coalition mass vectors \(x^k\), welfare \sum_k (x^k)^\top W x^k/q_k, and Wardrop-style Nash stability.
Passing from finite agents to nonatomic mass changes denominator-changing unilateral deviations into Wardrop-style infinitesimal deviations, so Theorem 14's Exact 3-Cover reduction and NP-hardness do not carry over.
fatal: False
It covers the \textsc{COMPUTE BEST STABLE} clause of Theorem 14; it leaves the \textsc{COMPUTE OPT} clause and the paper's existence, efficiency, dynamics, and topology-specific results unaddressed.
The strongest positive case is a high-multiplicity version of the paper’s general-graph welfare problem, anchored in Theorem 14, proved in this paper (Appendix D).
Theorem 14 states that both named problems
\[ \textsc{COMPUTE BEST STABLE}(\mathcal G(G)) \]
and
\[ \textsc{COMPUTE OPT}(\mathcal G(G)) \]
are NP-hard. The first asks for a Nash-stable coalition structure of maximum social welfare; the second asks for a maximum-welfare coalition structure without requiring stability. The reduction is from Exact 3-Cover and works even for connected, unweighted graphs. In particular, an exact cover exists precisely when the constructed game reaches the threshold \(\frac{19}{5}p+3(m-p)\), and in that case a Nash-stable coalition structure reaches it as well.
I would use the first clause as the lead anchor.
Call the continuous problem \(\textsc{Best-Stable-FHG}_{\infty}\). An instance consists of:
A type is a complete compatibility profile: agents of type \(t\) have identical values for every other type. The population is nonatomic, but each infinitesimal agent still belongs integrally to one coalition.
A coalition structure is represented by finitely many positive-mass coalitions \(x^1,\ldots,x^K\), where \(x^k_t\) is the mass of type \(t\) in coalition \(k\), and
\[ \sum_{k=1}^{K}x^k_t=\mu_t \]
for every type \(t\). We may take \(K\le \tau+1\) after the usual finite-support reduction; alternatively, one can formulate the same object as a measurable partition of the population.
Let
\[ q_k=\sum_{t\in T}x^k_t \]
be the mass of coalition \(k\). The utility of a type-\(t\) agent in coalition \(k\) is
\[ u_t(k;x)=\frac{\sum_{r\in T}w_{tr}x^k_r}{q_k}. \]
This is exactly the paper’s average-value utility with integer coalition sizes replaced by coalition masses. The social welfare is
\[ \operatorname{SW}(x) = \sum_{k=1}^{K} \frac{\sum_{t,r\in T}w_{tr}x^k_tx^k_r}{q_k}. \]
The mass assignment \(x\) is Nash stable if every type receiving positive mass in coalition \(k\) weakly prefers \(k\) to every other occupied coalition:
\[ x^k_t>0 \quad\Longrightarrow\quad u_t(k;x)\ge u_t(\ell;x) \]
for every occupied coalition \(\ell\), with an empty coalition providing the paper’s outside option of utility \(0\). Ties may split a type across several coalitions. The problem asks for a Nash-stable \(x\) maximizing \(\operatorname{SW}(x)\), or, equivalently, whether some stable \(x\) has welfare at least \(B\).
This is not merely fractionalizing the outcome. The society itself has become continuous: \(\mu_t\) is a population fraction, and \(x^k_t\) is the mass of a type assigned to a coalition. The objective, average utility, unilateral deviations, and Nash-stability requirement remain the paper’s underlying questions.
A convincing regime is a large population of residents, workers, students, or market participants who form groups, with only a moderate number of compatibility profiles. For example, there may be millions of agents but only a few dozen or few hundred types determined by role, preferences, or publicly relevant social characteristics. Every member of a type has the same compatibility profile, so this is genuine high multiplicity rather than an arbitrary declaration that named individuals are interchangeable. The original graph becomes a type-level compatibility graph whose edges are repeated across the population.
The authors should recognise this as their problem. Their utility is still the average value of coalition members; their decision is still a partition into coalitions; their stability notion is still unilateral deviation; and their objective is still total social welfare. The only change is that repeated agents are represented by mass rather than by separate names. Indeed, the paper’s own use of coalition sizes and average utilities makes this limit particularly natural.
I would expect \(\textsc{Best-Stable-FHG}_{\infty}\) to be a candidate Class C problem: potentially hard for continuum-specific reasons. I would not claim that Theorem 14’s NP-hardness automatically transfers. Its Exact 3-Cover reduction relies on indivisible element vertices. In the continuous model, the mass of an element type could split between several set-types, turning exact cover into a fractional-cover question. Thus the reduction’s hardness is not plainly population-independent.
Nevertheless, the continuous problem remains nontrivial. Stability imposes support conditions of the form “every type used in a coalition must regard that coalition’s composition as utility-maximising,” while welfare is a nonconvex sum of quadratic-over-linear terms,
\[ \frac{x^{k\mathsf T}Wx^k}{\mathbf 1^{\mathsf T}x^k}. \]
The difficulty may therefore survive in the arrangement of type masses across coalition compositions, even when each type is replicated arbitrarily many times. A proof of tractability would be valuable; a proof of hardness would be an especially clean example of continuum-specific hardness.
The weakest point is that a typed blow-up is not the same graph as the paper’s arbitrary individual-level graph. In particular, all agents of one type have identical interactions, and cross-type interactions are complete bipartite. Also, nonatomic Nash stability treats one agent’s effect on coalition size as negligible, whereas the paper’s finite agents can change denominators discretely. Those are genuine modelling changes. But they are precisely the changes required by a high-multiplicity population limit, not an attempt to replace the authors’ question with an easier one.
This mirror covers Theorem 14’s maximum-welfare stable-coalition result. It generates natural follow-up questions: whether the unrestricted continuous analogue of \(\textsc{COMPUTE OPT}\) is tractable; which compatibility graphs admit polynomial algorithms; how continuous optima round back to finite elections; and whether positive-mass coordinated deviations give a meaningful continuous analogue of \(k\)-strong Nash stability.
The strongest case against the proposed mirror is that Theorem 14’s hardness is inseparable from individually specified vertices. Its Exact 3-Cover construction uses each element vertex \(y_j\) as an indivisible carrier of a set-membership choice, while every gadget vertex has a distinct neighbourhood. Replacing these vertices by positive-mass types permits the mass of \(y_j\) to split among several set gadgets. The paper’s key normalization—each element is assigned to only one set—then has no continuous counterpart. Thus the reduction does not establish hardness, or even preserve the paper’s computational object, under continuization.
The proponent’s better formulation avoids claiming hardness transfer, but that exposes the deeper problem: it is an anonymous fractional coalition-allocation model newly imposed on the paper. In the paper, coalitions are valuable precisely because they contain particular agents connected by a particular graph. A type-level blow-up replaces that identity-sensitive graph by a complete weighted graph between roles and replaces indivisible deviations by Wardrop-style infinitesimal deviations. The resulting stability condition and welfare objective are mathematically coherent, but they no longer explain the paper’s Theorem 14; they ask a different fractional coalition-formation question.
One could make that new question socially plausible—large populations of workers or residents with finitely many compatibility profiles—but that concession defeats the universal negative case. The paper’s average utility, coalition partition, unilateral stability, and welfare objective all survive naturally, and the population can genuinely have high multiplicity. The fact that the Exact 3-Cover proof does not survive is not an admissible objection: discovering whether fractional splitting makes the problem tractable or continuum-specifically hard is exactly the kind of question the programme seeks.
Accordingly, I cannot honestly defeat this anchor. I can show that the proponent overstates what Theorem 14 itself supports: its reduction neither transfers nor motivates a hardness claim for the continuous model. But a worthwhile continuous mirror nevertheless exists in the proposed high-multiplicity setting, so the requested universal negative verdict is not defensible.
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.