Answer: \(\mathrm{coNP}\text{-complete for both core verification and strict-core verification; equivalently, both blocker-existence problems are }\mathrm{NP}\text{-complete}\)
Theorem 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf the friendship graph (resp. the union graph) is acyclic, then every FENs-instance admits an individually stable (resp. Nash stable) partition, which can be found in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), and disjoint directed friendship and enemy graphs \(G_g,G_b\) on \(T\) such that \(G_g\cup G_b\) is acyclic, decide whether there exist rational coalition vectors \(z^1,\ldots,z^q\in\mathbb{Q}_{\ge 0}^{T}\), with \(q\le |T|\) and \(\sum_{j=1}^{q}z_t^j=\mu_t\) for every \(t\), such that no positive-mass type assigned to any \(z^j\) strictly prefers another existing coalition or a new singleton coalition under the lexicographic valuation \(v_t(z)=\left(\sum_{r\in N^+_{G_g}(t)}z_r,-\sum_{r\in N^+_{G_b}(t)}z_r\right)\).
Definitions. Let \(T\) be finite; for each \(t\in T\), \(T\setminus\{t\}=F_t\mathbin{\dot\cup}E_t\). A type \(t\) ranks mass profiles \(q\in\mathbb{Q}_{\ge0}^{T}\) lexicographically by \(\bigl(\sum_{u\in F_t}q_u,-\sum_{u\in E_t}q_u\bigr)\). The input has rational \(z^j,\lambda_j,s\) with \(\sum_j\lambda_jz^j_t+s_t=\mu_t\); coalition \(j\)'s profile is \(\lambda_jz^j\), and a residual type \(t\) has singleton profile \(e_t\).
A blocker is \(y\) with \(0\le y_{j,t}\le\lambda_jz^j_t\), \(0\le y_{0,t}\le s_t\), and \(\beta_t=y_{0,t}+\sum_jy_{j,t}\), where \(\sum_t\beta_t>0\), such that every source with positive selected mass strictly prefers \(\beta\) to its current profile (or \(e_t\) for source \(0\)). For strict-core verification, replace this by weak preference for every selected source and strict preference for at least one.
Target. Is typed continuous FEs core verification, and separately strict-core verification, solvable in polynomial time or NP-hard?
Nearest known results. For finite friends-and-enemies hedonic games, verifying that a given partition is core stable is coNP-complete.
The corresponding finite strict-core verification problem is also coNP-complete.
Assume that the number of types is part of the input and that rationals are binary encoded.
Theorem. For typed continuous friends-and-enemies games:
Thus neither verification problem is polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
Strictly speaking, a \(\mathrm{coNP}\)-complete verification problem is not known to be \(\mathrm{NP}\)-hard under ordinary many-one reductions unless \(\mathrm{NP}=\mathrm{coNP}\). Its complement—the blocker-existence problem—is \(\mathrm{NP}\)-complete.
For a type \(t\), define
\(f_t(q)=\sum_{u\in F_t}q_u\) and \(e_t(q)=\sum_{u\in E_t}q_u\).
For a source \(i=(j,t)\), let
\(a_i=f_t(\lambda_jz^j)\) and \(b_i=e_t(\lambda_jz^j)\).
For a residual source, both values are \(0\), because \(F_t,E_t\subseteq T\setminus\{t\}\).
Then source \(i\) strictly prefers \(\beta\) precisely when
\(f_t(\beta)>a_i\),
or
\(f_t(\beta)=a_i\) and \(e_t(\beta)<b_i\).
It weakly prefers \(\beta\) precisely when
\(f_t(\beta)>a_i\),
or
\(f_t(\beta)=a_i\) and \(e_t(\beta)\le b_i\).
Consider either blocker-existence problem. Guess:
After this guess, all requirements form a rational linear system. For example, a selected core source is assigned either \(f_t(\beta)>a_i\), or \(f_t(\beta)=a_i\) together with \(e_t(\beta)<b_i\).
Feasibility of such a system with strict inequalities is polynomial-time decidable. Introduce one variable \(\delta\), replace every strict inequality \(L(x)>r\) by \(L(x)\ge r+\delta\), replace every guessed positivity condition \(y_i>0\) by \(y_i\ge\delta\), and maximize \(\delta\). The original guessed system is feasible exactly when the optimum satisfies \(\delta>0\).
There are polynomially many cells and branches. Hence both blocker-existence problems belong to \(\mathrm{NP}\), and both verification problems belong to \(\mathrm{coNP}\).
We first show that arbitrary rational current thresholds can be realized without introducing unintended blockers.
Let \(x\) be a principal type of mass \(c_x>0\), and let \(a_x>0\), \(b_x\ge0\) be desired current friend and enemy masses. One can construct a private coalition containing \(x\) and two new dummy types such that:
If \(b_x>0\), introduce dummies \(d_x^1,d_x^2\) of masses \(a_x,b_x\), respectively. Type \(x\) regards \(d_x^1\) as a friend and \(d_x^2\) as an enemy.
If \(b_x=0\), give both dummies mass \(a_x/2\), and let \(x\) regard both as friends.
Let the private coalition profile be
\(p^x_x=c_x\),
with the two specified dummy masses and all other coordinates zero.
Each dummy regards the other two types in its private coalition as friends and every type outside that coalition as an enemy. Thus a dummy already has all globally available friend mass and no enemy mass in its current coalition. It can never strictly improve.
Suppose a dummy weakly prefers some candidate in which it is selected. Weak preference forces all its private friends to be present at full mass and forbids every outside type. The other dummy is therefore also selected; applying the same argument to it forces the first dummy to be present at full mass. Consequently, the candidate is exactly \(p^x\). All three selected sources are then indifferent, so this candidate is not a strict-core blocker.
To represent this coalition in the required input format, set \(\lambda_x=\sum_t p^x_t\) and \(z^x=p^x/\lambda_x\). This proves the lemma. \(\square\)
Let \(\varphi\) be a \(3\)-CNF formula with \(n\) variables and \(m\) clauses. Put
\(H=n+m\), \(W=2n+4\), and \(A=W+1+H+4n\).
The principal types are:
Thus \(A\) is the total mass of all principal types.
The following table specifies each principal's friends among the other principal types and its desired current pair \((a_x,b_x)\). Lemma 1 supplies the private dummies realizing that pair. Every unspecified type is an enemy.
| Principal | Friends among principals | Current pair |
|---|---|---|
| \(r\) | \(q\), all \(v_i\), all \(c_j\) | \((H+1,2n+1)\) |
| \(q\) | \(r\) | \((W,H+2n+1)\) |
| \(v_i\) | \(r,\ell_i^0,\ell_i^1\) | \((W,0)\) |
| \(c_j\) | \(r\) and the literal types occurring in clause \(j\) | \((W,0)\) |
| \(\ell_i^b\) | \(r,k_i^b\) | \((W+1,A+1)\) |
| \(k_i^b\) | \(\ell_i^b\) | \((1,A+1)\) |
There is no residual mass. Each principal and its two private dummies occur only in their private coalition.
The construction has polynomial size, and all numbers have polynomial binary encoding length.
Suppose \(\varphi\) has a satisfying assignment. Select at full mass:
Select no private dummy.
For \(r\), the candidate has friend mass \(H+1\) and enemy mass \(2n<2n+1\). Thus \(r\) strictly improves.
For \(q\), the candidate has friend mass \(W\) and enemy mass \(H+2n<H+2n+1\). Thus \(q\) strictly improves.
Each variable checker has friend mass \(W+1>W\). Every clause checker also has friend mass at least \(W+1\), because its clause contains a selected satisfying literal.
Each selected \(\ell_i^b\) has friend mass \(W+1\). Its enemy mass is smaller than \(A+1\), so it strictly improves in the second coordinate. The same argument applies to \(k_i^b\), whose friend mass is \(1\).
Hence every selected source strictly improves. The candidate is a core blocker and therefore also a strict-core blocker. \(\square\)
Suppose a weakly blocking candidate exists. By Lemma 1, it contains no private dummy, so it is supported entirely on principal types.
First, any selected principal forces \(r\) to be selected:
Because \(r\)'s maximum possible friend mass is exactly \(H+1\), weak preference by \(r\) forces \(q\) and every checker to be present at full mass. Weak preference by \(q\) then forces \(r\) to be present at its full mass \(W\).
Consider a variable checker \(v_i\). If neither \(\ell_i^0\) nor \(\ell_i^1\) is selected, its friend mass is exactly \(W\). But \(q\) is then a present enemy, whereas \(v_i\)'s current enemy mass is \(0\). Therefore \(v_i\) would not weakly prefer the candidate. Thus at least one of \(\ell_i^0,\ell_i^1\) is selected.
The same argument applied to each clause checker shows that at least one literal occurring in every clause is selected.
Whenever \(\ell_i^b\) is selected, its maximum-friend threshold forces \(k_i^b\) to full mass; the lock then forces \(\ell_i^b\) to full mass. Conversely, a selected lock forces its literal. Therefore selected literals occur in complete literal-lock modules, each of total mass \(2\).
Let \(L\) be the number of selected literal modules. The variable checkers give \(L\ge n\). For \(r\), all selected literal and lock types are enemies, so its enemy mass is \(2L\). Weak preference by \(r\) gives
\(2L\le 2n+1\).
Since \(L\) is integral, \(L\le n\). Hence \(L=n\), and exactly one literal module is selected for each variable.
Assign each variable the truth value corresponding to its selected module. Every clause checker forces one of its clause's literal types to be selected, so every clause is satisfied. Thus \(\varphi\) is satisfiable. \(\square\)
The same converse applies a fortiori to a core blocker, because every core blocker is also a strict-core blocker.
The construction satisfies
\(\varphi\) is satisfiable if and only if a core blocker exists,
and this is also equivalent to the existence of a strict-core blocker.
Thus both blocker-existence problems are \(\mathrm{NP}\)-hard. Together with Section 2, they are \(\mathrm{NP}\)-complete. Taking complements proves that both verification problems are \(\mathrm{coNP}\)-complete.
This is a direct continuous-mass reduction; it does not assume that the finite-agent hardness result automatically survives divisibility. The quoted finite result appears as Theorem \(1\) in [Chen, Csáji, Roy, and Simola](https://arxiv.org/pdf/2203.09655).
⟨structured verdict parsed — rendered above⟩
The reduction is substantively correct. The threshold gadget handles divisible mass, the converse correctly forces integral literal-lock modules, and the complexity conclusions follow. I found no false central step or missing mathematical lemma.
Several minor points should be made explicit, chiefly the exact constraints in the NP-membership linear program and the intended meaning of “weakly blocking candidate” in Lemma 3.
The stated strict and weak lexicographic preference conditions are correct.
For a residual source of type \(t\), its current profile is \(e_t\). Since \(t\notin F_t\cup E_t\), both current friend and enemy masses are indeed \(0\).
Guessing the support, a lexicographic branch for every selected source, and a strict witness in the strict-core case leaves a rational linear feasibility problem.
The common-slack construction using \(\delta\) is valid because there are finitely many strict inequalities: any feasible point has a positive minimum slack over all of them. Conversely, a feasible solution with \(\delta>0\) satisfies every original strict inequality.
The presentation omits three routine but necessary details:
Also, “the optimum satisfies \(\delta>0\)” should separately allow for the auxiliary linear program being infeasible. These are expositional gaps, not defects in the complexity argument.
The gadget works as claimed.
A selected dummy can weakly prefer a candidate only if:
The second dummy then forces the first dummy itself to full mass. Hence the aggregate candidate is exactly the original private coalition profile. All selected sources are indifferent, so it cannot be a strict-core blocker. A dummy can never strictly improve, so it cannot occur in a core blocker.
The two cases \(b_x>0\) and \(b_x=0\) realize the desired current pair correctly. The normalization \(z^x=p^x/\lambda_x\) also correctly gives \(\lambda_xz^x=p^x\).
The listed principal masses sum to
\[ W+1+n+m+4n=W+1+H+4n=A. \]
There are only polynomially many principal and dummy types, and every numerical quantity has polynomial binary encoding length. Thus the construction is polynomial.
The prover should explicitly define the polarity convention: a positive occurrence of variable \(i\) corresponds to \(\ell_i^1\), while a negative occurrence corresponds to \(\ell_i^0\). This is evident from the intended assignment interpretation but is not formally stated.
For a satisfying assignment, all selected sources strictly prefer the proposed candidate:
Thus the candidate is a core blocker and consequently a strict-core blocker.
The title of Lemma 3 concerns a strict-core blocker, but its proof begins, “Suppose a weakly blocking candidate exists.” Read literally as merely requiring weak preference by everyone, this is false: a private coalition profile containing its dummies is an all-indifferent weakly preferred candidate. Lemma 1 excludes it only when the candidate also has at least one strict witness.
The proof is correct if “weakly blocking candidate” means a strict-core blocker, namely weak preference for every selected source and strict preference for at least one. That hypothesis should be stated explicitly.
Under that intended hypothesis:
The same implication applies to a core blocker because every core blocker meets the strict-core blocking conditions.
The reduction establishes equivalence between satisfiability and the existence of either kind of blocker. Together with NP membership, both blocker-existence problems are NP-complete. Taking complements correctly makes both verification problems coNP-complete.
The prover also correctly cautions that coNP-completeness of verification should not itself be called NP-hard under ordinary many-one reductions unless an additional complexity-class collapse holds.
No new mathematics is needed. The write-up should:
⟨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.