Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, even for equal positive dyadic masses; \(\mathrm{NP}\)-hard under polynomial-time Turing reductions.
Corollary 4.9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet $\R$ be any non-deterministic polynomial-time compact representation such that $\graph\precsim_e \R$ (e.g., $\R=\marginal$). On the class $\C(\R)$, \CoreNonEmptyness\ is \CONPc.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\) and a symmetric rational type-interaction matrix \(W=(w_{tu})\) with \(w_{tt}=0\), define \(V_W(a)=\sum_{t<u}w_{tu}a_ta_u\) for \(a\in[0,\mu]\); decide whether there exists \(x\in\mathbb{R}^{\tau}\) such that \(\sum_t\mu_tx_t=V_W(\mu)\) and \(\sum_ta_tx_t\ge V_W(a)\) for every coalition-mass vector \(a\in[0,\mu]\).
A society is given by its support: a list of \(\tau\geq 1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains a symmetric matrix \(W\in\mathbb{Q}^{\tau\times\tau}\) with \(w_{tt}=0\); off-diagonal entries may have either sign and are encoded in binary. Let \(L\) be the total input bit length; running times are measured in \(\tau\) and \(L\), with no separate \(m\) parameter.
A coalition is any real mass vector \(a\) satisfying \(0\leq a_t\leq\mu_t\), and its worth is \(V_W(a)=\sum_{t<u}w_{tu}a_ta_u\). A payoff \(x_t\) is a real payoff per unit mass, constant within type.
Call the mass core nonempty if there exists \(x\in\mathbb{R}^{\tau}\) satisfying \(\sum_t\mu_tx_t=V_W(\mu)\) and \(\sum_ta_tx_t\geq V_W(a)\) for every coalition \(a\). These inequalities include coalitions supported on one type and enforce individual rationality.
Is deciding whether this mass core is nonempty solvable in polynomial time in \(\tau\) and \(L\), or is it \(\mathrm{NP}\)-hard?
Discrete core nonemptiness is \(\mathrm{coNP}\)-complete for graph games, whose coalition worth is the sum of signed edge weights induced by the coalition, and for nondeterministic polynomial-time compact representations admitting polynomial-time translations of graph games.
No complexity classification for the exact mass problem above was identified in the literature search.
The mass-core nonemptiness problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, even when all masses are equal positive dyadic rationals.
Consequently, it is polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\). It is also \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. Under many-one reductions, calling it \(\mathrm{NP}\)-hard would be equivalent to asserting \(\mathrm{NP}=\mathrm{coNP}\).
The key is an exact equivalence between the mass core and a discrete graph-game core.
Let \(N=\{1,\ldots,\tau\}\), and define symmetric edge weights and total type payoffs by
\[ b_{tu}=w_{tu}\mu_t\mu_u, \qquad y_t=\mu_tx_t. \]
For each \(S\subseteq N\), define
\[ v(S)=\sum_{\substack{t<u\\t,u\in S}}b_{tu}, \qquad y(S)=\sum_{t\in S}y_t. \]
Because every \(\mu_t\) is positive, the transformation between \(x\) and \(y\) is invertible.
Lemma. A payoff \(x\) belongs to the mass core if and only if \(y\) satisfies the discrete graph-game core constraints
\[ y(N)=v(N), \qquad y(S)\geq v(S)\quad\text{for every }S\subseteq N. \]
Proof. Necessity follows by considering the coalition that takes all of each type in \(S\) and none of the other types. Efficiency also transforms exactly.
For sufficiency, suppose the discrete constraints hold. Take any real coalition \(a\), and put \(p_t=a_t/\mu_t\). Thus \(0\leq p_t\leq1\). For every \(S\subseteq N\), define
\[ \lambda_S= \prod_{t\in S}p_t \prod_{t\notin S}(1-p_t). \]
These coefficients are nonnegative, and expanding the products gives
\[ \sum_{S\subseteq N}\lambda_S=1, \qquad \sum_{S\ni t}\lambda_S=p_t, \qquad \sum_{S\supseteq\{t,u\}}\lambda_S=p_tp_u \quad(t\ne u). \]
Consequently,
\[ \begin{aligned} \sum_ta_tx_t-V_W(a) &=\sum_tp_ty_t-\sum_{t<u}b_{tu}p_tp_u\\ &=\sum_{S\subseteq N}\lambda_S\bigl(y(S)-v(S)\bigr)\\ &\geq0. \end{aligned} \]
This verifies every fractional coalition constraint. The zero diagonal is essential to this calculation: every interaction involves two distinct coordinates. \(\square\)
In particular, single-type coalitions are retained: the discrete singleton constraints give \(y_t\geq0\), equivalently \(x_t\geq0\).
For \(S\subseteq N\), define its signed cut weight by
\[ c(S)=\sum_{\substack{t\in S\\u\in N\setminus S}}b_{tu}. \]
Each crossing edge occurs once in this sum.
Proposition. The mass core is nonempty if and only if \(c(S)\geq0\) for every \(S\subseteq N\). Whenever it is nonempty, a core payoff is
\[ x_t^*=\frac12\sum_{u\ne t}w_{tu}\mu_u. \]
Proof. Suppose first that the discrete core contains \(y\). Adding the constraints for \(S\) and its complement gives
\[ v(N)=y(N)\geq v(S)+v(N\setminus S). \]
Every edge is either internal to one side or crosses the cut, so
\[ v(N)=v(S)+v(N\setminus S)+c(S). \]
Hence \(c(S)\geq0\).
Conversely, suppose every cut has nonnegative weight. Define
\[ y_t^*=\frac12\sum_{u\ne t}b_{tu}. \]
Summing over all vertices counts each edge twice before multiplication by one half, so \(y^*(N)=v(N)\). Summing over \(S\) counts internal edges twice and crossing edges once, giving
\[ y^*(S)=v(S)+\frac12c(S)\geq v(S). \]
Thus \(y^*\) belongs to the discrete core. The lemma places \(x_t^*=y_t^*/\mu_t\) in the mass core, yielding the stated formula. \(\square\)
This also shows why the existence of an explicit candidate payoff does not yield a polynomial-time decision algorithm: verifying that candidate requires deciding whether every signed cut is nonnegative.
If the mass core is empty, the proposition supplies a subset \(S\subseteq N\) with \(c(S)<0\).
Its characteristic vector has \(\tau\) bits. A verifier computes
\[ c(S)=\sum_{\substack{t\in S\\u\notin S}}w_{tu}\mu_t\mu_u \]
using exact rational arithmetic and checks its sign. There are at most \(\tau^2\) summands, and their products and sums have polynomial bit length in \(\tau\) and \(L\). Verification therefore takes polynomial time.
Mass-core emptiness belongs to \(\mathrm{NP}\), so nonemptiness belongs to \(\mathrm{coNP}\).
Use the graph-game core nonemptiness theorem supplied in the question: this problem is \(\mathrm{coNP}\)-complete for signed graph games. The graph representation and classification are also stated in [Greco, Malizia, Palopoli, and Scarcello, *On the Complexity of Core, Kernel, and Bargaining Set*, Section 1.1](https://arxiv.org/pdf/0810.3136).
Take a graph-game instance with \(n\geq1\) explicitly represented vertices and rational edge weights \(q_{tu}\). Missing edges have weight zero.
Let \(k\) be the least power of two with \(k\geq n\). Add \(k-n\) isolated vertices, extending all incident weights by zero. This preserves core nonemptiness: cuts in the padded graph have exactly the weights of their intersections with the original vertices, so the cut characterization applies.
Construct a mass instance with support size \(\tau=k\) and
\[ \mu_t=\frac1k, \qquad w_{tu}=k^2q_{tu}\quad(t\ne u), \qquad w_{tt}=0. \]
All masses are positive dyadic rationals and sum to one. The matrix is symmetric and satisfies the required diagonal condition. Moreover,
\[ w_{tu}\mu_t\mu_u=q_{tu}. \]
Thus the discrete game associated with the constructed mass instance is exactly the padded source game. Section 2 proves that their cores are simultaneously nonempty.
Finally, \(k<2n\), and multiplying a rational weight by \(k^2\) increases its encoding length by at most a constant times \(\log k\). The dense output matrix and all masses therefore have polynomial total bit length. This is a polynomial-time many-one reduction, proving \(\mathrm{coNP}\)-hardness.
Together with membership, this proves the classification.
The exact classification is \(\mathrm{coNP}\)-complete. Its complement, mass-core emptiness, is \(\mathrm{NP}\)-complete.
Therefore an oracle for nonemptiness decides any \(\mathrm{NP}\) problem by reducing to emptiness, querying the oracle once, and reversing its answer. This establishes \(\mathrm{NP}\)-hardness under Turing reductions.
For many-one reductions, an \(\mathrm{NP}\)-hard language belonging to \(\mathrm{coNP}\) would imply \(\mathrm{NP}\subseteq\mathrm{coNP}\), hence \(\mathrm{NP}=\mathrm{coNP}\). Conversely, that equality would make this \(\mathrm{coNP}\)-complete problem \(\mathrm{NP}\)-hard. Thus the distinction between reduction notions is necessary.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes that mass-core nonemptiness is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, including for equal positive dyadic masses. The argument correctly distinguishes this classification from \(\mathrm{NP}\)-hardness under many-one reductions.
No major or minor mathematical issues were found.
The definitions \(b_{tu}=w_{tu}\mu_t\mu_u\) and \(y_t=\mu_tx_t\) are valid. Positivity of every \(\mu_t\) makes the payoff transformation invertible.
Necessity is correct: choosing \(a_t=\mu_t\) for \(t\in S\) and \(a_t=0\) otherwise gives exactly the discrete coalition constraint. The efficiency equalities also coincide.
For sufficiency, all three identities for \(\lambda_S\) are correct. They hold for every \(p_t\in[0,1]\), including endpoints, and involve only finite sums and products. In particular, the third identity requires distinct indices, as explicitly stated.
The displayed slack identity is exact:
\[ \sum_ta_tx_t-V_W(a) = \sum_{S\subseteq N}\lambda_S\bigl(y(S)-v(S)\bigr). \]
Every summand on the right is nonnegative under the discrete core constraints. Thus the proof covers all real coalitions, with arbitrary signed weights; it does not assume rational coalition coordinates or nonnegative interactions.
The singleton constraints correctly enforce \(x_t\geq0\). The empty coalition gives a tautology. The zero diagonal ensures that the worth contains only products of distinct coordinates, as required by the calculation.
Assessment: correct and complete.
The cut definition counts each crossing edge exactly once.
For necessity, adding the constraints for \(S\) and its complement yields
\[ v(N)\geq v(S)+v(N\setminus S). \]
The decomposition of total worth into the two internal contributions and the crossing contribution is correct. It therefore implies \(c(S)\geq0\).
For sufficiency, both counting identities for the proposed payoff are correct:
\[ y^*(N)=v(N), \qquad y^*(S)=v(S)+\tfrac12c(S). \]
Consequently, all discrete core inequalities hold whenever every cut is nonnegative. Dividing by \(\mu_t>0\) gives precisely the stated formula for \(x_t^*\).
These arguments include \(S=\varnothing\), \(S=N\), and \(\tau=1\). In the last case, all worths and cuts are zero and the proposed payoff is zero.
Assessment: correct and complete.
The cut characterization supplies a certificate of emptiness consisting of one subset with strictly negative cut weight. Its characteristic vector has polynomial length.
The arithmetic claim is sound. Each summand is a product of three input rationals. There are at most \(\tau^2\) summands, and exact addition and multiplication produce intermediate encodings of polynomial length in \(\tau\) and \(L\). Strict negativity can therefore be checked in polynomial time.
There is no need to certify a real payoff or a real coalition: the proposition supplies a discrete certificate whenever the core is empty.
Assessment: correct and complete.
The invoked source theorem is supplied in USER_TASK. The linked paper’s Section 1.1 also states the induced-edge definition of graph games and their \(\mathrm{coNP}\)-complete core-nonemptiness problem. Its definition of imputations includes efficiency and individual rationality, consistent with the constraints used here. [Greco et al., *On the Complexity of Core, Kernel, and Bargaining Set*](https://arxiv.org/pdf/0810.3136)
The reduction satisfies the target’s input restrictions:
The size analysis is correct. Explicitly represented vertices ensure that \(n\) is bounded by the source input size; \(k<2n\) bounds the output dimension. A dense matrix has polynomially many entries, and scaling each weight increases its encoding length by only \(O(\log k)\). There is no hidden dependence on a separate population parameter.
The reduction preserves yes-instances and no-instances in the required direction.
Assessment: correct polynomial-time many-one reduction.
The remaining claims follow correctly from completeness:
The prover therefore resolves the intended complexity question while correctly qualifying the reduction notion. No additional clarification or repair is needed.
⟨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.