| paper | Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals |
| authors | Kazunori Ohta, N. Barrot, Anisse Ismaili, Y. Sakurai, M. Yokoo |
| venue | IJCAI 2017 |
| 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}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational mass vector \(\mu\in\Delta(T)\), and relation matrix \(R:T\times T\to\{F,E,\bot\}\), decide whether there exists a finite-support mass decomposition \(\mathcal P=\{(\lambda_r,x^r)\}_r\) with \(\sum_r\lambda_r x^r=\mu\) and no nonzero profile \(z\) that can be assembled from agents weakly preferring \(z\) to their assigned profiles, with a positive-mass set strictly preferring it, under enemies aversion.
A role-homogeneous atomless HG/E in which types \(t\) carry masses \(\mu_t\), coalitions are mass profiles \(x^r\), decision variables are \((\lambda_r,x^r)\), and the objective is existence of a decomposition with no positive-mass weak block.
For Theorem 4, divisible types may split across coalitions, while the atomless positive-mass blocking convention and absence of a finite-support normal form leave the exact computational model unresolved.
fatal: False
The mirror covers continuous analogues of \(\mathrm{HG/E/SC/EXIST}\), \(\mathrm{HG/F/SC/EXIST}\), and the SCC construction in Theorem 9; it leaves verification results, nonexistence examples, and any hardness-transfer proof untreated.
The strongest positive case is a role-homogeneous, atomless version of the same hedonic game—not a lottery over coalition structures and not fractional preferences. The population becomes continuous; coalition formation and blocking remain the objects of study.
Take a finite set of complete types \(T\), with \(|T|=\tau\). A type \(t\) specifies how its agents regard every type \(u\): \(R(t,u)\in\{F,E,\bot\}\). The society is a rational mass vector \(\mu\), where \(\mu_t\) is the fraction of agents of type \(t\). Thus a finite realization could contain \(M\mu_t\) interchangeable agents of type \(t\), with \(M\gg\tau\).
For a coalition profile \(x\in[0,1]^\tau\), let \(x_u\) be the mass of type \(u\) in the coalition, \(f_t(x)=\sum_{R(t,u)=F}x_u\), and \(e_t(x)=\sum_{R(t,u)=E}x_u\). Type \(t\)'s preferences are exactly those in the paper: enemies aversion compares \((-e_t(x),f_t(x))\) lexicographically, while friends appreciation compares \((f_t(x),-e_t(x))\).
A continuous coalition structure is a mass decomposition into coalition profiles. In a finite-support representation it consists of profiles \(x^1,\ldots,x^q\), multiplicities \(\lambda_1,\ldots,\lambda_q\ge 0\), and singleton mass \(s\), satisfying \(\sum_r\lambda_r x^r+s=\mu\). Here \(\lambda_r x^r_t\) is the mass of type \(t\) currently assigned to coalitions of profile \(x^r\). A proposed deviating coalition has profile \(z\). It blocks if the required mass \(z_t\) can be taken from type-\(t\) agents whose current profile they strictly prefer \(z\) to; for a weak block, “strictly” is replaced by “weakly”, with positive mass of at least one type strictly improving. This positive-mass convention is the natural atomless analogue of “at least one agent”.
The regime is plausible for repeated team formation in a large organisation, public-sector workforce, or online community. Types might be departments, roles, locations, or skill categories. Agents in one type have the same collaboration template: they regard some role types as friends, some as enemies, and the rest as irrelevant. The relation can remain directed, as in the paper. Millions of agents and perhaps tens or hundreds of role types make the high-multiplicity interpretation genuine.
My lead anchor is Theorem 4, proved in this paper. It states that HG/E/SC/EXIST—whether an enemies-aversion hedonic game with friends, enemies, and neutrals has a coalition structure in the strict core—is \(\mathrm{NP}^{\mathrm{NP}}\)-complete. Membership comes from guessing a coalition structure and using an NP oracle to test whether it has a weakly blocking coalition. Hardness is obtained from the \(\mathrm{coNP}^{\mathrm{NP}}\)-complete MINMAXCLIQUE problem using neutral edges, fulcrum agents, inhibitors, and circuit gadgets.
The corresponding continuous problem is:
\(\mathrm{C\text{-}HG/E/SC/EXIST}\): given \(T\), \(\mu\), and the type-level relation matrix \(R\), does there exist a continuous coalition structure \(\mathcal P\) with no positive-mass weakly blocking coalition under enemies aversion? A yes-solution is an explicit mass decomposition \(\mathcal P\); a no-instance has no such decomposition.
This is recognisably the same problem. The preference rule, coalition structures, weak blocking, strict core, and neutral relations are unchanged. Only named agents have become interchangeable mass. I expect the continuous problem to be Class B, because the paper’s hardness is driven mainly by the relation graph and its logical gadgets, not by large population counts. The source graph can be interpreted as a graph of role types, each replicated many times. The technical issue is whether additional gadgets can force each logical type’s mass to make an all-or-nothing choice; without such a mass-locking lemma, fractional splitting could dissolve the reduction. That is precisely the interesting continuous question rather than a reason to reject the mirror.
My second anchor is Theorem 8, also proved in this paper, though its proof is given as a sketch. It states that HG/F/SC/EXIST—existence of a strict-core-stable coalition structure under friends appreciation with neutrals—is \(\mathrm{NP}^{\mathrm{NP}}\)-complete. The reduction again uses MINMAXCLIQUE, inhibitors, and circuit gadgets, but exploits the friends-appreciation tie-break: agents can be forced to choose between coalitions with the same number of friends but different numbers of enemies.
The matching continuous problem is:
\(\mathrm{C\text{-}HG/F/SC/EXIST}\): given \(T\), \(\mu\), and \(R\), does there exist a continuous coalition structure with no positive-mass weakly blocking coalition under friends appreciation?
I again expect Class B, although this is a less secure hardness conjecture than the enemies-aversion mirror because fractional splitting may interfere especially directly with the equal-friends/different-enemies gadgets. It nevertheless preserves the paper’s central question: whether a very compact preference language remains second-level hard when a large population is represented by role masses.
The third anchor is Theorem 9, proved here. It states that for every HG/F, a core-stable coalition structure exists, and one can compute it in polynomial time as the strongly connected components of the friends digraph \(G_F=(N,A_F)\).
Its continuous version is:
\(\mathrm{C\text{-}HG/F/C/CONSTRUCT}\): given \(T\), \(\mu\), and \(R\), output a core-stable continuous coalition structure under friends appreciation.
Build the type-level friends digraph \(G_F(T)\), ignoring zero-mass types. Compute its strongly connected components. For each component \(S\), put all mass \(\mu_t\), \(t\in S\), into one coalition. This is polynomial in \(\tau\). The proof lifts directly: take a sink strongly connected component. If a deviation takes only part of its mass, some participating type loses friends; if it takes the whole component and adds agents outside it, no member gains friends because the component is a sink, and adding agents can only add enemies or neutrals. Repeating over the condensation DAG rules out every blocking coalition.
This anchor is securely Class A. It is also useful because it shows that continuization need not destroy the paper’s structural algorithm; it can expose the correct quotient graph and make the population size disappear from the running time. It does not imply anything similar for the strict core.
I regard Theorem 4 as the best programme anchor, because it asks the central question: does discrete second-level hardness survive when population multiplicity becomes divisible? Theorem 9 is the most technically secure positive lift. I deliberately omit Theorem 6 because it would add a very similar enemies-aversion existence anchor without widening the case.
The weakest point is mass splitting. The finite reductions rely on indivisible agents, whereas a continuum lets one type divide itself among several coalitions. Proving that role-level gadgets lock masses into integral-looking choices is essential; I have not established it here. A second, related issue is representation: the semantic model allows measurable coalition decompositions, while a computational version needs a finite-support or other exact encoding. Those are genuine research questions, not details to conceal.
Even if the hardness anchors collapse to tractability, these are still legitimate mirrors: they ask whether the paper’s strict-core existence problems become easier in the high-multiplicity regime. The resulting follow-up questions include fixed-\(\tau\) complexity, bounded-treewidth type graphs, finite-support and rounding theorems, and whether continuous stable structures can be approximated by stable or nearly stable finite high-multiplicity elections.
The strongest negative case is that the two hardness anchors are not yet continuous computational problems in the programme’s sense. The paper’s reductions are built from named, indivisible agents: one fulcrum agent, paired inhibitor agents, singleton vertex agents, and circuit gadgets whose logic depends on an agent making an all-or-nothing choice. In a role-homogeneous society, copies of a type may split their mass between several coalitions. A fulcrum type can divide between the two alternatives; a vertex type can be partly “available” on each side; and the inhibitor and circuit gadgets no longer enforce Boolean values merely from friends, enemies, and neutrals. The proponent has identified exactly the missing theorem—a mass-locking lemma—but without it the claimed \(\mathrm{NP}^{\mathrm{NP}}\)-hardness is only a conjectural analogy.
The obvious repair does not restore the paper’s result cleanly. If every gadget agent becomes its own type, then \(\tau\) grows with the reduction and the construction is no longer a genuinely high-multiplicity interpretation. If many copies are assigned to each gadget type, divisibility returns. Adding minimum masses, indivisible role blocks, or constraints that force a type to move together would restore the discrete gadget, but those are extra combinatorial restrictions rather than consequences of the paper’s hedonic model.
There is also a more basic problem with Theorems 4 and 8. A continuous coalition structure is generally a measure over coalition profiles \(x\in[0,\mu]^\tau\), not the finite-support list assumed in the positive case. No finite-support theorem is supplied. With unrestricted measurable decompositions, the proposed existence problem has no ordinary finite certificate and therefore no immediate \(\mathrm{NP}^{\mathrm{NP}}\) interpretation. Restricting to finite support makes the problem computationally encodable, but changes the model unless one proves that every relevant stable structure has such a representation.
Strict-core stability is especially unstable under this limit. In a finite population of size \(M\), a weak blocking coalition may contain only one strictly improving agent, whose normalized mass is \(1/M\). Under the proposed atomless rule, that witness disappears because strict improvement must occur on a positive-mass set. If null strict witnesses are admitted, the model behaves differently again. Thus the continuous problem is not simply the high-multiplicity relaxation of the paper’s strict-core problem; it is a new bulk-stability concept. The friends-appreciation gadgets are even more vulnerable because their choices depend on exact equalities in friend counts and one-agent enemy tie-breaks.
Theorem 9 is the serious difficulty for the negative case. Its core-stability result does have a clean continuous lift: form the SCCs of the positive-mass type-level friends graph and place each SCC’s entire mass in one coalition. A sink component cannot participate in a strict blocking coalition: a proper submass loses some friends, while the full component gains no friends from outside. Recursing through the condensation graph proves core stability. This is a legitimate Class A high-multiplicity mirror.
The best objection is that this mirror is population-inert. The SCCs depend only on \(R\), not on \(\mu\); the mass vector merely labels how much material is placed in each already-determined coalition. The construction is therefore a direct quotient of the finite theorem, with no continuous optimization, pricing problem, or new population-dependent phenomenon. But that is a weak objection under the programme’s rules: a simple Class A answer is still an answer, and the result is not already a continuous treatment.
So the honest negative verdict is narrower than the requested universal one. Theorem 4 and Theorem 8 do not presently support the proponent’s hardness claims without substantial new modelling and encoding work. They remain potentially worthwhile open mirrors, however. Theorem 9 survives outright as a natural continuous-population result. I therefore cannot credibly argue that this paper has no worthwhile continuous mirror in any scenario; the strongest defensible conclusion is that its two exciting hardness anchors are presently speculative, while its simpler core-construction anchor is green.
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.