| paper | Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity |
| authors | — |
| venue | AAMAS 2023 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), and disjoint directed friendship and enemy graphs \(G_g,G_b\) on \(T\) such that \(G_g\cup G_b\) is acyclic, decide whether there exist rational coalition vectors \(z^1,\ldots,z^q\in\mathbb{Q}_{\ge 0}^{T}\), with \(q\le |T|\) and \(\sum_{j=1}^{q}z_t^j=\mu_t\) for every \(t\), such that no positive-mass type assigned to any \(z^j\) strictly prefers another existing coalition or a new singleton coalition under the lexicographic valuation \(v_t(z)=\left(\sum_{r\in N^+_{G_g}(t)}z_r,-\sum_{r\in N^+_{G_b}(t)}z_r\right)\).
A hierarchical high-multiplicity population of relationship types with rational mass \(\mu\), a type-level DAG of friendship and enemy relations, decision variables \(z_t^j\) allocating type mass to anonymous coalitions, and a feasibility objective requiring no profitable type-level unilateral deviation.
The mass-vector representation imposes grouped anonymous coalitions and does not capture finite blow-ups with arbitrary fragmentation of identical agents across many coalitions, so it is not the canonical continuum limit of the full named-agent model.
fatal: False
The mirror covers Theorem 10's Nash-existence result for FENs instances whose union relationship graph is acyclic; it leaves the paper's cyclic-graph hardness results, verification problems, individual stability, and parameterized dichotomies untreated.
My lead mirror is a continuum version of the paper’s FENs-NashEx result on acyclic relationship graphs.
The anchor is Theorem 10, proved in this paper (the conference text gives a proof sketch, with details deferred). It states that if the union of the friendship and enemy graphs is acyclic, every FENs instance admits a Nash-stable partition, computable in polynomial time.
The natural high-multiplicity regime is a population of \(N\) agents arranged in \(\tau\) recurring social or professional roles, with \(N\gg\tau\). A type \(t\) specifies the complete relationship profile of its agents: which other types are friends, which are enemies, and which are neutral. All agents of type \(t\) have mass \(\mu_t\), with \(\sum_t\mu_t=1\), and are otherwise indistinguishable. Within-type relationships are neutral. This is plausible, for example, in a hierarchical organisation or professional network where friendship and hostility follow role, department, or seniority, and the resulting type-level relationship graph is acyclic.
I would name the continuous problem DAG-FENs-NashEx\(_\infty\).
An instance consists of:
A coalition is a mass vector \(z\in\mathbb{R}_{\ge0}^{T}\), where \(z_t\) is the mass of type \(t\) in that coalition. A solution is a finite list of coalition vectors \(z^1,\ldots,z^q\) satisfying
\[ \sum_{j=1}^{q} z_t^j=\mu_t \]
for every \(t\). A type-\(t\) agent in coalition \(z\) evaluates it lexicographically by
\[ v_t(z)= \left( \sum_{r\in N^+_{G_g}(t)}z_r,\; -\sum_{r\in N^+_{G_b}(t)}z_r \right), \]
maximising friend mass and, subject to that, minimising enemy mass. The zero vector represents forming a new singleton coalition. The mass partition is continuously Nash stable if no positive-mass type \(t\) assigned to \(z^j\) strictly prefers any existing coalition \(z^\ell\), or a new coalition, to \(z^j\).
The question is whether such a mass partition exists, and a witness is the finite list of vectors \(z^1,\ldots,z^q\). This is genuinely a population continuization: the action variable is the allocation of type mass to coalitions, while the preference rule and Nash-stability concept remain those of the paper.
The problem is expected to be in Class A. Take a topological ordering \(t_1,\ldots,t_\tau\) of \(G_g\cup G_b\), with every arc directed forward. Process types in reverse order. When processing \(t_i\), all of its friend and enemy types have already been assigned to coalitions. Put all mass \(\mu_{t_i}\) into whichever existing coalition, or the empty coalition, maximises \(v_{t_i}\). Later types cannot affect \(t_i\)'s valuation, because no later-processed type is an out-neighbour of \(t_i\). Nor can the placement affect already processed types. Thus the construction is Nash stable and runs in time polynomial in \(\tau\) and the encoding length of \(\mu\), independently of \(N\).
The high-multiplicity bridge is exact. Given rational \(\mu\), choose \(N\) so that \(N\mu_t\) is integral and replace each type by \(N\mu_t\) identical clones. The type-level DAG becomes a DAG on the expanded agents, and the paper’s reverse-topological construction collapses precisely to the mass algorithm above. Conversely, the continuous output is a compressed representation of a stable partition of arbitrarily large finite blow-ups. The gain is therefore not merely cosmetic: \(N\) may be enormous while the witness contains only \(O(\tau)\) coalition vectors.
The mirror is also recognisably the authors’ problem. It preserves FEN preferences, the friends-before-enemies comparison, coalition formation, and Nash stability. Only the population representation changes from named agents to masses of interchangeable agents. It covers Theorem 10’s acyclic-union-graph Nash-existence result, not the paper’s hardness results for arbitrary cyclic graphs.
Further questions arise naturally: whether bounded feedback-arc number admits an FPT continuous algorithm; whether a linear cost of moving mass can be added while retaining tractability; and when a stable mass partition can be chosen without splitting any type across coalitions.
The weakest point is the nonatomic convention. A single agent has zero mass, so the effect of joining a coalition is represented by aggregate type mass rather than by a \(1\)-agent increment. This can erase phenomena caused by very small coalitions. It is not a defect for the intended high-multiplicity regime, but it means this is a deliberately atomless mirror of Nash stability, not a claim that every finite-agent detail survives unchanged. That weakness is avoided more cleanly here than for individual stability, because Nash stability has no coalition-acceptance condition whose meaning would collapse in the continuum.
The strongest case against the proposed anchor is that it is not really a continuization of the paper’s general graph model. The paper allows arbitrary named-agent relationships. To obtain \(\tau \ll N\), the mirror imposes a much stronger block-uniform structure: every agent of type \(t\) must relate identically to every agent of type \(r\), with within-type relations fixed as neutral. The original graph’s topology has been replaced by a role graph. If arbitrary topology is retained, the type description can require essentially one type per agent; if block uniformity is imposed, Theorem 10 already applies directly to the resulting blow-up.
There is also a genuine representation problem. A population mass vector records how much mass of each type exists, but not how that mass is distributed among coalitions. A finite blow-up may contain \(N\) separate singleton coalitions, whereas the proposed vector representation may pool all mass of type \(t\) into one coalition. An earlier type that likes \(t\) then sees mass \(\mu_t\) in one destination rather than one clone in each of many destinations. Thus the finite list of coalition vectors is an additional anonymous-coalition convention, not forced by the continuum limit. Retaining arbitrary coalition fragmentation would require a measure over coalition compositions, potentially an infinite-dimensional object rather than the proposed compact witness.
The atomless Nash notion has a related limitation: an individual deviation has zero mass and therefore does not alter any aggregate coalition. That is a legitimate nonatomic best-response concept, but it selects away finite-population effects involving singleton coalitions and one-agent increments. Replacing it by positive-mass deviations would no longer mirror Nash stability; retaining all microscopic coalitions would require a substantially richer model.
These objections do not, however, defeat the anchor. A hierarchical role network with peer-neutral types is a plausible high-multiplicity regime. For rational \(\mu\), denominator clearing gives a finite blow-up with \(N\mu_t\) clones, and the reverse-topological construction supplies a stable grouped partition of that blow-up. The compression from \(N\) agents to \(O(\tau)\) coalition vectors is real. Theorem 10 is also an explicit computational result, and Nash stability avoids the acceptance problem that makes individual stability more fragile in the continuum.
So I would reject this as a narrow standalone contribution rather than as an invalid mirror: it is mainly a type-compressed restatement of an already elementary topological algorithm, with no need for continuous optimization. But under the programme’s rules, that is not enough to establish that no worthwhile mirror exists. The proponent’s Theorem 10 anchor survives, and an honest universal negative case is weak.
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.