| paper | Hedonic Games with Ordinal Preferences and Thresholds |
| authors | Anna Maria Kerkmann, J. Lang, Anja Rey, J. Rothe, Hilmar Schadrack, Lena Schend |
| venue | JAIR 2020 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 43 supplies the required named computational result, but its proposed mirror changes the problem at the limit. In the atomless model, a type’s mass may split among teams, an infinitesimal deviation does not alter team composition, and one shared type completion replaces the paper’s independent player completions; this is Wardrop-style stability rather than the paper’s Nash-stability existence problem. The typed workforce question is natural, but under the stated gate it is not a surviving continuous analogue of the anchored theorem.
fails bit b-changes — the continuum limit changes the question
The atomless limit changes Nash stability itself: fractional type mass can occupy several teams, individual deviations have no compositional effect, and completion choices become type-level rather than player-level.
fatal: True
The attempted mirror covers only Theorem 43 and leaves the paper’s other stability-verification, existence, and hardness results untouched.
The strongest mirror is a high-multiplicity version of the paper’s possible Nash-stability existence problem, with workers replacing named players and team compositions replacing named coalitions.
My anchor is Theorem 43, “POSSIBLE-NASH-STABILITY-EXISTENCE is NP-complete.” This theorem is proved in the paper; its reduction is from X3C, although the construction is inspired by Sung and Dimitrov. The problem asks, given a FEN-hedonic game, whether there exists a coalition structure that is Nash stable under at least one complete preference profile extending the polarized responsive preferences. Thus both the coalition structure and the completion of every player’s incomplete preference relation are existentially quantified. The proof establishes NP membership using polynomial-time possible Nash-stability verification, and NP-hardness by constructing chain players, element players, and set-player chains. The chain players force one chain coalition; each set-player chain forces its members to stay together; and the element players can be stably assigned to selected coalitions \(P_S\) exactly when the corresponding sets form an exact cover. Hence a possibly Nash-stable coalition structure exists if and only if the X3C instance has an exact cover.
I would call the continuous problem POSSIBLE-CONTINUOUS-FEN-NASH-EXISTENCE. An instance consists of a finite set of complete FEN types \(T=\{1,\ldots,\tau\}\), a rational population distribution \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\), and a bound \(K\) on the number of positive-mass teams. A type \(t\) specifies its friends, enemies, neutral types, weak order over friends, and weak order over enemies. Two workers of type \(t\) are identical for the problem: they have exactly the same friend/enemy/neutral classification and rankings.
A team is represented by a mass vector \(q\in\mathbb{Q}_{\ge0}^{\tau}\), where \(q_t\) is the fraction of the whole population in that team having type \(t\). A team structure is a list \(q^1,\ldots,q^K\) satisfying \(\sum_{\ell=1}^K q^\ell=\mu\). This does not give an individual fractional team membership: every worker still belongs to one integral team; \(q^\ell_t\) records only the mass of type-\(t\) workers assigned to team \(\ell\).
The paper’s polarized responsive comparison extends naturally from injections to fractional monotone transports. For two team-mass vectors \(q\) and \(q'\), \(q\) is at least as good as \(q'\) for type \(t\) when all friend mass in \(q'\) can be transported into no more friend mass in \(q\), with each unit transported only to an equally or more preferred friend type, and all enemy mass in \(q\) can be transported into no more enemy mass in \(q'\), with each current enemy no worse than its matched enemy in \(q'\). Neutral mass is ignored. This is precisely the paper’s injection definition with unit agents replaced by divisible mass. It induces a partial order \(q\succeq^{\mathrm{PR}}_t q'\), with strict comparisons, indifferences, and incomparabilities as in the paper.
The question is whether there are team masses \(q^1,\ldots,q^K\) and, for every type \(t\), a complete preference relation \(\succeq_t\) extending its fractional polarized-responsive order, such that every positive-mass type in every team weakly prefers its current team to every other existing team and to the empty team. Formally, whenever \(q^\ell_t>0\), require \(q^\ell\succeq_t q^j\) for every \(j\), and \(q^\ell\succeq_t 0\). The empty vector represents being alone. A deviating individual has infinitesimal mass, so joining another team does not change that team’s aggregate composition; this is the natural nonatomic limit of the paper’s \(C\cup\{i\}\).
This is a genuine population continuization. The population is the continuous object; teams remain coalitions, preferences remain ordinal and FEN-based, and the decision variable is still the existence of a Nash-stable coalition structure. The bound \(K\) is a practical computational specification: in the paper a finite coalition structure is implicit, whereas a continuum model needs a finite description of the positive-mass team templates.
The natural regime is a large organization, university, hospital system, or distributed company assigning many workers to teams. There may be millions of workers but only moderately many repeated types: for example, workers may share role, specialization, and team preferences, while differing only through their type-level profile. A type might mean “junior data scientist who prefers machine-learning specialists, is neutral toward designers, and dislikes sales staff,” together with the relevant rankings. The population mass \(\mu_t\) is the fraction of workers of that type. This is exactly the kind of central-authority team-formation setting the paper itself discusses in its engineering interpretation and future-work paragraph.
I would initially expect this problem to be Class B, with an important qualification. The X3C combinatorics in Theorem 43 live primarily in the incidence structure among preference types—the element/set relationships and the chain gadgets—not merely in the number of named individuals. That suggests that duplicating each role many times should not eliminate the obstruction. A successful transfer proof would need fractional-locking gadgets ensuring that a type’s mass cannot harmlessly split among several set coalitions. The original theorem does not provide that proof: divisible mass may turn exact cover into a fractional-cover problem. If such locking is impossible, the problem becomes an excellent Class C candidate, or possibly a configuration/flow problem with a tractable special case. Either outcome would be informative.
The weakest point is therefore clear. The original FEN model ranks named agents, whereas this mirror ranks type classes, and the continuum turns unilateral deviations into infinitesimal deviations. That is a real co-modification, not cosmetic notation. It is nevertheless defensible here: the paper explicitly treats FEN games as compact, engineering-oriented descriptions of team formation, and a high-multiplicity regime requires agents with identical problem-relevant preferences to be grouped into types. The mirror should be presented as the authors’ problem in a repeated-role setting, not as a claim that every named-agent FEN game has a canonical continuum limit.
Further questions include whether the Theorem 43 reduction can be repaired with fractional-locking chains; whether the corresponding necessary-stability problem behaves differently; whether fixed \(\tau\), bounded \(K\), or bounded friend/enemy-rank depth yields a configuration-LP algorithm; and how a stable continuous team structure can be rounded to a finite population with an additive stability guarantee.
Theorem 43 is a genuine computational anchor, so the negative case cannot rely on “the paper has no algorithmic result.” The strongest objection is that the proposed atomless Nash problem does not preserve the mechanism that makes Theorem 43 an exact-cover problem.
The reduction relies on indivisible named players. The chain players force one chain coalition; each \(Q_S\) must remain together; and each element player \(\beta_b\) must choose one coalition \(P_S\). The exact-cover condition comes from the fact that one individual \(\beta_b\) cannot simultaneously belong to several \(P_S\)'s.
In the proposed model, a type’s mass can be split. A positive fraction of type \(\beta_b\) can join \(P_{S_1}\), another fraction \(P_{S_2}\), and so on. A unilateral deviation has zero mass, so it does not change either team’s composition. In symmetric instances, every incident \(Q_S\) can have the same mass and rank for \(\beta_b\); the fractions are then indifferent among those teams and have no profitable deviation. The set players are neutral toward the relevant element players, so they do not restore the all-or-nothing constraint. The reduction’s crucial inference—“each \(\beta_b\) must be assigned to exactly one \(P_S\)”—therefore fails, and exact cover is replaced by a fractional incidence condition.
This is not an objection that the continuous answer might be easier. A tractable relaxation would be valuable. The problem is more basic: the stated object is no longer the high-multiplicity version of the paper’s Nash problem in the sense required for a two-way dictionary. The finite problem’s stability depends on the \(+1\) contribution of the deviating agent; the atomless limit erases that contribution. The same issue affects the possible-completion quantifier: in the paper, each named player may receive an independent completion, whereas all copies of one continuous type must share a type-level completion.
The obvious repair is to force every type’s entire mass into one team, or to make a type a nondivisible cohort. That can restore the exact-cover gadget, but it introduces an integrality or block-assignment constraint absent from Nash stability in the paper. The population may then contain many people, but the decision variable is a finite partition of indivisible type blocks; the continuous mass is merely a label. Introducing a positive transfer granularity \(\varepsilon\) has the same problem: it restores a discrete model, and the relevant effect vanishes as \(\varepsilon\to0\).
A bound \(K\) on the number of teams does not repair this. With \(K\) large enough, fractional splitting remains possible; with \(K\) fixed, the problem has acquired a new team-count restriction that is not present in Theorem 43. Capacities, cohort indivisibility, or composition thresholds might produce an interesting new team-formation problem, but they would be additional modelling ingredients doing the computational work, not a continuization of this theorem.
There is nevertheless an important limit to this negative case. A natural atomless typed workforce model—especially one motivated by the paper’s own employee-team interpretation—does exist. It could yield worthwhile questions about fractional stable team structures, rounding, or the boundary between fractional and integral stability. I therefore cannot honestly establish the universal claim that no continuous mirror is worthwhile. What the argument does establish is narrower: the proposed mirror does not successfully carry Theorem 43’s anchor, and every repair that preserves its exact-cover content appears to reintroduce the discreteness that continuization was meant to remove.
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.