| paper | Hedonic Diversity Games: A Complexity Picture with More than Two Colors |
| authors | Robert Ganian, Thekla Hamm, Dušan Knop, Šimon Schierreich, Ondřej Suchý |
| venue | AAAI 2022 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 9
statement extracted from the paper’s text layer
Given marker types ( M_1,\ldots,M_\omega ) and normal types ( G_1,\ldots,G_k ) with rational masses ( a_i,b_j ) , colors, explicitly listed finite sets ( S_i\subseteq\mathbb{Q}_{\ge0}^k ) , and a bound ( rho_{\ge1} ) , does there exist a finite collection of coalition-mass vectors ( x^r\in\mathbb{Q}_{\ge0}^{T} ) and singleton masses ( ell_t\ge0 ) satisfying ( \sum_r x_t^r+\ell_t=\mu_t ) and using at most ( rho_{\ge1} ) occupied coalitions, such that no infinitesimal unit of any type can profitably move to an occupied coalition or its singleton coalition under price-taking palette changes? Marker type ( M_i ) prefers a coalition with no other marker color and ( x_{G_j}=s_jx_{M_i} ) for some ( s\in S_i ) , then its singleton, then all other coalitions; normal types prefer exactly one marker color, then no marker, then multiple marker colors.
A nonatomic high-multiplicity hedonic diversity game whose types carry colors and complete palette preferences, whose rational masses are ( \mu_t ) , and whose decision variables are coalition masses ( x_t^r ) and singleton leftovers ( \ell_t ) ; feasibility asks for price-taking Nash stability, including the all-or-nothing activation forced by strict preference over being alone.
The proposed LP incorrectly permits a type's mass to split between a strictly preferred approved coalition and its singleton option; stability instead imposes all-or-nothing activation, while a faithful parameterized version should also bound the number of occupied coalitions by ( rho_{\ge1} ) .
fatal: False
The mirror covers the HDG-NASH half of Theorem 9 on the marker/normal restricted family; it leaves the HDG-INDIVIDUAL half, the other parameterized results, and the full oracle-input HDG problem untreated.
The strongest honest case is a Class-A mirror of Theorem 9, covering HDG-NASH rather than the whole paper.
The right object is a nonatomic high-multiplicity HDG. A type \(t\) consists of its color \(c(t)\) and its complete master preference order \(\succeq_t\); color must be included because it affects every coalition palette. The input gives rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). A coalition is a mass vector \(x\in\mathbb{Q}_{\ge0}^{T}\), with palette
\[ \pi_c(x)=\frac{\sum_{t:c(t)=c}x_t}{\sum_t x_t}. \]
A solution is a finite collection of coalition vectors \(x^1,\ldots,x^K\), together with leftover singleton mass \(\ell_t\), satisfying
\[ \sum_{r=1}^{K}x_t^r+\ell_t=\mu_t. \]
The singleton mass is an outside option with palette \(e_{c(t)}\). Nash stability is interpreted in the standard price-taking limit: whenever \(x_t^r>0\), type \(t\) weakly prefers \(\pi(x^r)\) to every other occupied coalition palette and to \(e_{c(t)}\); the same must hold for singleton mass. The decision problem is whether such a mass allocation exists. This preserves the paper’s colors, palettes, master lists, and Nash deviations; only the population and coalition assignments become divisible.
My lead anchor is Theorem 9: “HDG-NASH and HDG-INDIVIDUAL are W[1]-hard parameterized by \(\gamma+\rho_{\ge1}+\tau\).” This theorem is proved in the paper, via a reduction from partitioned MULTIDIMENSIONAL SUBSET SUM. I use only its HDG-NASH part. The reduction is especially suitable because its combinatorics come from choosing one vector for each marker agent.
Call the continuous problem the Fractional Marker HDG-NASH\(_\infty\). Its instance has marker types \(M_1,\ldots,M_\omega\), normal types \(G_1,\ldots,G_k\), rational masses \(a_i\) and \(b_j\), and explicit finite sets \(S_i\subseteq\mathbb{Q}_{\ge0}^{k}\). Marker type \(M_i\) strictly prefers a coalition containing only marker color \(i\) and satisfying
\[ x_{G_j}=s_jx_{M_i}\qquad\text{for some }s\in S_i, \]
then being alone, then every other coalition. A normal type \(G_j\) strictly prefers any coalition containing exactly one marker color, then a coalition with no marker color, then one containing multiple marker colors. The question is whether a nonatomic Nash-stable coalition structure exists.
This is a faithful high-multiplicity scenario for, for example, many repeated cohorts of organizers and participants forming project teams, activity groups, or tables. Agents with the same color and master list are genuinely interchangeable, and the population is large compared with the number of such types. The source paper’s reduction itself is not evidence that its hard instances are high-multiplicity—the marker agents are singletons—so the continuous version is deliberately asking what happens after those marker cohorts are replicated.
I expect Fractional Marker HDG-NASH\(_\infty\) to be polynomial-time solvable. Let \(z_{i,s}\) be the mass of marker type \(M_i\) placed in coalitions realizing vector \(s\). A stable structure exists precisely when the following linear feasibility system has a solution:
\[ z_{i,s}\ge0, \]
\[ \sum_{s\in S_i}z_{i,s}\le a_i \qquad\text{for every }i, \]
\[ \sum_{i=1}^{\omega}\sum_{s\in S_i}s_jz_{i,s}=b_j \qquad\text{for every }j. \]
The unused marker mass remains alone. Every normal unit is placed in a one-marker coalition, and every participating marker unit is in one of its approved compositions. Thus the discrete “choose one \(s\in S_i\)” operation becomes a convex combination of choices. With explicitly listed \(S_i\), this is an ordinary rational LP. The W[1]-hardness therefore plausibly dissolves for the precise reason continuization is meant to expose: indivisible population units were carrying the selection combinatorics.
This does not establish that arbitrary continuous HDG-NASH is in P. With unrestricted preference oracles, the problem may have a difficult pricing or continuum-specific boundary. The natural follow-up questions are whether arbitrary palette orders admit a column-generation algorithm, whether bounding the number of positive-mass coalition templates restores hardness, and how to round a continuous stable structure back to a finite election while controlling stability violations.
The weakest point is that the mirror uses price-taking deviations and allows one type’s mass to split across several coalitions. In the original reduction, a single marker agent is pivotal, so forbidding such splitting would preserve much of the hardness. That is a real limitation, but it is also exactly the high-multiplicity change: a large cohort of identical marker agents should be divisible at population scale. I would not claim that this mirror covers individual stability, because in a nonatomic model an infinitesimal entrant does not change the target coalition’s palette, causing individual stability to collapse toward Nash stability unless a positive-mass acceptance notion is added.
The proponent’s anchor is not valid as stated. Its LP does not characterize nonatomic Nash stability.
Take one marker type \(M_i\) of mass \(a_i=2\), one normal type of mass \(b_1=1\), and \(S_i=\{(1)\}\). The proposed LP accepts \(z_{i,(1)}=1\), leaving marker mass \(1\) alone. But every residual marker agent strictly prefers the occupied \(1{:}1\) coalition to being alone; under price-taking deviations, joining infinitesimally does not change that coalition’s palette. Hence the alleged stable allocation is unstable.
This is not a cosmetic correction. If \(z_i=\sum_s z_{i,s}\), stability requires
\[ z_i=0 \quad\text{or}\quad z_i=a_i, \]
because a type cannot have some mass in an approved coalition and some mass exercising a strictly worse singleton option. The correct formulation therefore needs binary activation variables:
\[ \sum_{s\in S_i}z_{i,s}=a_i y_i,\qquad y_i\in\{0,1\}. \]
The continuous relaxation has removed the discrete choice only by allowing an allocation that Nash stability forbids. If all marker mass is forced to participate, the formulation becomes an LP, but that is a different game: it deletes the paper’s explicit “being alone” alternative and the optional-marker branch used in the reduction.
The proposed mirror also drops the parameter \(\rho_{\ge1}\) that anchors Theorem 9. Its LP may use one coalition for every pair \((i,s)\), whereas the paper bounds the number of coalitions. A faithful mass version must specify a corresponding bound on occupied coalition templates. Once such a bound is retained, splitting a marker cohort among arbitrarily many approved palettes is no longer available; in the natural one-activity/one-coalition interpretation, it restores the original choice of one vector \(s\in S_i\).
There is a secondary representation problem: the paper’s preferences are accessed through an oracle, while the claimed polynomial LP is polynomial only because every \(S_i\) is explicitly listed. With succinct preference descriptions, constructing or separating over the relevant convex hull is itself an additional computational problem. Thus the claimed result is for a specially encoded fractional packing subproblem, not yet for a continuous version of HDG-NASH under the paper’s input model.
That said, the universal negative case is honestly weak. Hedonic diversity games do have a plausible high-multiplicity interpretation—large cohorts of agents with the same color and palette preferences—and if one deliberately permits type mass to split among many coalition templates while removing the singleton issue, the resulting fractional problem may well be a worthwhile Class-A mirror. The strongest conclusion against the present case is therefore narrower: the proponent has not established a valid mirror of Theorem 9; their LP gains tractability by changing the stability semantics and omitting a central coalition constraint.
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.