Answer: \(\mathrm{NP}\)-hard; in fact undecidable, even for \(m=\tau=1\).
Theorem 5.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCore-NonEmptiness is ΣP 2 -hard, even for cohesive constrained games with polynomial-time oracles, and where integer and auxiliary variables are not allowed.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite types \(T\), rational masses \(\mu_t>0\) summing to \(1\), rational type-level payoff constraints \(P\) and their projections \(P_I\), reservation payoffs \(r_t\), and an exact evaluator \(V(q)\) for rational coalition masses \(q\in[0,\mu]\), determine whether there is a grand-coalition allocation \(x\in P_T\) with \(\sum_t\mu_t x_t\le V(\mu)\) and \(x_t\ge r_t\), that is efficient under the paper's definition (no feasible \(y\) has \(y_t>x_t\) for every type) and admits no blocking coalition: there are no nonzero \(q\) and \(p\in P_{I(q)}\) such that \(\sum_{t:q_t>0}q_t p_t\le V(q)\) and \(p_t>x_t\) for every type with \(q_t>0\).
A society is given by its support \(T\): the list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Input also includes a polyhedron \(P\subseteq\mathbb R^T\) described by \(m\) non-strict rational linear inequalities, rational reservation payoffs \(r_t\), and a finitely encoded exact evaluator \(V\) returning rational worths on rational vectors \(q\in[0,\mu]\), in time polynomial in its encoding and the query bit length. Payoffs, reservations, and worths may have either sign; there are no integer or auxiliary variables.
For \(I\subseteq T\), let \(P_I\) be the coordinate projection of \(P\), obtained by existentially extending coordinates outside \(I\) to a point of \(P\). For nonzero rational \(q\in[0,\mu]\), put \(I(q)=\{t:q_t>0\}\) and \(F(q)=\{p\in P_{I(q)}:\sum_{t\in I(q)}q_tp_t\le V(q)\}\). Allocations and coalition payoffs are real and constant within each participating type.
Assume cohesiveness: for every finite rational decomposition \(\mu=\sum_{j=1}^k q^j\) into nonzero nonnegative vectors, \(V(\mu)\ge\sum_{j=1}^k V(q^j)\). No continuity or homogeneity of \(V\) is assumed.
A core allocation is \(x\in F(\mu)\) with \(x_t\ge r_t\) for every type, such that no \(y\in F(\mu)\) strictly improves every coordinate, and no nonzero rational \(q\in[0,\mu]\) admits \(p\in F(q)\) with \(p_t>x_t\) for every \(t\in I(q)\). Coalitions may include the whole society.
Is deciding whether a core allocation exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and the total input bit length \(L\), including the evaluator encoding.
For finite agents, core nonemptiness is \(\Sigma_2^{\mathrm P}\)-hard even with cohesive worths, polynomial-time worth evaluators, and purely real linear constraints without auxiliary variables; it is also in \(\Sigma_2^{\mathrm P}\). [Source](https://arxiv.org/pdf/1401.3852). No result settling the precise mass problem above was identified in the literature search.
Core nonemptiness is \(\mathrm{NP}\)-hard. Under the stated evaluator model, it is actually undecidable, even for \(m=\tau=1\).
I first prove hardness using a direct reduction from satisfiability. This reduction uses only polynomially many exceptional coalitions, each with a polynomial-length encoding. I then prove the stronger undecidability result, which uses the absence of any bound on coalition query lengths.
Let \(\varphi\) be a formula in conjunctive normal form with at most three literals per clause. Pad with unused variables so that its number of variables satisfies \(n\ge3\). Repeated literals within a clause may be removed.
For each variable, introduce two types corresponding to its positive and negative literals. Introduce two further types, denoted \(z\) and \(b\). These are actual supported types, with positive masses.
Choose a power of two \(D\ge16n\), and set
\[ a=\frac1D,\qquad B=na. \]
Assign mass \(a\) to every literal type, and set
\[ \mu_z=\frac34,\qquad \mu_b=\frac14-2na. \]
These masses sum to one. Moreover, \(\mu_b\ge1/8\), so all masses are positive dyadic rationals.
Reservations are zero for the literal types and type \(z\). Set
\[ r_b=-\frac{B}{\mu_b}. \]
Write \(u_\ell\) for the payoff coordinate of literal type \(\ell\). Define \(P\) by
\[ 0\le u_\ell\le1 \quad\text{for every literal type }\ell, \]
\[ 0\le z\le1, \]
\[ u_{v_i}+u_{\neg v_i}\le1+z \quad\text{for every variable }v_i, \]
and
\[ \mu_b b+a\sum_\ell u_\ell=0. \]
Represent the last equality by two non-strict inequalities. Consequently,
\[ \tau=2n+2,\qquad m=5n+4. \]
All variables appearing here are payoff coordinates of supported types; there are no auxiliary or integer variables.
Let \(\mathcal S\) consist of:
For \(S\in\mathcal S\), define the rational coalition \(q^S\) by
\[ q^S_z=\frac12,\qquad q^S_b=0,\qquad q^S_\ell= \begin{cases} a,&\ell\in S,\\ 0,&\ell\notin S. \end{cases} \]
Each coalition lies in \([0,\mu]\). Every set \(S\) has size \(d\) satisfying \(1\le d\le3\le n\).
Define the indicator
\[ \beta(q)= \begin{cases} 1,&q=\mu\text{ or }q=q^S\text{ for some }S\in\mathcal S,\\ 0,&\text{otherwise}, \end{cases} \]
and define the exact evaluator by
\[ V(q)=\sum_t r_tq_t+B\beta(q). \]
Thus
\[ V(\mu)=r_b\mu_b+B=0, \qquad V(q^S)=B. \]
The evaluator merely performs rational comparisons, checks membership in an explicitly encoded list of supports, and computes a rational affine expression. It runs in polynomial time in its encoding length and the query bit length.
Consider any finite rational decomposition
\[ \mu=\sum_{j=1}^k q^j. \]
Every coalition with \(\beta(q^j)=1\) has its \(z\)-coordinate at least \(1/2\). Since the total \(z\)-mass is \(3/4\), at most one component can have indicator one. Therefore,
\[ \begin{aligned} \sum_{j=1}^k V(q^j) &=\sum_t r_t\mu_t+B\sum_{j=1}^k\beta(q^j)\\ &=-B+B\sum_{j=1}^k\beta(q^j)\\ &\le0=V(\mu). \end{aligned} \]
This verifies the cohesiveness promise for every decomposition.
For every point \(p\in P\), the defining equality gives
\[ \sum_t\mu_tp_t =a\sum_\ell p_\ell+\mu_zp_z+\mu_bp_b =\mu_zp_z. \]
Since \(V(\mu)=0\) and \(p_z\ge0\), every allocation \(x\in F(\mu)\) satisfies
\[ x_z=0,\qquad \sum_t\mu_tx_t=0. \]
It consequently satisfies
\[ x_{v_i}+x_{\neg v_i}\le1 \quad\text{for every variable }v_i. \]
Such an allocation also meets the required grand-coalition efficiency condition: if every coordinate of \(y\) strictly exceeded the corresponding coordinate of \(x\), positivity of all masses would imply
\[ \sum_t\mu_ty_t>\sum_t\mu_tx_t=0, \]
contradicting \(y\in F(\mu)\).
Suppose \(x_t\ge r_t\) for every type and \(\beta(q)=0\). If \(p_t>x_t\) for every participating type, then
\[ \sum_{t\in I(q)}q_tp_t > \sum_{t\in I(q)}q_tx_t \ge \sum_tq_tr_t = V(q). \]
Hence \(p\notin F(q)\).
The same strict weighted-sum argument excludes blocking by \(q=\mu\).
Let \(x\in F(\mu)\) meet all reservations, and fix \(S\in\mathcal S\).
If \(x_\ell=1\) for some \(\ell\in S\), no point of \(P_{I(q^S)}\) can strictly improve that coordinate: every extension in \(P\) satisfies \(u_\ell\le1\). Thus \(q^S\) cannot block.
Conversely, suppose \(x_\ell<1\) for every \(\ell\in S\). Put \(d=|S|\). Since \(d\le n\),
\[ a\sum_{\ell\in S}x_\ell<ad\le an=B. \]
Choose a real \(\varepsilon>0\) small enough that
\[ \varepsilon< \min\left\{ \frac12,\ \min_{\ell\in S}(1-x_\ell),\ \frac{B-a\sum_{\ell\in S}x_\ell}{1+ad} \right\}. \]
Define a full extension \(\widehat p\) by
\[ \widehat p_z=2\varepsilon,\qquad \widehat p_\ell= \begin{cases} x_\ell+\varepsilon,&\ell\in S,\\ 0,&\ell\notin S, \end{cases} \]
and
\[ \widehat p_b=-\frac{a}{\mu_b}\sum_\ell\widehat p_\ell. \]
I check that \(\widehat p\in P\). Its literal coordinates lie in \([0,1]\), its \(z\)-coordinate lies in \([0,1]\), and the equality defining \(b\) holds. For each variable pair:
Thus every pair inequality holds.
The restriction of \(\widehat p\) to the participating coordinates therefore belongs to \(P_{I(q^S)}\). Its weighted payoff is
\[ \begin{aligned} \sum_tq^S_t\widehat p_t &=\frac12(2\varepsilon) +a\sum_{\ell\in S}(x_\ell+\varepsilon)\\ &=a\sum_{\ell\in S}x_\ell+(1+ad)\varepsilon\\ &<B=V(q^S). \end{aligned} \]
Every participating literal payoff strictly improves, and \(z\) improves from zero to \(2\varepsilon\). Hence \(q^S\) blocks.
We have proved the exact equivalence
\[ q^S\text{ does not block }x \quad\Longleftrightarrow\quad x_\ell=1\text{ for some }\ell\in S. \]
Suppose a core allocation exists. For every variable, its exceptional pair coalition forces at least one associated literal payoff to equal one. The pair inequality and nonnegativity then force the two payoffs to be exactly zero and one. Interpret the literal assigned payoff one as true.
Every exceptional clause coalition also forces one of its literal payoffs to equal one. Consequently, this assignment satisfies \(\varphi\).
Conversely, suppose \(\varphi\) has a satisfying assignment. Give each true literal payoff one and each false literal payoff zero, and set
\[ x_z=0,\qquad x_b=r_b. \]
Exactly \(n\) literal coordinates equal one, so the equality defining \(b\) holds. All other constraints and reservations hold, and the grand-coalition weighted payoff is zero.
Every exceptional coalition contains a literal with payoff one and therefore cannot block. Nonexceptional coalitions and the grand coalition cannot block by the preceding arguments. Grand-coalition efficiency also holds. Thus this is a core allocation.
Therefore,
\[ \varphi\text{ is satisfiable} \quad\Longleftrightarrow\quad \text{the constructed society has a core allocation}. \]
Let \(N\) be the formula’s binary encoding length. Choosing the least power of two satisfying \(D\ge16n\) gives coefficients of \(O(\log(n+1))\) bits. Under a dense encoding of the inequalities, the total constructed input length satisfies
\[ L=O\!\left(N^2\log(N+2)\right), \]
including the evaluator encoding. The reduction can be implemented in \(O(N^3)\) bit operations. All exceptional coalition encodings have polynomial length. This establishes \(\mathrm{NP}\)-hardness in the stated parameters \(m,\tau,L\).
The unrestricted evaluator model permits a stronger construction.
Let \(M\) be an arbitrary deterministic Turing machine run on blank input. Construct a society with
\[ \tau=1,\qquad \mu=1,\qquad r=0,\qquad P=\{p\in\mathbb R:p\ge0\}. \]
Thus \(m=1\).
For a rational \(q\in[0,1]\), let \(h(q)\) be the binary bit length of its denominator after reduction to lowest terms. Define
\[ \gamma_M(q)= \begin{cases} 1,&q=1,\\ 1,&\frac12<q<1 \text{ and }M\text{ halts within }h(q)\text{ steps},\\ 0,&\text{otherwise}, \end{cases} \]
and
\[ V_M(q)=-q+\gamma_M(q). \]
This is a valid polynomial-time exact evaluator. For query bit length \(H\), reducing the rational and simulating \(M\) for at most \(h(q)\le H\) steps both take polynomial time in \(H+|M|\). A straightforward implementation has a uniform polynomial bound, for example \(O((H+|M|+1)^4)\). Its encoding is constructed from \(M\) in polynomial time and has length \(O(|M|)\).
We have \(V_M(1)=0\). In any finite rational decomposition
\[ 1=\sum_{j=1}^kq^j, \]
a component receiving bonus one has mass strictly greater than \(1/2\). At most one component can receive that bonus. Hence
\[ \sum_{j=1}^kV_M(q^j) =-1+\sum_{j=1}^k\gamma_M(q^j) \le0=V_M(1). \]
The promise holds independently of whether \(M\) halts.
Because \(P\) requires nonnegative payoff and \(V_M(1)=0\), the only grand-coalition feasible allocation is \(x=0\). It meets the reservation and efficiency requirements.
If \(M\) never halts, every proper nonzero coalition has worth \(-q<0\). Its feasible set is empty because coalition payoffs must be nonnegative. Thus \(x=0\) is a core allocation.
If \(M\) halts after \(s\) steps, choose an integer \(k\ge\max\{s,2\}\) and set
\[ q=\frac12+2^{-k}. \]
Its reduced denominator is \(2^k\), so \(h(q)=k+1\ge s\). Consequently,
\[ V_M(q)=1-q>0. \]
The payoff
\[ p=\frac{1-q}{2q}>0 \]
is feasible and satisfies
\[ qp=\frac{1-q}{2}\le V_M(q). \]
It strictly improves \(x=0\), so the core is empty.
We have therefore proved
\[ \text{the constructed society has a core allocation} \quad\Longleftrightarrow\quad M\text{ does not halt}. \]
A core-existence decider would decide nonhalting for arbitrary Turing machines, contradicting undecidability of the halting problem.
Under the exact assumptions in the question, there is no total decision algorithm, hence no decision running-time bound in \(m,\tau,L\). This already holds for \(m=\tau=1\), with uniformly polynomial-time evaluators.
Independently, the direct satisfiability reduction proves \(\mathrm{NP}\)-hardness using only finitely many explicitly recognizable exceptional coalitions of polynomial encoding length. Thus the hardness conclusion does not depend solely on the unbounded-query phenomenon used in the undecidability proof.
⟨structured verdict parsed — rendered above⟩
The undecidability construction is correct under the stated evaluator model. It establishes that core existence has no total decision algorithm, even when \(m=\tau=1\).
The direct satisfiability reduction is also sound in substance. Its only identified gap is an unstated convention excluding empty clauses. This is a minor issue in that reduction and does not affect the independent undecidability result.
The construction uses precisely \(2n+2\) supported types. Since \(D\ge16n\),
\[ na\le\frac1{16},\qquad \mu_b=\frac14-2na\ge\frac18. \]
Thus all masses are positive dyadic rationals, and their sum is one.
The inequality count is correct: literal bounds contribute \(4n\), the bounds on \(z\) contribute two, variable-pair constraints contribute \(n\), and the equality contributes two. Hence \(m=5n+4\).
Every variable is a payoff coordinate of a supported type. There are no auxiliary or integer variables.
The exceptional coalitions satisfy the coordinate bounds \(0\le q^S\le\mu\). Equality testing against the explicitly encoded exceptional list and evaluating the rational affine expression take polynomial time in the evaluator encoding and query length.
The worth calculations are correct:
\[ r_b\mu_b=-B,\qquad V(\mu)=0,\qquad V(q^S)=B. \]
The cohesiveness argument applies to every finite rational decomposition. Every component receiving a bonus has \(z\)-mass at least \(1/2\), whereas the total available \(z\)-mass is \(3/4\). Therefore at most one component receives a bonus. Summing the affine terms gives exactly \(-B\), proving the claimed inequality. Negative worths cause no difficulty because the task expressly permits them.
The equality defining \(b\) gives, for every point of \(P\),
\[ \sum_t\mu_tp_t=\mu_zp_z. \]
Since \(P\) requires \(p_z\ge0\) and grand-coalition feasibility requires this weighted sum to be at most zero, every grand-coalition feasible allocation has \(x_z=0\) and weighted sum zero.
Consequently, every literal pair has sum at most one. Positivity of all masses also makes the stated efficiency argument valid: strict improvement in every coordinate would strictly increase the weighted sum above zero.
For an individually rational allocation, strict improvement in every participating coordinate implies
\[ \sum_{t\in I(q)}q_tp_t> \sum_{t\in I(q)}q_tx_t \ge\sum_tq_tr_t. \]
The first inequality is strict because \(q\) is nonzero and every participating weight is positive. For nonexceptional coalitions, the last expression equals \(V(q)\). Thus they cannot block.
The separately stated argument for the whole society is also valid.
For nonempty \(S\), the blocking characterization is correct.
If a selected literal already has payoff one, its upper bound in every full extension prevents strict improvement in the projection.
Conversely, when all selected literal payoffs are below one, every quantity in the displayed minimum is positive. The proposed extension respects the literal and \(z\) bounds. The variable-pair check is valid, including pairs with both literals selected, because their original sum is at most one. The coordinate \(b\) satisfies its defining equality and has no additional constraint in \(P\).
Crucially, the argument supplies a full point of \(P\), so membership in the coordinate projection is justified. Coalition feasibility does not require that this extension meet the reservation payoff for the nonparticipating type \(b\).
The weighted-payoff calculation is correct, and the prescribed bound on \(\varepsilon\) makes it strictly less than \(B\). All participating coordinates strictly improve.
Where: “Every set \(S\) has size \(d\) satisfying \(1\le d\le3\le n\),” and the subsequent exceptional-coalition argument.
Issue: A CNF formula with “at most three literals per clause” can contain an empty clause unless a convention excludes it. Such a clause produces \(S=\varnothing\), contradicting \(1\le d\). The displayed \(\varepsilon\) choice then contains a minimum over an empty set, and the asserted strict inequality
\[ a\sum_{\ell\in S}x_\ell<ad \]
is false when \(d=0\).
Severity: Minor. This concerns a routine source-instance convention or edge case; it does not undermine the construction for nonempty clauses or the independent undecidability proof.
Minimum clarification: Explicitly restrict the source satisfiability problem to formulas with nonempty clauses, or explicitly address empty clauses in the construction and blocking verification.
Subject to that convention, both directions of the reduction follow.
Variable-pair coalitions force exactly one literal payoff per variable to be one. Clause coalitions then enforce satisfaction. Conversely, a satisfying assignment gives exactly \(n\) literal coordinates equal to one, making \(x_b=r_b\) consistent with the defining equality. All feasibility, reservation, efficiency, and nonblocking conditions are checked.
Choosing the least suitable power of two gives coefficients with \(O(\log(n+1))\) bits. The stated dense-encoding bound
\[ L=O\!\left(N^2\log(N+2)\right) \]
is consistent with the numbers of rows, coordinates, and exceptional coalitions, including the evaluator encoding. The claimed \(O(N^3)\) construction time is a valid conservative polynomial bound.
The one-type instance meets all requirements: positive mass one, rational reservation zero, and one non-strict rational inequality defining \(P\).
For a query of bit length \(H\), reducing the rational denominator and simulating the encoded machine for at most \(h(q)\le H\) steps take polynomial time in \(H+|M|\). The claimed fourth-degree bound is a permissible conservative bound under conventional binary encodings and straightforward simulation.
The evaluator returns rational values exactly. Its encoding has size \(O(|M|)\). No assumption requires a uniform bound on the lengths of all possible coalition queries, so using denominator length as a simulation budget is legitimate.
Every component receiving bonus one has mass strictly greater than \(1/2\), including the component \(q=1\). Therefore at most one component in a decomposition receives a bonus.
The affine terms sum to \(-1\), giving total worth at most zero, equal to \(V_M(1)\). This proves cohesiveness regardless of whether \(M\) halts.
Grand-coalition feasibility forces \(x=0\), which meets the reservation and efficiency requirements.
If \(M\) never halts, every proper nonzero rational coalition has worth \(-q<0\). Its projected payoff domain is nonnegative, so its feasible set is empty. The whole society cannot strictly improve on zero either. Thus the stated allocation is a core allocation.
For \(k\ge2\),
\[ q=\frac12+2^{-k} =\frac{2^{k-1}+1}{2^k}. \]
The numerator is odd, so the reduced denominator is indeed \(2^k\), with binary length \(k+1\). Hence the chosen query detects halting within \(s\) steps.
The query is rational and lies strictly between \(1/2\) and one. Its worth is positive. The proposed positive payoff belongs to \(P\), and its weighted payoff is half the worth. It therefore blocks the only possible grand-coalition allocation.
The construction establishes the claimed equivalence between core existence and nonhalting on blank input for an arbitrary encoded deterministic Turing machine.
The undecidability theorem used here applies to precisely that machine problem. A total core-existence decider would decide it through the finite, polynomial-time construction. Therefore the conclusion that no total decision algorithm exists is justified, already for fixed \(m=\tau=1\).
Clarify the treatment of empty clauses in the satisfiability reduction. No substantive repair is needed for the undecidability argument, and no other mathematical gaps were identified.
⟨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.