Answer: The problem is in \(\mathrm{P}\): every valid instance has a nonempty core, and a rational core vector is computable in time polynomial in \(m,\tau,L\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCORE-NONEMPTY with transferable utility is NP-complete.
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\geq 0\) summing to \(1\), and finitely many repeatable recipes \((a^j,w_j)\), define \(v(x)=\max\{\sum_j w_j\lambda_j:\sum_j a^j_t\lambda_j\leq x_t\ \forall t,\ \lambda_j\geq 0\}\) for each coalition composition \(0\leq x\leq\mu\). Does there exist a per-unit payoff vector \(p\geq 0\) with \(p\cdot\mu\leq v(\mu)\) and \(p\cdot x\geq v(x)\) for every \(x\leq\mu\)?
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.
The other input is \(m\) repeatable recipes \((a^j,w_j)\), with \(a^j\in\mathbb{Q}_{\geq0}^{T}\setminus\{0\}\) and \(w_j\in\mathbb{Q}\), all binary encoded. Let \(L\) be the total input bit length.
A coalition composition is any real vector \(x\) with \(0\leq x\leq\mu\), componentwise. Recipes may be used in arbitrary nonnegative real quantities; unused mass earns zero, and utility is transferable within every coalition.
Define \(v(x)=\max\{\sum_{j=1}^{m}w_j\lambda_j:\sum_{j=1}^{m}a_t^j\lambda_j\leq x_t\ \forall t\in T,\ \lambda\in\mathbb{R}_{\geq0}^{m}\}\).
The decision problem asks whether there exists \(p\in\mathbb{R}_{\geq0}^{T}\) such that \(p\cdot\mu\leq v(\mu)\) and \(p\cdot x\geq v(x)\) for every real \(0\leq x\leq\mu\).
Is this continuous core-nonemptiness decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite players with explicitly listed coalition values extended by maximizing over disjoint partitions, transferable-utility core nonemptiness is \(\mathrm{NP}\)-complete; it is in \(\mathrm{P}\) when the grand-coalition value is also supplied. [Conitzer–Sandholm](https://www.cs.cmu.edu/~sandholm/core_complexity.AIJ.pdf)
Core nonemptiness is known for finite-player linear production games. This is a neighboring result, rather than a verified complexity classification of the exact support-encoded mass problem above. [Owen](https://link.springer.com/article/10.1007/BF01681356)
The problem is in \(\mathrm{P}\). In fact, every valid instance has a nonempty core, and a rational core vector can be computed in time polynomial in \(m,\tau,L\).
The key is that the coalition inequalities are exactly the feasibility constraints of the grand coalition’s linear-programming dual.
Let \(A\) be the matrix whose columns are the recipe vectors \(a^j\), and let \(w=(w_1,\ldots,w_m)\). For any \(0\leq x\leq\mu\), the program defining \(v(x)\) is
\(\displaystyle \max\{w^\top\lambda:A\lambda\leq x,\ \lambda\geq0\}.\)
It is feasible because \(\lambda=0\) is allowed. To check boundedness, for each recipe \(j\) choose a coordinate \(t(j)\) with \(a_{t(j)}^j>0\); such a coordinate exists because \(a^j\neq0\). Every feasible vector satisfies
\(\displaystyle a_{t(j)}^j\lambda_j\leq(A\lambda)_{t(j)}\leq x_{t(j)}\leq\mu_{t(j)},\)
and consequently
\(\displaystyle 0\leq\lambda_j\leq\frac{\mu_{t(j)}}{a_{t(j)}^j}.\)
Thus the feasible set is closed and bounded, hence compact. The linear objective attains a finite maximum. This argument accommodates negative recipe rewards.
If \(m=0\), every coalition value is zero and \(p=0\) settles the problem. Henceforth assume \(m>0\).
Define the polyhedron
\(\displaystyle D=\{p\in\mathbb{R}_{\geq0}^{T}:A^\top p\geq w\}.\)
We prove that, for every \(p\geq0\),
\(\displaystyle p\cdot x\geq v(x)\ \text{for every }0\leq x\leq\mu \quad\Longleftrightarrow\quad p\in D.\)
Sufficiency. Suppose \(p\in D\). For any coalition composition \(x\) and any production vector \(\lambda\geq0\) satisfying \(A\lambda\leq x\),
\(\displaystyle w^\top\lambda\leq(A^\top p)^\top\lambda =p^\top A\lambda\leq p^\top x.\)
The first inequality uses \(\lambda\geq0\); the last uses \(p\geq0\). Maximizing over feasible \(\lambda\) proves \(v(x)\leq p\cdot x\), for every real coalition composition.
Necessity. Suppose all coalition inequalities hold. Fix a recipe \(j\), and define
\(\displaystyle \varepsilon_j=\min_{t:a_t^j>0}\frac{\mu_t}{a_t^j}.\)
This minimum is over a nonempty finite set of positive numbers, so \(\varepsilon_j>0\). The composition \(x=\varepsilon_j a^j\) satisfies \(0\leq x\leq\mu\). Using recipe \(j\) in quantity \(\varepsilon_j\) is feasible for this coalition, so
\(\displaystyle \varepsilon_j\,p\cdot a^j =p\cdot x\geq v(x)\geq\varepsilon_j w_j.\)
Dividing by \(\varepsilon_j\) gives \(p\cdot a^j\geq w_j\). Doing this for every recipe proves \(A^\top p\geq w\).
Strict positivity of the support masses ensures that every recipe can be tested at some positive scale.
For the grand coalition, the primal and dual programs are
\(\displaystyle \max_{\lambda\geq0}\{w^\top\lambda:A\lambda\leq\mu\}, \qquad \min_{p\geq0}\{\mu^\top p:A^\top p\geq w\}.\)
The primal is feasible and has a finite attained optimum by Section 1. The dual is also feasible: put \(s_j=\sum_{t\in T}a_t^j>0\), choose
\(\displaystyle M=\max\left\{0,\max_{1\leq j\leq m}\frac{w_j}{s_j}\right\},\)
and set \(p_t=M\) for every type. Then \(p\cdot a^j=Ms_j\geq w_j\).
Finite-dimensional linear-programming strong duality therefore applies: the dual has an optimal solution \(p^*\), and
\(\displaystyle \mu^\top p^*=v(\mu).\)
By Section 2, \(p^*\cdot x\geq v(x)\) for every \(0\leq x\leq\mu\). Hence \(p^*\) satisfies all the required conditions.
More precisely, the core is exactly
\(\displaystyle \{p\geq0:A^\top p\geq w,\ \mu^\top p=v(\mu)\},\)
the set of optimal dual solutions. Indeed, the coalition inequality at \(x=\mu\), combined with the budget inequality, forces equality.
On valid inputs, the decision algorithm simply returns YES. Even if input validation is required, the stated rational conditions can be checked in polynomial time.
To compute a core vector, solve the dual program. It has \(\tau\) variables, \(m\) recipe inequalities, and \(\tau\) nonnegativity constraints. Its rational coefficients are taken directly from the input. The standard polynomial-time theorem for rational linear programming therefore computes an exact rational optimal solution in time polynomial in \(m,\tau,L\).
The finite-player hardness result concerns coalition values generated through disjoint partitions; it does not supply hardness for the fractional production program here. [Conitzer–Sandholm](https://www.cs.cmu.edu/~sandholm/core_complexity.AIJ.pdf) identify grand-coalition value computation as the source of hardness in their transferable-utility model. Here that value is a linear-programming optimum, and the proof above directly establishes nonemptiness for the exact support-encoded model.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the exact support-encoded continuous problem. Every valid instance has a nonempty core, so the decision problem is in \(\mathrm{P}\). The stronger claim that a rational core vector can be computed in polynomial time is also justified. No major or minor issues were found.
The feasibility argument is correct: \(\lambda=0\) satisfies every constraint because \(x\geq0\).
For each recipe \(j\), the selected coordinate \(t(j)\) exists because the recipe is nonzero and componentwise nonnegative. Nonnegativity of all recipe coefficients and production quantities justifies
\[
a_{t(j)}^j\lambda_j\leq(A\lambda)_{t(j)}.
\]
The resulting coordinate bound on \(\lambda_j\) is finite. With finitely many recipes, these bounds make the feasible set bounded; the linear inequalities make it closed. Compactness and continuity therefore establish a finite, attained optimum.
Negative rewards cause no difficulty: the objective remains continuous on this compact set, and zero production remains feasible. The separately treated case \(m=0\) is correct.
Sufficiency is correct. Each inequality in the displayed chain uses the stated sign condition: \(A^\top p\geq w\) is multiplied by \(\lambda\geq0\), and \(A\lambda\leq x\) is multiplied by \(p\geq0\). Maximizing then yields the required inequality for every real coalition composition.
Necessity is correct. The minimum defining \(\varepsilon_j\) ranges over a finite, nonempty set. Every ratio is positive because all support masses are strictly positive. Thus division by \(\varepsilon_j\) is justified.
For positive recipe coordinates, the definition ensures \(\varepsilon_j a_t^j\leq\mu_t\); for zero coordinates, this holds automatically. The selected coalition is therefore admissible. Producing only recipe \(j\) in quantity \(\varepsilon_j\) is feasible and earns \(\varepsilon_jw_j\), including when that reward is negative.
The argument proves the stated equivalence for every \(p\geq0\). It neither discretizes the coalition domain nor assumes integral production.
The displayed dual has the correct objective, constraint directions, and sign restriction for the primal.
The explicit dual-feasibility construction is valid. Every \(s_j\) is strictly positive, and the chosen \(M\) satisfies both \(M\geq0\) and \(Ms_j\geq w_j\).
The strong-duality application is justified: these are finite-dimensional linear programs; the primal is feasible with a finite optimum, and the dual is feasible. The invoked theorem guarantees dual attainment and equality of optimal values. Consequently, the selected \(p^*\) satisfies both the budget constraint and every coalition inequality.
The exact core characterization also follows: the coalition inequality at \(x=\mu\) and the budget inequality force equality, while every dual optimum satisfies the coalition inequalities by Section 2.
Returning YES on every valid input correctly decides the specified problem. Checking the explicit rational validity conditions, if required, takes polynomial time in the input length.
The constructive claim correctly invokes polynomial-time rational linear programming: the dual has \(\tau\) variables and \(m+\tau\) inequalities, with rational data directly supplied by the input. Its feasibility and finite attained optimum have already been established. The standard exact rational optimization theorem therefore applies with polynomial bit complexity; no numerical approximation is being substituted for exact core membership.
The comparison accurately reflects the cited paper’s account of hardness through grand-coalition possibilities and polynomial solvability when those possibilities are supplied. [Conitzer–Sandholm](https://www.cs.cmu.edu/~sandholm/core_complexity.AIJ.pdf)
That comparison is contextual; the continuous classification follows from the explicit argument above. No missing lemma, additional hypothesis, 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.