Answer: Both core-existence and strict-core-existence are \(\Sigma_2^p\)-hard, hence \(\mathrm{NP}\)-hard.
Theorem 6.1 — class: hardness
Given a finite type set \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), and a symmetric rational valuation matrix \(W=(w_{ts})\), decide whether the atomless population admits a measurable partition into coalitions with no positive-mass core block (or strict-core block). A type-\(t\) agent in a coalition with type-mass vector \(q\) has utility \(u_t(q)=\sum_{s\in T}w_{ts}q_s\); a core block makes its members strictly better off, while a strict-core block makes them weakly better off and has positive mass of strict improvers.
A society is given by its support: a nonempty list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). The support size counts listed types, not possible types. Input also includes a symmetric matrix \(W\in\mathbb Q^{\tau\times\tau}\), with arbitrary signs and unrestricted diagonal. Let \(m:=|T|=\tau\) and \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Realize the population as disjoint Lebesgue intervals \(X_t\) of lengths \(\mu_t\), with measure \(\lambda\). For any measurable coalition \(C\), define \(q_t(C)=\lambda(C\cap X_t)\) and \(u_t(C)=\sum_s w_{ts}q_s(C)\); these are absolute masses, not within-coalition proportions.
An outcome \(\pi\) is a partition into nonempty measurable coalitions such that \(x\mapsto q(\pi(x))\) is measurable. There is no bound on the number of coalitions; null coalitions, including singletons, are allowed, and coalition masses may be real. Types may split across coalitions.
A block is any measurable \(S\subseteq X\) with \(\lambda(S)>0\), drawing members from any existing coalitions. A core block satisfies \(u_t(S)>u_t(\pi(x))\) for almost every \(x\in S\cap X_t\), for every \(t\). A strict-core block satisfies the corresponding weak inequalities almost everywhere, with a positive-measure set satisfying strict inequality. Utilities are nontransferable; ties mean indifference. Stability means absence of the respective blocks.
For each notion separately, is deciding whether a stable outcome exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite symmetric additive hedonic games, core-existence and strict-core-existence are \(\Sigma_2^p\)-complete, with hardness even when each agent values at most \(10\) other agents nonzero ([Peters](https://arxiv.org/pdf/1509.02333)).
No result settling either existence problem for exactly the atomless model above was located in the literature search.
Both core-existence and strict-core-existence are \(\mathrm{NP}\)-hard. In fact, both are \(\Sigma_2^p\)-hard.
This holds even with equal dyadic masses, a common positive diagonal, and at most \(10\) nonzero off-diagonal entries per row. The proof below allows arbitrary measurable partitions, null coalitions, and real coalition masses.
We use the following property of the single reduction in Peters’s proof of Theorem 2. It maps an instance of a \(\Sigma_2^p\)-complete quantified-formula problem to a finite symmetric additive hedonic game with integer valuations such that:
Moreover, every agent has at most \(10\) nonzero valuations of other agents, each of absolute value at most \(100\). These properties follow from the equivalence of conditions (i), (ii), and (iii) in that proof and its valuation table. [Peters, Theorem 2 and proof, pp. 7–12](https://arxiv.org/pdf/1509.02333).
Write the resulting game’s valuation matrix as \(A=(a_{ts})\), with \(a_{tt}=0\). For a finite coalition \(B\) containing \(t\), define its utility by
\( v_t(B)=\sum_{s\in B\setminus\{t\}}a_{ts}. \)
If the game initially has \(n\) agents, pad it with isolated dummy agents to obtain \(N\) agents, where \(N\) is the smallest power of two satisfying \(N\ge n\). Thus \(N<2n\).
Padding preserves both existence questions. For the forward direction, extend a stable partition by putting each dummy in a singleton. A core block cannot contain a dummy, because its utility is always zero. A strict-core block must contain a strictly improving original agent; deleting its dummy members leaves a strict-core block in the original game. Conversely, restricting a padded stable partition to the original agents preserves their utilities, so any original block would also block the padded partition.
Hence the two source properties above remain valid after padding.
Set
\( R=\max\left\{1,\max_t\sum_{s\ne t}|a_{ts}|\right\}, \qquad H=4R^2+4R+1. \)
In particular,
\( H>3R,\qquad R/H<1/2,\qquad 2R^2/H<1. \)
Create one type for each padded finite agent, with
\( \mu_t=1/N,\qquad w_{tt}=NH,\qquad w_{ts}=Na_{ts}\quad(t\ne s). \)
These masses are positive dyadic rationals and sum to one. The matrix \(W\) is symmetric and integral.
For any measurable coalition \(C\), introduce the rescaled mass
\( z_t(C)=Nq_t(C)\in[0,1]. \)
The utility prescribed by the question is then exactly
\( u_t(C)=Hz_t(C)+\sum_{s\ne t}a_{ts}z_s(C). \)
Consequently, for every coalition \(C\),
\( \left|\sum_{s\ne t}a_{ts}z_s(C)\right|\le R. \)
We prove two implications:
Together with the source reduction, these suffice for both hardness results.
Let \(P\) be a strict-core-stable partition of the finite game. Construct the atomless outcome whose coalitions are
\( C_D=\bigcup_{t\in D}X_t \quad\text{for }D\in P. \)
This is an admissible measurable outcome. Every member of type \(t\) receives the constant utility
\( H+v_t(P(t)), \)
where \(P(t)\) is the finite coalition containing \(t\).
Suppose, towards a contradiction, that a measurable coalition \(S\) strictly-core blocks this outcome. Define
\( B=\{t:q_t(S)>0\},\qquad z_t=Nq_t(S),\qquad \delta_t=1-z_t\quad(t\in B). \)
Because \(S\) has positive measure, \(B\) is nonempty. The utility gain for its type-\(t\) members is the constant
\( g_t=-H\delta_t+d_t-\sum_{s\in B\setminus\{t\}}a_{ts}\delta_s, \)
where
\( d_t=v_t(B)-v_t(P(t))\in\mathbb Z. \)
The strict-core blocking conditions therefore say that \(g_t\ge0\) for every \(t\in B\), and \(g_t>0\) for at least one such type.
Weak improvement for type \(t\) implies
\( H\delta_t \le \sum_{s\in B\setminus\{t\}}a_{ts}z_s-v_t(P(t)) \le 2R. \)
Thus \(\delta_t\le2R/H\) for every \(t\in B\), and consequently
\( \left|\sum_{s\in B\setminus\{t\}}a_{ts}\delta_s\right| \le 2R^2/H<1. \)
If \(d_t<0\), its integrality gives \(d_t\le-1\), and hence
\( g_t\le-1+2R^2/H<0, \)
a contradiction. Therefore \(d_t\ge0\) for every \(t\in B\).
Strict-core stability of the finite partition \(P\) now implies that every \(d_t\) is zero: otherwise \(B\) itself would be a finite strict-core block.
With all \(d_t=0\), summing the gains gives
\( \sum_{t\in B}g_t = -\sum_{s\in B}\delta_s \left(H+\sum_{t\in B\setminus\{s\}}a_{ts}\right). \)
By symmetry and the definition of \(R\),
\( H+\sum_{t\in B\setminus\{s\}}a_{ts}\ge H-R>0. \)
The left side is nonnegative because every \(g_t\ge0\). The right side is nonpositive, and is strictly negative if any \(\delta_s>0\). Therefore every \(\delta_s=0\), which also gives every \(g_t=0\). This contradicts the required strict improvement.
We have proved that the lifted atomless outcome is strict-core-stable. In particular, it is core-stable.
Let \(\pi\) be any core-stable outcome of the constructed atomless society. We impose no restriction on its number of coalitions or on their masses.
For each type \(t\), the pure-type coalition \(X_t\) gives utility \(H\). Therefore the measurable set
\( E_t=\{x\in X_t:u_t(\pi(x))\ge H\} \)
must have positive measure. Otherwise \(X_t\) would core-block \(\pi\).
Choose a member of \(E_t\), and denote its incumbent coalition by \(C_t\). The bound on off-diagonal utility gives
\( H\le u_t(C_t)\le Hz_t(C_t)+R, \)
so
\( z_t(C_t)\ge1-R/H>1/2. \)
Two distinct coalitions cannot both contain more than half of type \(t\)’s mass, because they are disjoint. Thus \(C_t\) is unique.
Moreover, every other coalition \(C\ne C_t\) satisfies
\( z_t(C)\le1-z_t(C_t)\le R/H. \)
It follows that any type-\(t\) member outside \(C_t\) has incumbent utility at most
\( H(R/H)+R=2R. \)
These arguments apply equally to positive-measure and null incumbent coalitions.
Group finite agents according to their distinguished coalitions:
\( P(t)=\{s:C_s=C_t\}. \)
Equality of the coalitions \(C_t\) defines an equivalence relation, so this defines a finite partition.
For any \(s\ne t\):
Hence
\( \left| \sum_{s\ne t}a_{ts}z_s(C_t)-v_t(P(t)) \right| \le R^2/H. \)
Suppose \(P\) has a finite core block \(B\). Since utilities are integral,
\( v_t(B)-v_t(P(t))\ge1 \quad\text{for every }t\in B. \)
Consider the measurable, positive-mass coalition
\( S_B=\bigcup_{t\in B}X_t. \)
Its type-\(t\) utility is \(H+v_t(B)\).
For a type-\(t\) member currently in \(C_t\), the gain is at least
\( H(1-z_t(C_t)) +v_t(B)-v_t(P(t)) -R^2/H \ge1-R^2/H>0. \)
For a type-\(t\) member outside \(C_t\), incumbent utility is at most \(2R\), whereas its utility in \(S_B\) is at least
\( H-R>2R. \)
Thus every participating type strictly improves throughout \(S_B\). This is a core block of \(\pi\), a contradiction.
Therefore the extracted finite partition \(P\) is core-stable.
Apply this construction to the padded games from the finite source reduction.
For a true source formula, the finite game has a strict-core-stable partition. Section 3 produces an atomless strict-core-stable outcome, which is also core-stable.
For a false source formula, the finite game has no core-stable partition. Section 4 therefore rules out every atomless core-stable outcome. It also rules out strict-core-stable outcomes, because strict-core stability implies core stability.
Consequently, on the constructed instances,
\( \text{source formula is true} \iff \text{an atomless core-stable outcome exists} \iff \text{an atomless strict-core-stable outcome exists}. \)
The reduction is polynomial in the binary encoding. Specifically, \(m=\tau=N<2n\). For the sparse source family, \(R\le1000\), so \(H\) is bounded by an absolute constant. All nonzero entries of \(W\), and all masses, have \(O(\log(m+1))\) bits. Writing the explicit matrix takes \(O(m^2\log(m+1))\) bit operations and produces total input length \(L=O(m^2\log(m+1))\). The source construction is itself polynomial-time.
Thus both existence problems are \(\Sigma_2^p\)-hard under polynomial-time many-one reductions. In particular, neither admits a decision algorithm running in \((m+\tau+L)^{O(1)}\) time unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument establishes \(\Sigma_2^p\)-hardness, hence \(\mathrm{NP}\)-hardness, for both existence problems in the stated atomless model. I found no substantive mathematical gap. One heading overstates the concentration result proved beneath it; correcting that wording requires no new mathematics.
The proof needs a single reduction with both properties:
Separate hardness theorems would not suffice. The cited source supplies the stronger joint property: Peters’s proof of Theorem 2 explicitly establishes equivalence between formula truth, strict-core existence, and core existence. Table 1 also specifies symmetric integer valuations, permits replacing its negative-infinity notation by \(-100\), and states the bound of ten nonzero valuations per agent. Thus the source invoked here has the required hypotheses and quantitative bounds. [Peters, Theorem 2 and Table 1, pp. 8–12](https://arxiv.org/pdf/1509.02333).
Padding is valid for both notions:
The power-of-two choice satisfies \(n\le N<2n\), including \(n=1\).
Assessment: Correct.
The construction satisfies every input restriction:
The rescaling is exact:
\[
u_t(C)=Hz_t(C)+\sum_{s\ne t}a_{ts}z_s(C).
\]
Since \(0\le z_s(C)\le1\), the off-diagonal contribution has absolute value at most \(R\).
For \(R\ge1\), the specified constant satisfies
\[
H=(2R+1)^2>3R,\qquad \frac RH<\frac12,\qquad \frac{2R^2}{H}<1.
\]
The later inequalities \(H-R>2R\) and \(R^2/H<1\) therefore also hold.
Assessment: Correct.
The lifted outcome is admissible: it is a finite partition into nonempty measurable unions of type intervals, and its coalition-mass map is measurable.
For a proposed atomless strict-core block, the set \(B\) contains precisely the types participating with positive measure. Within each such type, both incumbent and proposed utilities are constant. Consequently, the almost-everywhere blocking conditions reduce exactly to \(g_t\ge0\) for every \(t\in B\), with \(g_t>0\) for at least one participating type. Members belonging to types represented only on null sets do not affect this reduction.
The gain formula is correct:
\[
g_t=-H\delta_t+d_t-\sum_{s\in B\setminus\{t\}}a_{ts}\delta_s.
\]
Weak improvement bounds every missing fraction by \(2R/H\). Hence the perturbation term has absolute value at most \(2R^2/H<1\). If the integer \(d_t\) were negative, then
\[
g_t\le-1+\frac{2R^2}{H}<0,
\]
contradicting weak improvement. Thus all \(d_t\) are nonnegative.
Finite strict-core stability then forces all \(d_t\) to vanish: otherwise \(B\) itself would be a finite strict-core block.
The tie-case calculation is also correct. Reordering the finite sum gives
\[
\sum_{t\in B}g_t
=
-\sum_{s\in B}\delta_s
\left(H+\sum_{t\in B\setminus\{s\}}a_{ts}\right).
\]
Symmetry supplies the column bound needed to make every coefficient at least \(H-R>0\). Nonnegative gains therefore force every \(\delta_s=0\), and consequently every gain is zero. This contradicts strict improvement on positive measure.
Assessment: Correct, including fractional participation and ties.
The set \(E_t\) is measurable because the outcome’s coalition-mass map is measurable and utility is its linear composition. If \(E_t\) had measure zero, the pure-type coalition \(X_t\) would strictly improve utility almost everywhere, so core stability indeed implies \(\lambda(E_t)>0\).
Choosing a member of \(E_t\) yields
\[
z_t(C_t)\ge1-\frac RH>\frac12.
\]
Disjointness makes this distinguished coalition unique. Every other coalition contains rescaled type-\(t\) mass at most \(R/H\), giving incumbent utility at most \(2R\) outside \(C_t\). These bounds remain valid for null coalitions.
There is one minor wording issue:
Minor — Section 4 heading, “Each type has a unique coalition containing almost all its mass.”
The argument proves concentration of at least the fraction \(1-R/H\). It does not prove that the remaining mass is zero. If “almost all” means “except a null set,” the heading overstates the result.
Minimum clarification: Replace “almost all its mass” with “at least the fraction \(1-R/H\) of its mass.” The subsequent proof already uses the correct quantitative bound.
The relation \(C_s=C_t\) defines a finite partition. For every coordinate, the deviation from its corresponding membership indicator is at most \(R/H\). The stated estimate
\[
\left|
\sum_{s\ne t}a_{ts}z_s(C_t)-v_t(P(t))
\right|
\le\frac{R^2}{H}
\]
follows correctly.
If \(B\) is a finite core block, integrality gives an improvement of at least one for each participating agent. The coalition \(S_B\) then gives:
Thus \(S_B\) is indeed an atomless core block. The argument does not assume a finite or countable incumbent partition, nor does it assume rational incumbent coalition masses.
Assessment: Correct apart from the heading.
The two established implications suffice for both reductions. True source instances yield atomless strict-core stability and therefore core stability. False source instances exclude atomless core stability and therefore also exclude strict-core stability.
For the source family, \(R\le1000\), so \(H\) is an absolute constant. Masses and nonzero matrix entries have \(O(\log(m+1))\) bits. With \(m=\tau=N\), the stated explicit-matrix construction time and output-length bounds,
\[
O(m^2\log(m+1)),
\]
are valid polynomial upper bounds. Together with the polynomial source construction, this establishes polynomial-time many-one reductions.
The conclusion concerns hardness only; it does not establish membership or completeness for either atomless problem. That is sufficient to answer the requested complexity alternatives.
⟨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.