Answer: \(\mathrm{NP}\)-hard
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateProblem HG/E/SC/EXIST is NPNP-complete. Therefore, since this problem is at least as intractable as all the problems that nest a coNP problem into an NP problem, it is extremely intractable, despite the utter simplicity of ene- mies aversion as a preference.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational mass vector \(\mu\in\Delta(T)\), and relation matrix \(R:T\times T\to\{F,E,\bot\}\), decide whether there exists a finite-support mass decomposition \(\mathcal P=\{(\lambda_r,x^r)\}_r\) with \(\sum_r\lambda_r x^r=\mu\) and no nonzero profile \(z\) that can be assembled from agents weakly preferring \(z\) to their assigned profiles, with a positive-mass set strictly preferring it, under enemies aversion.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. There is no separate candidate parameter \(m\).
The input also contains a directed relation matrix \(R:T\times T\to\{F,E,\bot\}\), denoting friends, enemies, and neutrals. Diagonal entries describe relations between distinct agents of the same type; an individual has zero mass.
A coalition profile is an absolute mass vector \(x\) with \(0\le x\le\mu\) and \(x\ne0\). Define \(e_t(x)=\sum_{s:R(t,s)=E}x_s\) and \(f_t(x)=\sum_{s:R(t,s)=F}x_s\). Type \(t\) ranks profiles by lexicographically maximizing \((-e_t(x),f_t(x))\); equality in both coordinates means indifference.
A finite fractional mass decomposition is \(\mathcal P=\{(\lambda_r,x^r)\}_{r=1}^{k}\), with real \(\lambda_r>0\), coalition profiles \(x^r\), and \(\sum_r\lambda_rx^r=\mu\). The mass of type \(t\) assigned profile \(x^r\) is \(\lambda_rx_t^r\); neither the profiles nor the weights are separately normalized.
A weak block consists of real recruitment amounts \(0\le y_{tr}\le\lambda_rx_t^r\), forming \(z_t=\sum_r y_{tr}\) with \(z\ne0\), such that \(y_{tr}>0\) implies \(z\succeq_t x^r\), and \(\sum_{(t,r):z\succ_t x^r}y_{tr}>0\). A decomposition is strictly core stable if it admits no weak block.
Is deciding whether such a strictly core-stable finite mass decomposition exists in \(\mathrm P\), with running time polynomial in \(\tau\) and \(L\), or is it \(\mathrm{NP}\)-hard?
For finite agents with directed friend, enemy, and neutral relations under enemies aversion, strict-core existence is \(\Sigma_2^{\mathrm P}\)-complete, and verification of a given partition is \(\mathrm{coNP}\)-complete. [Ota et al.](https://www.ijcai.org/proceedings/2017/0051.pdf)
No result settling this exact continuous mass-decomposition problem was located.
Deciding whether a strictly core-stable finite mass decomposition exists is \(\mathrm{NP}\)-hard.
This holds even when all masses are dyadic rationals, all diagonal entries are neutral, the enemy relation is symmetric, and only two types have any friends.
Call a profile \(x\) enemy-free if \(x_t>0\) implies \(e_t(x)=0\).
Lemma. Every profile of a strictly core-stable decomposition is enemy-free. Moreover, any weak block against a decomposition whose profiles are enemy-free must itself be enemy-free.
Proof. Suppose \(x_t^r>0\) and \(e_t(x^r)>0\). Set \(a=\lambda_rx_t^r\). Mass conservation gives \(0<a\le\mu_t\). Choose
\(\varepsilon=\frac12\min\{a,e_t(x^r)\}>0.\)
Recruit only an amount \(\varepsilon\) of type \(t\) from profile \(r\). The resulting profile \(z\) has \(z_t=\varepsilon\) and all other coordinates zero. It is feasible, and
\(e_t(z)\le\varepsilon<e_t(x^r).\)
Thus all recruited mass strictly improves, contradicting stability.
For the second assertion, let \(z\) be a weak block against enemy-free profiles. If \(z_t>0\), some \(y_{tr}>0\). Since the incumbent enemy coordinate is zero, \(z\succeq_t x^r\) requires \(e_t(z)=0\). Hence \(z\) is enemy-free. \(\square\)
Consequently, the support of an enemy-free profile cannot contain two types connected by an enemy entry.
We reduce from Independent Set: given a simple undirected graph \(G=(V,\mathcal E)\), with \(n=|V|\), and an integer \(1\le k\le n\), decide whether its maximum independent-set size \(\alpha(G)\) satisfies \(\alpha(G)\ge k\). This problem is \(\mathrm{NP}\)-complete: graph complementation transforms it into the clique threshold problem, whose \(\mathrm{NP}\)-completeness is stated in [Ota et al., Section 4](https://www.ijcai.org/proceedings/2017/0051.pdf).
Introduce a set \(B\) of \(k\) additional types and two distinguished types \(p,q\). Thus
\(T=V\mathbin{\dot\cup}B\mathbin{\dot\cup}\{p,q\}.\)
Choose the least integer \(h\) such that \(2^h>n+k\), and put
\(\delta=2^{-h},\qquad \mu_s=\delta\ \text{for }s\in V\cup B,\qquad \mu_p=\mu_q=\frac{1-(n+k)\delta}{2}.\)
These masses are positive dyadic rationals and sum to \(1\).
Specify the relation matrix as follows:
The types in \(V\cup B\) have no friends. Thus they are indifferent between all enemy-free profiles: their preference coordinates are always \((0,0)\).
For \(C\subseteq T\), write \(\mu[C]\) for the profile whose coordinate is \(\mu_t\) when \(t\in C\), and zero otherwise. Recruiting the entire mass of every type in \(C\) is always capacity-feasible: use \(y_{tr}=\lambda_rx_t^r\) for \(t\in C\), and zero otherwise.
We prove that the constructed society admits a strictly core-stable decomposition if and only if \(\alpha(G)\ge k\).
Suppose
\(\mathcal P=\{(\lambda_r,x^r)\}_{r=1}^{\ell}\)
is strictly core stable. By the lemma, every profile is enemy-free.
First, every profile containing type \(q\) must give it friend mass exactly \(k\delta\):
\(x_q^r>0\quad\Longrightarrow\quad f_q(x^r)=k\delta.\)
Indeed, \(q\)'s only friends are the types in \(B\), so every feasible profile gives \(q\) friend mass at most \(k\delta\).
Consider recruiting all mass of \(q\) and all mass of \(B\), producing \(z=\mu[\{q\}\cup B]\). This profile is enemy-free. Every recruited type in \(B\) is indifferent, while every recruited portion of \(q\) weakly prefers it. If any occupied profile of \(q\) supplied less than \(k\delta\) friend mass, a positive amount of \(q\) would strictly improve. That would be a weak block.
Because each coordinate \(x_b^r\) is at most \(\delta\), equality \(f_q(x^r)=k\delta\) forces
\(x_b^r=\delta\qquad\text{for every }b\in B\text{ whenever }x_q^r>0.\)
Now set
\(J=\{r:x_q^r>0\},\qquad W=\sum_{r\in J}\lambda_r.\)
Mass conservation for \(q\) gives
\(\mu_q=\sum_{r\in J}\lambda_rx_q^r\le\mu_qW,\)
so \(W\ge1\).
For any \(b\in B\), mass conservation gives
\(\delta=\sum_r\lambda_rx_b^r\ge\sum_{r\in J}\lambda_r\delta=\delta W,\)
so \(W\le1\). Here \(B\) is nonempty because \(k\ge1\). Therefore \(W=1\), and for every \(b\in B\),
\(\sum_{r\notin J}\lambda_rx_b^r=0.\)
All summands are nonnegative and every weight is positive. Consequently,
\(r\notin J\quad\Longrightarrow\quad x_b^r=0\text{ for every }b\in B.\)
Thus every profile containing any mass of \(B\) also contains \(q\). This conclusion applies to arbitrary real weights and arbitrary fractional profiles.
Since \(p,q\) are enemies, no enemy-free profile containing \(p\) can contain \(q\). By the preceding section, such a profile also contains no type in \(B\).
Its positive coordinates in \(V\) form an independent set of \(G\). Each such coordinate is at most \(\delta\). Hence
\(x_p^r>0\quad\Longrightarrow\quad f_p(x^r)\le\delta\alpha(G).\)
Suppose \(\alpha(G)<k\). Recruit all mass of \(p\) and all mass of \(B\), producing
\(z=\mu[\{p\}\cup B].\)
This profile is enemy-free and gives \(p\) friend mass \(k\delta\). Every recruited portion of \(p\) strictly prefers it, since its incumbent friend mass is at most \(\delta\alpha(G)<k\delta\). Every recruited portion of \(B\) is indifferent.
The strictly improving recruited mass is \(\mu_p>0\), so this is a weak block—a contradiction. Therefore existence of a strictly core-stable decomposition implies \(\alpha(G)\ge k\).
Conversely, suppose \(\alpha(G)\ge k\), and let \(I\subseteq V\) be a maximum independent set.
Use the following profiles, each with weight \(1\):
Their supports partition \(T\), so their sum is \(\mu\). They form a valid finite mass decomposition. Every profile is enemy-free.
The incumbent preference coordinates are:
Suppose a weak block produces \(z\). The recruitment bounds imply \(0\le z\le\mu\), and the lemma implies that \(z\) is enemy-free.
Every recruited type in \(V\cup B\) remains indifferent because it has no friends.
For type \(q\), every feasible profile satisfies
\(f_q(z)=\sum_{b\in B}z_b\le k\delta.\)
Thus \(q\) cannot strictly improve.
If \(p\) participates, examine the source types present in \(z\). The support cannot contain both a type in \(V\) and a type in \(B\), because every such pair consists of mutual enemies.
If it contains types from \(V\), those types form an independent set of \(G\), giving
\(f_p(z)\le\delta\alpha(G).\)
If it contains types from \(B\), it gives
\(f_p(z)\le k\delta\le\delta\alpha(G).\)
If neither set contributes, its friend mass is zero. Therefore \(p\) cannot strictly improve either.
All recruited types have zero incumbent enemy mass, so none can strictly improve by reducing enemies. No recruited mass strictly improves in either coordinate, contradicting the definition of a weak block. The decomposition is therefore strictly core stable.
The construction has
\(\tau=n+k+2\le2n+2.\)
Every mass has an encoding of \(O(\log n)\) bits, and the relation matrix has \(O(n^2)\) entries. The reduction is computable in polynomial time and establishes
\(\alpha(G)\ge k \quad\Longleftrightarrow\quad \text{a strictly core-stable finite mass decomposition exists}.\)
Hence the requested decision problem is \(\mathrm{NP}\)-hard. A running time polynomial in \(\tau\) and \(L\) would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s argument establishes the claimed \(\mathrm{NP}\)-hardness for the exact continuous mass-decomposition problem. I found no major or minor issues requiring repair. In particular, the necessity argument handles arbitrary positive real weights and fractional profiles, and the sufficiency argument rules out every permitted weak block.
If \(x_t^r>0\), then \(a=\lambda_rx_t^r>0\), and mass conservation gives \(a\le\mu_t\). The chosen recruitment amount satisfies
\[
0<\varepsilon\le a,\qquad \varepsilon\le\mu_t,\qquad \varepsilon<e_t(x^r).
\]
Thus recruiting \(\varepsilon\) exclusively from entry \((t,r)\) respects the recruitment bound and produces a nonzero feasible profile.
For this single-type profile, \(e_t(z)\) is either zero or \(\varepsilon\), depending on the diagonal relation. Therefore \(e_t(z)<e_t(x^r)\), so the recruited mass strictly improves regardless of its friend coordinate. The lemma consequently also covers enemy diagonal entries.
Conversely, if \(z_t>0\), at least one \(y_{tr}>0\). Its incumbent profile is enemy-free, so its incumbent enemy mass is zero. Since enemy mass is nonnegative, weak preference requires \(e_t(z)=0\). This proves the second assertion with the correct quantifiers.
The stated support restriction follows: an enemy entry between two positive coordinates would give its source type positive enemy mass.
The restriction \(1\le k\le n\) ensures that \(B\) is nonempty and that the construction has polynomial size. The cited clique threshold problem is explicitly defined and stated to be \(\mathrm{NP}\)-complete in [Ota et al., Section 4](https://www.ijcai.org/proceedings/2017/0051.pdf). Graph complementation gives the stated Independent Set source problem; thresholds outside this range are trivial and do not affect hardness.
Writing \(N=n+k\), the mass formulas give
\[
\mu_p=\mu_q=\frac{2^h-N}{2^{h+1}}>0,\qquad
N\delta+\mu_p+\mu_q=1.
\]
Every mass is a positive dyadic rational. The relation specifications do not conflict: friendship entries originate only at \(p\) or \(q\), while the other specified entries are enemy entries on distinct pairs. The enemy relation is symmetric, and all diagonal entries are neutral.
Types in \(V\cup B\) have no friends. Whenever such a type participates in an enemy-free profile, both preference coordinates are zero, so the claimed indifference is valid.
Recruiting all mass of a selected set \(C\) is capacity-feasible because the proposed recruitment uses each relevant capacity exactly, and conservation gives \(z=\mu[C]\). Preference feasibility must still be checked for each proposed block; the subsequent sections do so.
Every feasible profile has \(f_q(x)\le k\delta\). The proposed profile \(\mu[\{q\}\cup B]\) is enemy-free. All recruited \(B\)-mass is indifferent, and all recruited \(q\)-mass weakly improves.
If any profile with \(x_q^r>0\) supplies less than \(k\delta\) friend mass, the recruited amount \(\lambda_rx_q^r\) from that profile is positive and strictly improves. This meets the positive-mass strict-improvement requirement.
Consequently, every occupied \(q\)-profile has friend mass \(k\delta\). Since this is a sum of exactly \(k\) coordinates, each bounded above by \(\delta\), every \(B\)-coordinate in such a profile equals \(\delta\).
Both bounds on \(W\) follow correctly from conservation:
\[
\mu_q\le\mu_qW,\qquad \delta\ge\delta W.
\]
Their positive coefficients permit division, yielding \(W=1\). For each \(b\in B\), the profiles indexed by \(J\) therefore consume its entire mass. Positivity of every weight and nonnegativity of every coordinate imply \(x_b^r=0\) outside \(J\).
This step does not assume normalized weights or integral profiles. It proves exactly the claimed exclusion of \(B\) from profiles without \(q\).
Any occupied \(p\)-profile excludes \(q\) by enemy-freeness and excludes \(B\) by the preceding argument. Its positive \(V\)-coordinates form an independent set, each coordinate being at most \(\delta\). Thus its friend mass is at most \(\delta\alpha(G)\).
Under \(\alpha(G)<k\), the proposed profile \(\mu[\{p\}\cup B]\) is feasible and enemy-free. Every recruited portion of \(p\) strictly improves its friend coordinate at equal zero enemy mass. Every recruited portion of \(B\) is indifferent.
The total strictly improving recruited mass is \(\mu_p>0\). Hence the proposed recruitment is a weak block under the exact definition, proving the necessary implication.
The listed supports partition \(T\). Every profile is nonzero, every coordinate respects its mass bound, and all weights equal one. Their sum is therefore \(\mu\).
The first profile is enemy-free because \(I\) is independent and \(p\) has no enemy relation with its vertices. The second profile and all singleton profiles are also enemy-free. The stated incumbent preference coordinates follow directly from the specified relations and full coordinates.
Choosing a maximum independent set is legitimate for this existential argument. The prover does not claim to compute that set in polynomial time.
Recruitment bounds and mass conservation give \(0\le z\le\mu\), and the lemma makes every possible weak block enemy-free. Thus recruited types in \(V\cup B\) remain indifferent.
Type \(q\) cannot exceed its incumbent friend mass \(k\delta\).
If \(p\) participates, enemy-freeness excludes simultaneous positive coordinates from \(V\) and \(B\). When vertices contribute, their support is independent and their total mass is at most \(\delta\alpha(G)\). When \(B\) contributes, its total mass is at most \(k\delta\le\delta\alpha(G)\). When neither contributes, \(p\)'s friend mass is zero.
These cases exhaust \(p\)'s possible friends, including fractional recruitment. Neither distinguished type can strictly improve its friend coordinate, and no recruited type can reduce an incumbent enemy coordinate already equal to zero. Therefore the required positive strictly improving mass cannot exist.
Equality \(\alpha(G)=k\) causes no exception: matching incumbent friend mass gives indifference, which alone cannot constitute a weak block.
The support size is \(n+k+2\le2n+2\). The chosen denominator exponent and mass numerators require \(O(\log n)\) bits asymptotically, and the relation matrix has \(O(n^2)\) entries. Constructing the instance requires no independent-set computation.
The two directions establish a polynomial-time many-one reduction with the claimed yes-instance equivalence. Thus the exact continuous existence problem is \(\mathrm{NP}\)-hard, including under the stated restrictions. No membership claim for \(\mathrm{NP}\), or transfer of the finite-agent completeness result, is needed.
No additional clarification or 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.