Answer: \(\mathrm{NP}\text{-hard}\), already for one template with \(\lambda_1=1\); decidable in time \(O(\tau\,8^mL^3)\).
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCORE-EXISTENCE is NP-hard even for graphi- cal hedonic games of treewidth 2 that are given by an HC-net.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many connected graphical hedonic-game templates \(H_j\), each with an HC-net representation and treewidth at most \(2\), and positive rational copy intensities \(\lambda_j\), consider a continuum of copies of each template. Does there exist a measurable assignment of an ordinary integral partition to each copy such that no measurable coalition of positive population mass makes every member strictly prefer that coalition to their assigned coalition? Equivalently, does every positive-mass template admit a core-stable local partition?
Input consists of finitely many nonempty templates \(H_j\), each with a supplied connected dependency graph \(G_j=(N_j,E_j)\) of treewidth at most \(2\), with no degree bound.
Each vertex has an HC-net: an explicitly listed collection of Boolean formulas over vertex-presence variables with signed binary-rational weights; its utility \(u_{j,i}(S)\) is the sum of weights of formulas satisfied by \(S\). Utilities are promised to depend only on \(S\cap(\{i\}\cup\Gamma_{G_j}(i))\); equal utilities mean indifference.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types are labeled roles \((j,i)\), each of mass \(\lambda_j>0\); \(\tau=\sum_j|N_j|\) is the support size, not the number of possible types. Masses need not sum to \(1\).
The population is \(\Omega=\bigsqcup_j(\{j\}\times[0,\lambda_j]\times N_j)\), with Lebesgue measure on the copy coordinate and counting measure on roles. Neighbors belong to the same copy only.
An outcome is a measurable map \(t\mapsto\pi_j(t)\) into the finite set of ordinary integral partitions of \(N_j\), equipped with its discrete sigma-algebra; partition blocks need not be connected.
For a measurable coalition \(B\subseteq\Omega\), write \(B_{j,t}=\{i:(j,t,i)\in B\}\). It blocks precisely when \(\mu(B)>0\) and \(u_{j,i}(B_{j,t})>u_{j,i}(\pi_j(t)(i))\) for every \((j,t,i)\in B\). Coalitions may span copies; every nonempty local subset is allowed, including singletons.
Is existence of an outcome admitting no such blocking coalition in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m=\max_j|N_j|\), \(\tau\), and the total input bit length \(L\), including formulas, weights, graphs, and masses.
Discrete core existence for HC-net graphical hedonic games is NP-hard already on connected graphs of treewidth two. [Source](https://dominik-peters.de/publications/hedonic-treewidth.pdf)
No published result settling this exact continuum model was located.
The problem is \(\mathrm{NP}\)-hard, already with one template and mass \(\lambda_1=1\).
More precisely, an unblocked measurable outcome exists if and only if every template has a nonempty ordinary discrete core. The continuum therefore preserves the discrete existence question.
A deterministic algorithm decides existence and constructs an outcome when one exists in time
\[
O\!\left(\tau\,8^m L^3\right).
\]
Thus the problem is fixed-parameter tractable in \(m\), but a polynomial-time algorithm for unrestricted \(m\) would imply \(\mathrm{P}=\mathrm{NP}\).
For each template \(j\), let \(\mathcal P_j\) be the finite set of partitions of \(N_j\). Define its discrete core by
\[
\mathcal C_j=
\left\{
p\in\mathcal P_j:
\text{there is no nonempty }S\subseteq N_j
\text{ with }u_{j,i}(S)>u_{j,i}(p(i))
\text{ for every }i\in S
\right\}.
\]
This definition allows every nonempty subset, including singletons.
Lemma. A measurable outcome \(\pi=(\pi_j)_j\) admits no blocking coalition exactly when \(\pi_j(t)\in\mathcal C_j\) for Lebesgue-almost every \(t\in[0,\lambda_j]\), for every \(j\).
Proof. Fix \(j\). For each nonempty \(S\subseteq N_j\), put
\[
D_{j,S}=
\left\{
t\in[0,\lambda_j]:
u_{j,i}(S)>u_{j,i}(\pi_j(t)(i))
\text{ for every }i\in S
\right\}.
\]
This set is measurable: it is the inverse image under the measurable map \(\pi_j\) of a subset of the finite discrete space \(\mathcal P_j\).
The set of copies with an unstable partition is
\[
E_j=\{t:\pi_j(t)\notin\mathcal C_j\}
=\bigcup_{\varnothing\ne S\subseteq N_j}D_{j,S}.
\]
This union is finite. Consequently, if \(E_j\) has positive Lebesgue measure, some \(D_{j,S}\) has positive measure. Then
\[
B=\{(j,t,i):t\in D_{j,S},\ i\in S\}
\]
is measurable, has measure \(|S|\,\operatorname{Leb}(D_{j,S})>0\), and satisfies \(B_{j,t}=S\) on \(D_{j,S}\). Every member strictly improves, so \(B\) blocks.
Conversely, suppose every \(E_j\) is null, and suppose a measurable coalition \(B\) satisfies the required strict improvement for every member. Whenever \(B_{j,t}\ne\varnothing\), that subset blocks the discrete partition \(\pi_j(t)\). Hence \(t\in E_j\). Therefore
\[
\mu(B)
=\sum_j\sum_{i\in N_j}
\operatorname{Leb}\{t:(j,t,i)\in B\}
\le
\sum_j |N_j|\,\operatorname{Leb}(E_j)
=0.
\]
Thus \(B\) cannot be a blocking coalition. This also handles coalitions spanning several copies or templates. \(\square\)
Corollary. An unblocked measurable outcome exists exactly when \(\mathcal C_j\ne\varnothing\) for every \(j\).
Proof. If an unblocked outcome exists, the lemma gives a full-measure set of stable copies in each interval. Since \(\lambda_j>0\), this set is nonempty, so \(\mathcal C_j\ne\varnothing\).
Conversely, choose \(p_j\in\mathcal C_j\) for each template and set \(\pi_j(t)=p_j\) everywhere. These constant maps are measurable and, by the lemma, form an unblocked outcome. \(\square\)
The known discrete result is that core existence is \(\mathrm{NP}\)-hard for HC-net graphical hedonic games of treewidth two. The construction in Theorem 7 uses a triangle with leaves attached to one vertex, so its supplied dependency graph is connected; its HC-net weights are signed integers. [Peters, *Graphical Hedonic Games of Bounded Treewidth*, Theorem 7](https://dominik-peters.de/publications/hedonic-treewidth.pdf)
Take an instance from this hard family and construct a continuum instance with:
All promises hold. The graph remains connected with treewidth at most two. Signed integer weights are allowed binary-rational weights. Utilities retain their neighborhood dependence. Ordinary partitions, strict improvement, and singleton deviations are exactly those used in discrete core stability.
By the corollary, the continuum instance admits an unblocked outcome exactly when the original discrete game has a core-stable partition. This is a polynomial-time many-one reduction.
If the discrete input has bit length \(D\) and \(n\) roles, the transformation takes \(O(D+n\log(n+1))\) time and produces that order of encoding length under ordinary explicit labeling. Its parameters satisfy \(m=\tau=n\). No population normalization is needed: the resulting total mass is \(n\), which the task explicitly permits.
Write \(n_j=|N_j|\) and \(e_j=|E_j|\).
Connected partitions suffice. Given any partition \(p\), split each block into its connected components in \(G_j\), obtaining \(p'\). For every vertex \(i\),
\[
p(i)\cap(\{i\}\cup\Gamma_{G_j}(i))
=
p'(i)\cap(\{i\}\cup\Gamma_{G_j}(i)).
\]
Indeed, any neighbor of \(i\) lying in its original block belongs to the same connected component as \(i\). The locality promise consequently gives \(u_{j,i}(p(i))=u_{j,i}(p'(i))\). Since every blocking comparison uses these baseline utilities, \(p\) and \(p'\) have exactly the same blocking subsets. Core existence can therefore be tested using connected partitions.
Enumerating candidate partitions. Enumerate all edge subsets \(F\subseteq E_j\), and use the connected components of \((N_j,F)\) as a candidate partition. Every connected partition occurs: choose a spanning tree within each of its blocks and let \(F\) be the union of those trees. Duplicate candidates cause no difficulty.
For each candidate, enumerate every nonempty \(S\subseteq N_j\). Reject the candidate if
\[
u_{j,i}(S)>u_{j,i}(p(i))
\quad\text{for every }i\in S.
\]
Accept the template if some candidate survives every check.
Bounding the enumeration. A graph of treewidth at most two has a vertex of degree at most two in every nonempty induced subgraph. To verify this, take a width-two tree decomposition and repeatedly remove any leaf bag contained in its adjacent bag. If one bag remains, there are at most three vertices. Otherwise, a leaf bag contains a vertex absent from its adjacent bag. Connectedness of that vertex’s bag occurrences implies that it occurs only in the leaf bag, so all its neighbors lie there. Its degree is at most two. Restricting the decomposition proves the same statement for induced subgraphs.
Removing such vertices successively counts each edge once and gives \(e_j\le 2n_j\). Thus the algorithm examines at most
\[
2^{e_j}2^{n_j}\le 8^{n_j}
\]
candidate-and-coalition pairs per template.
Exact arithmetic. Formula evaluation is polynomial in the explicit formula length. Rational sums and comparisons can also be performed exactly in polynomial bit time: the product of all input denominators has \(O(L)\) bits, and all relevant sums have \(O(L)\)-bit numerators and denominators. Using ordinary schoolbook arithmetic, \(O(L^3)\) is a conservative bound for evaluating the needed utilities and comparisons for one pair.
The total running time is therefore
\[
O\!\left(
L^3\sum_j2^{e_j+n_j}
\right)
\subseteq
O\!\left(\tau\,8^mL^3\right),
\]
because there are at most \(\tau\) nonempty templates. Graph processing and reading the masses fit within this bound. If every template is accepted, the selected partitions specify a valid constant measurable outcome.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task. The continuum equivalence is correct, the cited hardness result applies to the stated input model, and the exponential algorithm has the claimed bit-complexity bound. I found no major or minor mathematical issues.
The definition of \(\mathcal C_j\) matches the task: blocking requires strict improvement for every member of a nonempty subset. It includes singleton deviations and imposes no connectedness restriction.
Each \(D_{j,S}\) is measurable because the blocking condition selects a subset of the finite discrete partition space, and \(\pi_j\) is measurable. The equality
\[
E_j=\bigcup_{\varnothing\ne S\subseteq N_j}D_{j,S}
\]
follows directly from the discrete core definition. The union is finite, so positive measure of \(E_j\) implies positive measure of at least one \(D_{j,S}\). There is no measurable-selection gap.
The constructed coalition consists of the same roles \(S\) at precisely the coordinates in \(D_{j,S}\). Its role sections are measurable, and its measure is correctly calculated as \(|S|\operatorname{Leb}(D_{j,S})>0\).
At every included coordinate its local subset equals \(S\). The definition of \(D_{j,S}\) therefore ensures strict improvement for every member, as required by the task, rather than merely almost every member.
If a coalition satisfies the strict-improvement condition and \(B_{j,t}\) is nonempty, that local subset is a discrete blocking coalition. Consequently \(t\in E_j\).
Every role section of \(B\) is therefore contained in the corresponding null set \(E_j\). The measure formula and inequality in the proof are valid for Lebesgue measure on coordinates and counting measure on roles. There are finitely many templates and roles, so the resulting sum is zero.
This argument covers coalitions spanning multiple copies and templates. It also correctly allows unstable partitions at null sets of coordinates: deviations supported there cannot have positive population measure.
The assumption \(\lambda_j>0\) is used correctly. A full-measure subset of \([0,\lambda_j]\) is nonempty, so an unblocked outcome supplies at least one discrete core partition for every template.
Conversely, selecting one core partition for each of finitely many templates gives measurable constant maps. The preceding lemma establishes their stability. No normalization of masses is needed.
I checked [Peters, Theorem 7 and the accompanying definitions](https://dominik-peters.de/publications/hedonic-treewidth.pdf). The theorem establishes NP-hardness of core existence for HC-net graphical hedonic games of treewidth two. Its construction has a triangle with variable-agent leaves attached to one triangle vertex, hence a connected graph. The listed weights are signed integers, and the rules satisfy numerical neighborhood locality. The paper’s core definition uses strict improvement by every member of a nonempty coalition.
Thus the cited family meets the task’s promises, including the stronger numerical utility-locality requirement. Copying it into one template with mass \(\lambda_1=1\) preserves utilities, partitions, and blocking comparisons. The proved equivalence supplies both directions of the many-one reduction.
The stated transformation time and encoding size are valid under the explicitly stated ordinary labeling convention. The parameter identities \(m=\tau=n\) and total population mass \(n\) are also correct. The argument establishes NP-hardness; it does not claim NP membership or NP-completeness.
Splitting an original block into its induced connected components preserves every vertex’s intersection with its closed neighborhood. Any neighbor remaining in the original block is connected to that vertex by their edge and consequently remains in its component.
The locality promise therefore preserves each baseline utility exactly. Since the utility of a proposed blocking subset is independent of the current partition, every blocking comparison is preserved. This justifies restricting candidate partitions while still checking all nonempty blocking subsets.
Components of an edge subset always form a connected partition. Conversely, spanning trees within the blocks of any connected partition produce an edge subset whose components are exactly those blocks. Duplicate candidates do not affect correctness.
The tree-decomposition argument correctly proves the existence of a vertex of degree at most two in every nonempty induced subgraph. Pruning a contained leaf bag preserves a valid decomposition. In the remaining multi-bag case, the selected vertex occurs only in its leaf bag, so every neighbor lies in that bag. The one-bag case also gives degree at most two.
Successive deletion therefore yields \(e_j\le 2n_j\), including the single-vertex case. The number of candidate-and-coalition pairs is bounded by
\[
2^{e_j}(2^{n_j}-1)\le 2^{e_j+n_j}\le 8^{n_j}.
\]
No supplied tree decomposition is needed by the enumeration algorithm.
With explicit Boolean formulas, evaluation is polynomial in their listed length. The product of input denominators has \(O(L)\) bits because their aggregate encoded length is at most \(L\). Numerators of the relevant sums also have \(O(L)\) bits, including the additional bits needed for summation.
There are at most \(O(L)\) listed weights. Schoolbook arithmetic on these bounded-length integers supports the conservative \(O(L^3)\) cost for all needed utility evaluations and comparisons in one pair. Candidate construction and subset processing fit within this bound.
Summing over templates gives the claimed
\[
O\!\left(L^3\sum_j2^{e_j+n_j}\right)
\subseteq O(\tau\,8^mL^3),
\]
since nonempty templates number at most \(\tau\). Reading and processing masses are covered by \(L\). Selected partitions provide a finite description of the constant measurable outcome.
Thus the FPT claim in \(m\) and the stated implication that an unrestricted polynomial-time algorithm would yield \(\mathrm P=\mathrm{NP}\) both follow.
No additional clarification or mathematical repair is required.
⟨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.