Answer: \(\Sigma_2^{\mathrm P}\)-complete under polynomial-time many-one reductions; hence \(\mathrm{NP}\)-hard, even when all masses equal \(1\).
Theorem 6.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet R be a non-deterministic polynomial-time compact representation. Given any coalitional game with non-transferable payoffs G ∈C(R), deciding whether the core of G is not empty is in ΣP 2 . In particular, it is ΣP 2 - complete if R is the marginal contribution nets framework. However, if R is a deterministic polynomial-time compact representation, the problem is in co-NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), positive rational masses \(\mu_t\), and NTU rules whose literals test whether coalition mass \(z_t\) is positive or zero and whose triggered rules add chosen payoff-increment vectors, decide whether \(V(\mu)\) contains an \(x\) such that for every nonzero \(z\leq\mu\) and every \(y\in V(z)\), some \(t\) with \(z_t>0\) satisfies \(y_t\leq x_t\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive masses \(\mu_t\), each encoded as a binary rational. Here \(\tau\) is the support size, not the number of possible types; masses need not sum to \(1\).
The input contains \(m\) NTU rules. Each rule \(r\) has a conjunction of literals testing \(z_t>0\) or \(z_t=0\), and an explicitly listed, finite, nonempty set \(A_r\subseteq\mathbb{Q}^{T}\) of payoff-increment vectors with binary rational coordinates of either sign. Every vector vanishes outside the types tested positively by that rule.
A coalition is any real vector \(z\) with \(0\leq z\leq\mu\) and \(z\neq0\). Let \(R(z)\) be the rules whose conjunctions hold, and define \(V(z)=\{\sum_{r\in R(z)}a_r:a_r\in A_r\}\), with \(V(z)=\{0\}\) when no rule applies.
Each coordinate is the common payoff per member of that type; increments are not multiplied or divided by coalition mass. A coalition chooses exactly one vector from every triggered rule, without convexification. Members prefer larger own-coordinate payoffs, with blocking requiring strict improvement for every participating type.
Let \(L\) be the total binary input length; state running times in \(m\), \(\tau\), and \(L\).
Is deciding whether there exists \(x\in V(\mu)\) such that, for every nonzero real \(z\leq\mu\) and every \(y\in V(z)\), some \(t\) with \(z_t>0\) satisfies \(y_t\leq x_t\), in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard?
For finite players, core nonemptiness under these NTU marginal-contribution rules is \(\Sigma_2^{\mathrm{P}}\)-complete. [Discrete complexity result](https://www.ijcai.org/Proceedings/07/Papers/226.pdf)
No published complexity result for this exact continuous model was located in the literature search.
The problem is \(\Sigma_2^{\mathrm P}\)-complete under polynomial-time many-one reductions, and therefore \(\mathrm{NP}\)-hard. This holds even when every mass equals \(1\).
The key fact is that coalition masses affect neither rule activation nor payoff comparison. The continuous model is therefore exactly equivalent to a finite-player model with one player per supported type.
For a coalition \(z\), define its support by \(\operatorname{supp}(z)=\{t\in T:z_t>0\}\).
For each subset \(S\subseteq T\), let \(R_S\) contain precisely those rules whose positive literals belong to \(S\) and whose negative literals belong to \(T\setminus S\). Define
\(W(S)=\left\{\sum_{r\in R_S}a_r:a_r\in A_r\right\}\),
with \(W(S)=\{0\}\) when \(R_S\) is empty.
Lemma. For every admissible coalition \(z\), \(V(z)=W(\operatorname{supp}(z))\). Moreover, every nonempty subset of \(T\) occurs as an admissible coalition support.
Proof. A positive literal concerning \(t\) holds exactly when \(t\in\operatorname{supp}(z)\); a zero literal holds exactly when \(t\notin\operatorname{supp}(z)\). Thus \(R(z)=R_{\operatorname{supp}(z)}\). The definitions of the feasible payoff sets then give the claimed equality.
For any nonempty \(S\subseteq T\), define \(z^S_t=\mu_t\) for \(t\in S\), and \(z^S_t=0\) otherwise. Positivity of every \(\mu_t\) implies that \(z^S\neq0\), that \(0\leq z^S\leq\mu\), and that \(\operatorname{supp}(z^S)=S\). ∎
Since \(\operatorname{supp}(\mu)=T\), grand-coalition feasibility is exactly \(x\in W(T)\).
Consequently, the required condition on \(x\) is equivalent to
\(\displaystyle \forall\,\varnothing\neq S\subseteq T\;\forall\,y\in W(S)\;\exists\,t\in S:\ y_t\leq x_t.\)
Both directions follow from the lemma: every real coalition determines such a subset, and every nonempty subset has the representative \(z^S\).
In particular, replacing all positive masses by \(1\) preserves the answer.
Use the finite-player theorem supplied in the question: core nonemptiness for NTU marginal-contribution nets is \(\Sigma_2^{\mathrm P}\)-complete. The cited paper’s Definition 6.1 uses conjunctions of positive and negative player literals, finite alternatives of signed payoff increments supported on positively tested players, and sums formed by choosing one alternative from every applicable rule. Its Theorem 6.3 gives the completeness result. [Malizia, Palopoli and Scarcello, Definitions 6.1 and Theorem 6.3](https://www.ijcai.org/Proceedings/07/Papers/226.pdf)
Here is the reduction, including the representation checks.
Take a finite-player instance with player set \(N\). Construct a continuous instance as follows:
This construction preserves the number \(m\) of non-default rules and gives \(\tau=|N|\). Every alternative remains supported on the types tested positively by its rule. Singleton alternatives consisting of the zero vector may be omitted or retained, since they do not change any sum.
For every finite coalition \(S\subseteq N\), the rules it triggers are exactly \(R_S\). Its feasible payoff vectors, embedded in the full coordinate space with zeros outside \(S\), are therefore exactly \(W(S)\). Its strict blocking condition is precisely
\(\displaystyle y_t>x_t\quad\text{for every }t\in S.\)
By Section 1, these are also exactly the possible blocking events in the continuous instance. Thus the finite instance has a nonempty core if and only if the constructed continuous instance has a feasible unblocked grand-coalition payoff.
The reduction has polynomial size and running time. More explicitly, if the finite encoding has length \(L_{\mathrm{fin}}\), padding explicitly listed alternatives to \(\tau\) coordinates and copying the rules takes at most \(O\!\left(\tau(L_{\mathrm{fin}}+m+1)\right)\) bit operations under a straightforward encoding. Writing the unit masses adds \(O(\tau)\) bits.
All hypotheses of the finite-player hardness theorem are therefore preserved. The continuous problem is \(\Sigma_2^{\mathrm P}\)-hard.
A grand-coalition payoff has a polynomial-size description: choose one explicitly listed alternative from every rule triggered by \(T\), and sum the chosen vectors.
For a fixed such payoff \(x\), a blocking certificate consists of:
The verifier evaluates the rule conjunctions, computes \(y\), and checks \(y_t>x_t\) for every \(t\in S\). Section 1 proves that such certificates capture all real blocking coalitions.
To check the arithmetic bound, each coordinate sum contains at most \(m\) input rationals. An unreduced common denominator can be taken as their denominator product. Its binary length is at most the sum of their input lengths, hence \(O(L)\). The corresponding numerator also has length \(O(L+\log(m+1))=O(L)\). Thus exact summation and comparison use polynomially many bit operations.
Using schoolbook integer arithmetic, constructing and checking one payoff pair takes the conservative bound
\(O\!\left(L+(m+1)\tau L^2\right).\)
The decision condition consequently has a polynomial-time existential–universal formulation: existentially choose valid grand-coalition alternatives, then universally consider support-and-alternative descriptions and require that each valid nonempty description fails to block. Invalid universal descriptions are accepted automatically.
By the quantified-predicate characterization of \(\Sigma_2^{\mathrm P}\), the problem belongs to that class. Together with Section 2, this proves completeness.
For completeness, put \(k_r=|A_r|\) and \(K=\prod_{r=1}^{m}k_r\), taking \(K=1\) when \(m=0\).
There are at most \(K\) grand-coalition choice tuples. For each of the \(2^\tau-1\) nonempty supports, there are at most \(K\) coalition choice tuples, because every \(k_r\) is positive. Exhaustively comparing these tuples therefore decides the problem in
\(O\!\left(2^\tau K^2\bigl[L+(m+1)\tau L^2\bigr]\right)\)
bit operations. Since each \(k_r\leq L\) under the explicit-list encoding, a bound solely in the requested parameters is
\(O\!\left(2^\tau L^{2m}\bigl[L+(m+1)\tau L^2\bigr]\right).\)
This is an exhaustive upper bound, not a polynomial-time algorithm. The proved classification is \(\Sigma_2^{\mathrm P}\)-completeness; in particular, polynomial-time solvability would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the target correctly. The support reduction is exact, the cited finite-player hardness theorem applies, and the membership and running-time arguments are valid. I found no major or minor mathematical issues.
Verified. Every rule tests only whether a coordinate is positive or zero. Consequently, two admissible coalitions with the same support trigger exactly the same rules. Their feasible payoff sets are identical because the chosen increments do not depend on coalition masses.
The representative coalition defined by \(z^S_t=\mu_t\) for \(t\in S\) and \(z^S_t=0\) otherwise is admissible for every nonempty \(S\subseteq T\). The positivity assumption on every mass is precisely what guarantees that its support is \(S\).
The lemma therefore establishes both required directions:
Since participating types are exactly the support coordinates, the blocking comparison is preserved as well. Thus the displayed condition involving \(W(S)\) is exactly equivalent to the task’s condition, including its quantifiers over all feasible coalition payoffs.
Replacing positive masses by unit masses preserves every possible support, every triggered-rule set, and every blocking comparison. This conclusion is justified.
Verified against the cited source. Definition 6.1 specifies conjunctions of positive and negative player literals, signed payoff increments supported on positively tested players, and additive selection of rule consequences. Its implicit default rules contribute zero. Definition 2.4 uses strict improvement for every coalition member. Theorem 6.3 states completeness for NTU marginal-contribution nets. The published hardness construction uses finite, explicitly displayed integer alternatives, so it lies within the target’s binary-rational representation. [Malizia, Palopoli and Scarcello, Definitions 2.4 and 6.1, Theorem 6.3](https://www.ijcai.org/Proceedings/07/Papers/226.pdf)
The proposed transformation preserves each relevant feature:
Consequently, the asserted equivalence of core nonemptiness in the source and target instances follows from the already-proved support lemma. No additional assumption about convexification, payoff redistribution, or mass normalization is introduced.
The padding bound is polynomial: the number of explicitly listed alternatives and their existing encoding lengths are bounded by the source input length, and adding up to \(\tau\) coordinates per alternative gives the stated conservative bound. The hardness transfer is valid.
Verified. A choice of one alternative from every grand-coalition rule describes a feasible grand-coalition payoff. Explicit listing ensures that these indices require only polynomially many bits.
For a fixed candidate, a nonempty support and one alternative index per triggered rule describe a blocking certificate. Every such valid description determines a feasible coalition payoff, and the support lemma guarantees that every possible real blocking event has such a description.
The arithmetic bounds also hold. Each coordinate sum uses at most \(m\) input rationals. The product of their denominators has bit length bounded by the sum of the corresponding input lengths. After conversion to that denominator, the numerator sum has bit length \(O(L+\log(m+1))\). Since the rules are explicitly encoded, this is \(O(L)\).
Signed numerators cause no difficulty, and exact comparisons preserve strict inequality. Using schoolbook arithmetic, the stated bound
\(O\!\left(L+(m+1)\tau L^2\right)\)
is conservative and sufficient for evaluating rules, forming both payoffs, and checking the comparisons.
Verified. The existential description chooses valid grand-coalition alternatives. The universal description ranges over supports and coalition alternatives. The polynomial-time predicate accepts invalid universal descriptions and otherwise checks that the described coalition fails to improve every participating coordinate strictly.
This is the required existential–universal characterization of \(\Sigma_2^{\mathrm P}\). The argument quantifies over descriptions rather than distinct payoff vectors, which is legitimate: duplicate descriptions do not change either existential feasibility or universal absence of blocking.
Together with the verified hardness transfer, this establishes \(\Sigma_2^{\mathrm P}\)-completeness.
Verified. For every triggered-rule subset, the number of alternative tuples is at most \(K=\prod_{r=1}^{m}|A_r|\), because each alternative set is nonempty. There are at most \(K\) grand-coalition tuples and \(2^\tau-1\) nonempty supports.
Multiplying these enumeration bounds by the verified per-comparison cost yields
\(O\!\left(2^\tau K^2[L+(m+1)\tau L^2]\right)\).
Explicit listing gives \(|A_r|\leq L\), so the replacement \(K^2\leq L^{2m}\) is valid. The resulting bound is exponential, as the prover expressly acknowledges.
The argument covers rules that never trigger, supports triggering no rules, duplicate payoff sums, negative increments, and arbitrary positive rational masses. When \(m=0\), the empty choice tuple produces the zero payoff, and no coalition can strictly improve upon it; the definitions and enumeration convention handle this case correctly.
The conclusion about polynomial-time solvability is appropriately conditional: the proved hardness implies that a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\). The output does not claim an unconditional separation.
No repair or additional clarification is necessary.
⟨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.