Answer: \(\mathrm{NP}\)-hard
Theorem 2 — class: hardness
Given a finite type set \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), and rational symmetric values \(a_{ts}=a_{st}\), represent the population by measurable type sets \(I_t\subseteq[0,1]\) with measure \(\mu_t\). For a measurable coalition \(C\), a member of type \(t\) receives \(u_t(C)=\sum_{s\in T}a_{ts}\lambda(C\cap I_s)\). Decide whether there is a measurable partition of \([0,1]\), up to measure zero, into positive-measure coalitions such that no positive-measure measurable group \(D\) has all its members weakly prefer \(D\) to their current coalition and a positive measure of its members strictly prefer it.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\), and a binary-rational symmetric matrix \(a_{ts}=a_{st}\). Values may have either sign, including diagonal entries. Let \(L\) be the total input bit length; running times are measured in \(\tau,L\), with no separate \(m\) parameter in this model. Support size means the number of listed positive-mass types, not the number of possible types.
Represent the society by disjoint Lebesgue-measurable sets \(I_t\) partitioning \([0,1]\) up to null sets, with \(\lambda(I_t)=\mu_t\). A type may be split among coalitions. For measurable \(C\), a member of type \(t\) receives \(u_t(C)=\sum_{s\in T}a_{ts}\lambda(C\cap I_s)\); preferences compare these utilities, with equality giving indifference.
An admissible partition \(\pi\) has finitely or countably many measurable positive-measure coalitions covering the society up to null sets; write \(\pi(x)\) for the coalition containing \(x\), and \(t(x)\) for its type.
A measurable group \(D\) weakly blocks \(\pi\) if \(\lambda(D)>0\), \(u_{t(x)}(D)\geq u_{t(x)}(\pi(x))\) for almost every \(x\in D\), and the subset satisfying strict inequality has positive measure. Groups may draw members from any coalitions, without consent from those left behind. A partition is strict-core stable if no such group exists.
Is deciding whether this society admits a strict-core stable admissible partition in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite symmetric additively separable hedonic games, existence of a core-stable or strict-core stable partition is strongly \(\mathrm{NP}\)-hard ([Aziz–Brandt–Seedig](https://www.ifaamas.org/Proceedings/aamas2011/papers/C1_R45.pdf)). No result settling the exact continuum decision problem above was located.
We give a polynomial-time reduction from strict-core existence in finite symmetric additively separable hedonic games. The reduction handles both arbitrary splitting of types and countably infinite admissible partitions.
The hardness holds even when all masses are equal dyadic rationals and all diagonal entries equal one positive integer.
Let the finite players be \(\{1,\ldots,n\}\), with symmetric integer weights \(w_{ij}=w_{ji}\) and \(w_{ii}=0\). A player \(i\) receives utility
\(\displaystyle v_i(B)=\sum_{j\in B\setminus\{i\}}w_{ij}\)
in coalition \(B\). A nonempty set \(S\) weakly blocks a partition \(P\) if every \(i\in S\) satisfies \(v_i(S)\geq v_i(P(i))\), with strict inequality for at least one player.
Deciding whether such a game has a strict-core stable partition is \(\mathrm{NP}\)-hard by [Aziz–Brandt–Seedig, Theorem 2](https://www.ifaamas.org/Proceedings/aamas2011/papers/C1_R45.pdf). Their theorem applies to symmetric preferences and exactly this blocking notion. Integer weights suffice: multiplying rational weights by a common positive denominator preserves every preference comparison, and the product of the input denominators has polynomial binary encoding length.
We may additionally require \(n\) to be a power of two. Pad the game to the next power of two with players whose weights to every player are zero. This preserves strict-core existence:
Padding increases the number of players by less than a factor of two.
Set
\(\displaystyle W=\max\bigl(\{1\}\cup\{|w_{ij}|:i\neq j\}\bigr),\qquad M=4n^2W^2+1.\)
Create exactly \(\tau=n\) listed types, with
\(\displaystyle \mu_i=\frac1n,\qquad a_{ii}=M,\qquad a_{ij}=w_{ij}\quad(i\neq j).\)
The masses are positive dyadic rationals and sum to one. The matrix is symmetric. We shall use the inequalities
\(\displaystyle M>2(n-1)W,\qquad M>2(n-1)^2W^2,\qquad M>(n-1)W.\)
The construction has polynomial encoding length: \(M\) has \(O(\log n+\log W)\) bits, and there are \(n^2\) matrix entries. Its support size is exactly the number of listed positive-mass types.
Lemma. In any strict-core stable admissible partition, all coalitions containing a positive mass of a given type give that type the same utility.
Proof. Suppose coalitions \(C\) and \(C'\) both contain positive masses of type \(i\), and \(u_i(C)>u_i(C')\).
Choose measurable sets \(E\subseteq C\cap I_i\) and \(F\subseteq C'\cap I_i\) with the same positive measure. Such sets exist because Lebesgue measure is nonatomic. Define
\(\displaystyle D=(C\setminus E)\cup F.\)
The type-mass vector of \(D\) equals that of \(C\). Hence every retained member of \(C\) is indifferent between \(D\) and \(C\), while all members of \(F\) strictly improve. Thus \(D\) weakly blocks, a contradiction.
This proves equality for every pair of type-bearing coalitions. Because the partition is countable and covers almost all of \(I_i\), this common value is the utility of almost every member of type \(i\). \(\square\)
Lemma. In the constructed society, a strict-core stable admissible partition assigns almost all members of each type to one coalition.
Proof. Suppose type \(i\) has positive mass in at least two coalitions. At least one such coalition \(C\) satisfies
\(\displaystyle q_i:=\lambda(C\cap I_i)\leq\frac1{2n}.\)
For each type \(j\), put \(q_j=\lambda(C\cap I_j)\). Since \(q_j\leq 1/n\),
\(\displaystyle u_i(C)=Mq_i+\sum_{j\neq i}w_{ij}q_j \leq\frac{M}{2n}+\frac{(n-1)W}{n} <\frac Mn.\)
By the equal-treatment lemma, almost every member of type \(i\) receives this same utility. The group \(I_i\), consisting of the entire type, gives every participant utility \(M/n\). It therefore strictly improves almost every participant and weakly blocks. This is impossible. \(\square\)
Consequently, every stable admissible partition induces a finite partition \(P\) of the types. Indeed, each positive-measure coalition contains a positive mass of some type, and each type belongs to only one coalition up to null sets. There are therefore at most \(n\) coalitions.
For a coalition consisting of the full types in \(B\), each type \(i\in B\) receives
\(\displaystyle u_i(B)=\frac{M+v_i(B)}n.\)
Thus, if the induced finite partition \(P\) had a finite weak block \(S\), the measurable group \(\bigcup_{i\in S}I_i\) would weakly block the society partition. We have proved:
Continuum strict-core existence implies finite strict-core existence.
For the converse, let \(P\) be a strict-core stable finite partition. Form the society partition whose coalitions are
\(\displaystyle C_B=\bigcup_{i\in B}I_i\qquad(B\in P).\)
We prove this partition is stable against every measurable group.
Suppose, for a contradiction, that a measurable group \(D\) weakly blocks it. Define
\(\displaystyle x_i=n\lambda(D\cap I_i),\qquad S=\{i:x_i>0\}.\)
Then \(S\neq\varnothing\), and \(0<x_i\leq1\) for \(i\in S\). Write \(b_i=v_i(P(i))\). The scaled utility gain of a participant of type \(i\in S\) is
\(\displaystyle g_i=n\bigl(u_i(D)-u_i(C_{P(i)})\bigr) =Mx_i+\sum_{j\in S\setminus\{i\}}w_{ij}x_j-M-b_i.\)
The blocking conditions mean \(g_i\geq0\) for every \(i\in S\), with \(g_i>0\) for at least one such type. This follows because both current and proposed utilities are constant within each participating type, and that type has positive participating measure.
Put
\(\displaystyle h_i=1-x_i\quad(i\in S),\qquad \Delta_i=v_i(S)-b_i.\)
Each \(\Delta_i\) is an integer, and
\(\displaystyle g_i=\Delta_i-Mh_i-\sum_{j\in S\setminus\{i\}}w_{ij}h_j.\)
From \(g_i\geq0\), we obtain
\(\displaystyle Mh_i \leq\sum_{j\in S\setminus\{i\}}w_{ij}x_j-b_i \leq2(n-1)W.\)
The last inequality uses \(x_j\leq1\), \(|w_{ij}|\leq W\), and \(|b_i|\leq(n-1)W\). Hence
\(\displaystyle 0\leq h_i\leq\frac{2(n-1)W}{M}.\)
Rearranging the gain equation now gives
\(\displaystyle \Delta_i =g_i+Mh_i+\sum_{j\in S\setminus\{i\}}w_{ij}h_j \geq-\frac{2(n-1)^2W^2}{M} >-1.\)
Because \(\Delta_i\) is an integer, \(\Delta_i\geq0\) for every \(i\in S\).
If any \(\Delta_i\) were positive, \(S\) would weakly block the finite partition \(P\). Its stability therefore forces
\(\displaystyle \Delta_i=0\qquad\text{for every }i\in S.\)
Substituting these equalities into the gain equation yields
\(\displaystyle Mh_i+\sum_{j\in S\setminus\{i\}}w_{ij}h_j=-g_i\leq0 \qquad(i\in S).\)
If some \(h_i\) were positive, choose \(k\in S\) maximizing \(h_k\). Since \(0\leq h_j\leq h_k\),
\(\displaystyle Mh_k+\sum_{j\in S\setminus\{k\}}w_{kj}h_j \geq\bigl(M-(n-1)W\bigr)h_k >0,\)
contradicting the preceding inequality. Thus every \(h_i=0\). The gain equation then gives every \(g_i=0\), contradicting the required strict improvement.
No measurable weak block exists. We have proved:
Finite strict-core existence implies continuum strict-core existence.
The construction is a polynomial-time many-one reduction, with equivalence in both directions. Therefore deciding whether the society in the question admits a strict-core stable admissible partition is \(\mathrm{NP}\)-hard.
The positive diagonal is essential to this reduction: it forces stable types to remain intact, while its quantitative size rules out additional blocks using fractional type masses.
⟨structured verdict parsed — rendered above⟩
The argument is correct and establishes \(\mathrm{NP}\)-hardness for the exact continuum decision problem in USER_TASK. Both arbitrary splitting of types and countably infinite admissible partitions are addressed. I found no major or minor mathematical issues.
The cited theorem supplies the required source hardness: existence of a strict-core stable partition in finite symmetric additively separable hedonic games is strongly \(\mathrm{NP}\)-hard. The paper defines weak blocking using weak improvement for every participant and strict improvement for at least one, matching the prover’s definition. Its construction uses rational weights, so clearing denominators yields integer weights without changing preferences. [Aziz–Brandt–Seedig, definitions and Theorem 2](https://www.ifaamas.org/Proceedings/aamas2011/papers/C1_R45.pdf).
The denominator-clearing argument is valid. The bit length of the product of the denominators is bounded by the sum of their bit lengths, and multiplying weights by this positive integer preserves all utility comparisons and symmetry.
Padding with zero-weight dummy players preserves existence in both directions:
The next power of two is less than twice the original positive number of players. Thus padding has polynomial size.
The constructed society satisfies all input requirements:
For \(W\geq1\) and \(n\geq1\), the chosen value
\[
M=4n^2W^2+1
\]
satisfies all three displayed inequalities. Its binary length is \(O(\log n+\log W)\), so the construction can be computed and encoded in polynomial time. There is no hidden dependence on an additional population-size parameter.
The exchange argument is valid.
Nonatomicity permits equal positive-measure subsets \(E\) and \(F\) of the two type-bearing coalitions. Replacing \(E\) by \(F\) preserves every coordinate of the coalition’s type-mass vector, and therefore preserves its utility for every retained member.
Every member of \(F\) obtains the strictly higher utility of \(C\). The proposed group is measurable and has positive measure. Thus it satisfies precisely the task’s weak-blocking condition.
Removing members from \(C\) requires no consent under USER_TASK, so there is no additional feasibility condition.
Countability is used correctly: the union of the zero-measure intersections with coalitions has measure zero. Hence the common utility across positive-mass intersections is indeed the utility of almost every member of the type.
If a type appears with positive mass in at least two coalitions, one such intersection has mass at most \(1/(2n)\). Otherwise two intersections alone would exceed the type’s total mass.
The bound
\[
u_i(C)\leq \frac{M}{2n}+\frac{(n-1)W}{n}<\frac{M}{n}
\]
is correct. Negative weights cause no difficulty because the estimate is an upper bound using absolute values.
By equal treatment, almost every member of this type receives the same strictly sub-\(M/n\) utility. The entire type \(I_i\) therefore constitutes a positive-measure strict improvement group. This contradicts stability.
The conclusion that there are at most \(n\) positive-measure coalitions also follows: every such coalition contains positive mass of at least one listed type, and no type can have positive mass in two coalitions. Countability again excludes positive mass hidden in a union of null intersections.
For intact types, the utility formula
\[
u_i(B)=\frac{M+v_i(B)}{n}
\]
is correct. A finite weak block transfers to a continuum weak block; strict improvement for one finite player becomes strict improvement on that type’s positive mass. The first implication is established.
The normalization \(x_i=n\lambda(D\cap I_i)\) correctly gives \(0<x_i\leq1\) on the nonempty participating set \(S\).
Both current and proposed utilities are constant within each participating type. Thus the almost-everywhere blocking conditions are equivalent to \(g_i\geq0\) for every \(i\in S\), with \(g_i>0\) for at least one participating type.
The gain formulas and substitution \(h_i=1-x_i\) are algebraically correct.
The omitted-fraction estimate
\[
0\leq h_i\leq\frac{2(n-1)W}{M}
\]
follows from the two stated absolute-value bounds. Consequently,
\[
\Delta_i\geq-\frac{2(n-1)^2W^2}{M}>-1.
\]
Because the source weights are integers, \(\Delta_i\) is an integer, and therefore \(\Delta_i\geq0\).
If any \(\Delta_i>0\), the nonempty set \(S\) weakly blocks the finite partition. Finite strict-core stability consequently forces every \(\Delta_i=0\).
The final maximum-coordinate argument is valid. The set \(S\) is finite, so a maximizing \(h_k\) exists. If it is positive, the displayed expression is bounded below by
\[
\bigl(M-(n-1)W\bigr)h_k>0,
\]
contradicting its required nonpositivity. Hence every omitted fraction vanishes, and the gain equation gives \(g_i=0\) for every participant, contradicting strict improvement.
This excludes every measurable weak block, without assuming rational participating masses or any restriction on the coalitions from which participants are drawn.
The bounds remain valid when \(n=1\), when all off-diagonal weights vanish, and when weights have either sign. Null sets do not affect any comparison or positive-measure requirement.
Both directions of the existence equivalence are proved, and the transformation is polynomial. The claimed hardness result follows. No additional clarification or repair is needed. The proof establishes \(\mathrm{NP}\)-hardness; it does not claim membership in \(\mathrm{NP}\).
⟨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.