Answer: \(\mathrm{NP\text{-}hard}\)
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateHDG-NASH and HDG-INDIVIDUAL are W[1]-hard parameterized by γ + ρ≥1 + τ.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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.
Definitions. Let the types be marker types \(M_1,\ldots,M_\omega\) of distinct marker colors and normal types \(G_1,\ldots,G_k\), with masses \(\mu_{M_i}=a_i\) and \(\mu_{G_j}=b_j\). For each \(i\), \(S_i\subseteq\mathbb{Q}_{\geq 0}^k\) is explicit. An occupied coalition \(r\) has a positive rational mass vector \(x^r\in\mathbb{Q}_{\geq0}^{\{M_i,G_j\}}\); singleton-state masses are \(\ell_t\geq0\), and \(\sum_r x_t^r+\ell_t=\mu_t\). At most \(\rho_{\geq1}\) occupied coalitions and positive singleton states may occur.
A marker \(M_i\) ranks highest coalitions having no marker color other than its own and satisfying \(x^r_{G_j}=s_jx^r_{M_i}\) for some \(s\in S_i\); it next ranks its pure-type singleton state, then all other coalitions. Each normal type ranks coalitions with exactly one marker color above those with no marker color, above those with multiple marker colors. Stability is price-taking Nash stability: no infinitesimal mass of any type strictly prefers the unchanged palette of another occupied coalition, or its pure-type singleton state, to that of its current state.
Target. Is deciding whether such a price-taking Nash-stable mass allocation exists solvable in polynomial time, or is it NP-hard?
Known results. For finite-agent Hedonic Diversity Games, deciding existence of a Nash-stable outcome is W[1]-hard parameterized by the number of colors, the bound on total coalitions, and the number of agent types. The same lower bound holds for individually stable outcomes.
Deciding whether a price-taking Nash-stable mass allocation with at most \(\rho_{\geq 1}\) occupied states exists is \(\mathrm{NP\text{-}hard}\).
Hardness holds even when every mass equals \(1\), every set \(S_i\) is a singleton, and every vector occurring in an \(S_i\) is binary.
Reduce from Exact Cover by 3-Sets.
An instance consists of a universe \(U=\{u_1,\ldots,u_k\}\), where \(k=3q\), and a family \(\mathcal C=\{C_1,\ldots,C_\omega\}\) with \(|C_i|=3\) for every \(i\). The question is whether some subfamily covers every element of \(U\) exactly once.
Introduce one marker type \(M_i\) for every set \(C_i\), and one normal type \(G_j\) for every element \(u_j\). Set
\[ a_i=1,\qquad b_j=1. \]
For each \(i\), let \(S_i=\{s^i\}\), where \(s^i\in\{0,1\}^k\) is the incidence vector of \(C_i\):
\[ s^i_j= \begin{cases} 1,&u_j\in C_i,\\ 0,&u_j\notin C_i. \end{cases} \]
Finally, set the support bound to
\[ \rho_{\geq1}=\omega. \]
The construction is polynomial, and all numerical data are in \(\{0,1\}\).
In every stable allocation of the constructed instance, at least \(\omega\) occupied coalitions and positive singleton states occur.
Every marker type has positive mass. Thus, for every \(i\), some state must contain positive mass of \(M_i\).
No stable occupied coalition can contain two distinct marker colors. Indeed, every marker in such a coalition ranks it in the lowest category and strictly prefers its pure-type singleton state.
Consequently, states containing different marker types must be distinct. Since there are \(\omega\) positive-mass marker types, at least \(\omega\) states are required. \(\square\)
Because the constructed bound is exactly \(\omega\), every stable feasible allocation must therefore satisfy all of the following:
If the unique state of \(M_i\) is an occupied coalition, it must be one of \(M_i\)'s highest-ranked coalitions. Otherwise \(M_i\) would strictly prefer its singleton state. Since \(S_i=\{s^i\}\) and the entire mass of \(M_i\) is \(1\), that coalition contains normal mass exactly \(s^i_j\) of every type \(G_j\).
Assume \(\mathcal C'\subseteq\mathcal C\) is an exact cover.
For every \(C_i\in\mathcal C'\), create one coalition containing the entire mass of \(M_i\) and normal masses prescribed by \(s^i\). Thus its mass vector satisfies
\[ x_{G_j}=s^i_jx_{M_i}=s^i_j. \]
For every \(C_i\notin\mathcal C'\), place the entire mass of \(M_i\) in its pure-type singleton state.
Because \(\mathcal C'\) is an exact cover, each normal type \(G_j\) is assigned total mass exactly \(1=b_j\). The allocation uses one state for every marker, hence exactly \(\omega\) states.
Every selected marker is in a highest-ranked coalition. Every unselected marker is in its singleton state, and every occupied coalition contains a different marker color, so none is attractive to it. Every normal type lies in a coalition with exactly one marker color, its highest-ranked category. Hence there is no strictly profitable price-taking deviation, and the allocation is stable.
Assume a stable allocation using at most \(\omega\) states exists.
By the structural lemma it uses exactly \(\omega\) states, one for each marker, and has no additional normal-only or normal-singleton state.
Let \(I\subseteq\{1,\ldots,\omega\}\) contain precisely those indices for which \(M_i\) is assigned to an occupied coalition rather than its singleton state. The unique coalition containing \(M_i\), for \(i\in I\), contains its entire marker mass \(1\). Stability forces this coalition to satisfy the unique ratio vector \(s^i\). Therefore its mass of normal type \(G_j\) is exactly \(s^i_j\).
All normal mass must occur in these coalitions. Applying the mass-balance equation for \(G_j\) gives
\[ 1=b_j=\sum_{i\in I}s^i_j. \]
Thus every element \(u_j\) belongs to exactly one set \(C_i\) with \(i\in I\). Consequently, \(\{C_i:i\in I\}\) is an exact cover.
The constructed stable allocation exists if and only if the Exact Cover by 3-Sets instance is positive. Hence the decision problem is \(\mathrm{NP\text{-}hard}\), even under the stated binary restrictions. In particular, it cannot be polynomial-time solvable unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction from Exact Cover by 3-Sets is substantively correct. The support bound forces exactly one state per marker type, which makes the selected marker coalitions correspond bijectively to an exact cover. No major logical gaps were found.
There is one minor overstatement concerning the numerical data of the constructed instance.
These deductions are valid.
The statement “all numerical data are in \(\{0,1\}\)” is literally false because the support bound is \(\rho_{\geq1}=\omega\), which need not be binary-valued. The intended restriction is evidently that all type masses and all coordinates appearing in the sets \(S_i\) lie in \(\{0,1\}\). This does not affect the reduction or its NP-hardness conclusion.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.