Answer: Polynomial-time solvable in \(m,\tau,r,d,L\).
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateGiven BCG ⟨N, Ω, P, (Ij), (≽j)⟩with risk- neutral agents, a grand contract cN is in the ex-interim core of the game if and only if for all S ⊆N, for all information sets I ∈I∨ S , E[ω(S)|I] ≤ X j∈S E[cN j |I] Checking whether a grand contract belongs to the ex-post core of a BCG is conceptually simple.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite worlds Ω with rational prior \(P\), type masses \(\mu_a\), a partition \(\Pi_a\) for each type, a feasible risk-neutral grand contract \(q_a(\omega)\), and coalition worth functions \(V_\omega(x)\) specified by rational production LPs, decide whether the contract is in the ex-interim core. Equivalently, for every nonzero \(x\in[0,\mu]\) and every positive-prior cell \(I\) in the common refinement \(\Pi^\vee_{A(x)}\) of the participating types’ partitions, test whether \(\mathbb{E}[V_\omega(x)\mid I]\le\sum_{a\in A(x)}x_a\mathbb{E}[q_a(\omega)\mid I]\), where \(A(x)=\{a:x_a>0\}\).
A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_a\). Here \(\tau\) is the support size, not the number of possible types; total mass need not equal one.
There are \(m\ge1\) explicitly listed worlds \(\Omega\), a rational common prior \(P\ge0\) with \(\sum_{\omega\in\Omega}P(\omega)=1\), and an explicitly listed information partition \(\Pi_a\) of \(\Omega\) for each type. Agents are risk-neutral, and utility is transferable within each world.
For each world, input nonnegative rational matrices \(D_\omega\in\mathbb Q_+^{r_\omega\times d_\omega}\), \(B_\omega\in\mathbb Q_+^{r_\omega\times\tau}\), and revenues \(c_\omega\in\mathbb Q_+^{d_\omega}\). Coalition worth is \(V_\omega(x)=\max\{c_\omega^\top y:D_\omega y\le B_\omega x,\ y\ge0\}\), promised finite for every \(0\le x\le\mu\).
The given grand contract specifies rational per-unit payments \(q_a(\omega)\), which may have either sign and need not be measurable with respect to \(\Pi_a\); feasibility means \(\sum_a\mu_aq_a(\omega)\le V_\omega(\mu)\) in every world.
A coalition is any real vector \(x\in\prod_a[0,\mu_a]\setminus\{0\}\), including the grand coalition. Write \(A(x)=\{a:x_a>0\}\), and let \(\Pi^\vee_{A(x)}\) consist of the nonempty intersections of one cell from each participating type's partition.
Define continuous ex-interim core membership by requiring \(\mathbb E[V_\omega(x)\mid I]\le\sum_{a\in A(x)}x_a\mathbb E[q_a(\omega)\mid I]\) for every such coalition and every \(I\in\Pi^\vee_{A(x)}\) with \(P(I)>0\). Equality does not block.
Let \(L\) be the total binary input length, \(r=\max_\omega r_\omega\), and \(d=\max_\omega d_\omega\); express running times in \(m,\tau,r,d,L\).
Is this continuous ex-interim core membership problem solvable in polynomial time in \(m,\tau,r,d,L\), or is it \(\mathrm{coNP}\)-hard under polynomial-time many-one reductions?
For finite societies, risk-neutral ex-interim core membership is characterized by the corresponding conditional inequalities for all coalitions and common-refinement cells; this characterization gives no polynomial-time guarantee. [Ieong–Shoham](https://ai.stanford.edu/~shoham/www%20papers/IeongShohamAAAI08.pdf)
Discrete core nonmembership for linear production games is \(\mathrm{NP}\)-complete, even without uncertainty. [Fang et al.](https://link.springer.com/article/10.1007/s001820200106)
Cores of nonatomic linear production games without uncertainty have been characterized; no result settling the precise Bayesian membership problem above was located. [Billera–Raanan](https://pubsonline.informs.org/doi/10.1287/moor.6.3.420)
The problem is solvable in polynomial time in \(m,\tau,r,d,L\).
The key point is that every strict blocking inequality can be witnessed by a coalition containing a positive mass of every type. Consequently, only the common refinement of all information partitions needs to be checked.
For any \(S\subseteq\Omega\) and \(0\le x\le\mu\), define
\[ F_S(x)=\sum_{\omega\in S}P(\omega)\left(V_\omega(x)-\sum_{a=1}^{\tau}x_aq_a(\omega)\right). \]
For \(P(S)>0\), the conditional inequality in the question is equivalent to \(F_S(x)\le0\). Summing over all types is legitimate because types outside \(A(x)\) have zero coalition mass.
We will use monotonicity:
\[ 0\le x\le x'\le\mu\quad\Longrightarrow\quad V_\omega(x)\le V_\omega(x'). \]
Indeed, nonnegativity of \(B_\omega\) implies \(B_\omega x\le B_\omega x'\), so every production plan feasible for \(x\) is feasible for \(x'\).
Also, \(V_\omega(0)=0\). Otherwise, a feasible production plan with positive revenue at zero resources could be scaled arbitrarily, contradicting the finiteness promise.
Let \(\mathcal J=\Pi^\vee_{\{1,\ldots,\tau\}}\). Its cells partition \(\Omega\), so there are at most \(m\) cells.
Lemma. The conditional inequalities defining membership hold if and only if
\[ F_J(x)\le0 \]
for every \(J\in\mathcal J\) with \(P(J)>0\) and every \(0\le x\le\mu\).
Proof, forward direction. Suppose membership holds, but \(F_J(x)>0\) for some such \(J,x\). For \(0<\varepsilon<1\), put
\[ x^\varepsilon=x+\varepsilon(\mu-x). \]
Then \(0<x^\varepsilon_a\le\mu_a\) for every type, because every \(\mu_a\) is positive. Thus \(A(x^\varepsilon)=\{1,\ldots,\tau\}\), and \(J\) is an admissible information cell for this coalition.
Define the finite, nonnegative number
\[ K=\sum_{\omega\in J}P(\omega)\sum_{a=1}^{\tau}(\mu_a-x_a)|q_a(\omega)|. \]
By monotonicity of production worth and linearity of payments,
\[ \begin{aligned} F_J(x^\varepsilon) &\ge F_J(x) -\varepsilon\sum_{\omega\in J}P(\omega) \sum_{a=1}^{\tau}(\mu_a-x_a)q_a(\omega)\\ &\ge F_J(x)-\varepsilon K. \end{aligned} \]
Choose \(\varepsilon\) sufficiently small that \(\varepsilon K<F_J(x)\); if \(K=0\), any \(\varepsilon\in(0,1)\) works. Then \(F_J(x^\varepsilon)>0\), contradicting membership.
This argument permits signed payments and requires no continuity assumption.
Proof, reverse direction. Let \(x\ne0\), and let \(I\in\Pi^\vee_{A(x)}\) satisfy \(P(I)>0\). The refinement \(\mathcal J\) refines every participating type’s partition. Therefore \(I\) is a disjoint union of cells of \(\mathcal J\), and
\[ F_I(x)=\sum_{\substack{J\in\mathcal J\\J\subseteq I}}F_J(x). \]
Every positive-probability summand is nonpositive by hypothesis; every zero-probability summand is zero. Hence \(F_I(x)\le0\), as required. This proves the lemma.
For each positive-probability \(J\in\mathcal J\), define rational coefficients
\[ g_{Ja}=\sum_{\omega\in J}P(\omega)q_a(\omega). \]
Solve the following rational linear program, with variables \(x\) and a separate production vector \(y_\omega\) for each \(\omega\in J\):
\[ Z_J=\max\left\{ \sum_{\omega\in J}P(\omega)c_\omega^\top y_\omega -\sum_{a=1}^{\tau}g_{Ja}x_a: \begin{array}{l} 0\le x\le\mu,\\ D_\omega y_\omega\le B_\omega x,\quad y_\omega\ge0 \quad(\omega\in J) \end{array} \right\}. \]
For fixed \(x\), production decisions in distinct worlds have separate constraints. Their optimized contribution is precisely \(\sum_{\omega\in J}P(\omega)V_\omega(x)\). Consequently,
\[ Z_J=\max_{0\le x\le\mu}F_J(x). \]
The program is feasible, since all variables may be zero. Its objective is bounded above: monotonicity gives \(V_\omega(x)\le V_\omega(\mu)\), and payments are bounded on \(0\le x\le\mu\). A feasible linear program with finite optimal value attains its optimum.
The zero solution gives \(Z_J\ge0\). Hence the lemma yields the exact decision rule:
\[ \text{All conditional core inequalities hold} \quad\Longleftrightarrow\quad Z_J=0\text{ for every positive-probability }J\in\mathcal J. \]
In particular, equality is accepted, as required.
If grand-contract feasibility is part of membership, additionally compute \(V_\omega(\mu)\) in every world and check
\[ \sum_{a=1}^{\tau}\mu_aq_a(\omega)\le V_\omega(\mu). \]
These checks include zero-probability worlds and require at most \(m\) additional production LPs.
Construct \(\mathcal J\) by assigning each world the tuple of its cell labels in the \(\tau\) partitions and grouping identical tuples. This takes polynomial time and produces at most \(m\) cells; there is no need to enumerate coalitions.
Each cell LP has at most
\[ N=\tau+md \]
variables and, counting bounds and nonnegativity constraints, at most
\[ M=2\tau+m(r+d) \]
inequalities.
Every objective coefficient is a sum of at most \(m\) products of input rationals. Such sums can be computed exactly with polynomial bit length: a common denominator formed from the input denominators has bit length bounded by their total bit length. All other coefficients come directly from the input.
Rational linear programming admits polynomial-time algorithms in the dimensions and binary encoding length, including exact determination of whether the optimum is zero. This is the standard polynomial-time LP theorem; see [Karmarkar’s original paper](https://www.stat.uchicago.edu/~lekheng/courses/302/classics/karmarkar.pdf).
There are at most \(m\) cell LPs and at most \(m\) feasibility LPs. Thus a valid overall bit-complexity bound is
\[ m\bigl(\tau+m(r+d)+L\bigr)^{O(1)}. \]
The continuous coalition model is essential to the proof: missing types can contribute arbitrarily small positive masses, thereby supplying their information while preserving an existing strict gain.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time conclusion is correct. The refinement lemma and LP formulation are sound, including signed payments, real coalition masses, strict blocking, and zero-probability worlds. No major or minor mathematical issues were found.
For a positive-probability cell \(S\), multiplying the conditional inequality by \(P(S)>0\) gives exactly \(F_S(x)\le0\). Including all types in the payment sum is valid because \(x_a=0\) for nonparticipating types.
The stated monotonicity is correct: \(B_\omega\ge0\) implies that increasing \(x\) weakly enlarges the feasible production set. Neither the sign of payments nor measurability of the contract is needed.
The assertion \(V_\omega(0)=0\) is also correct. The zero plan is feasible, and any feasible positive-revenue plan at zero resources could be scaled without limit, violating the finiteness promise.
The perturbation
\(x^\varepsilon=x+\varepsilon(\mu-x)\)
satisfies \(0<x^\varepsilon_a\le\mu_a\) for every type whenever \(0<\varepsilon<1\). This uses the explicitly assumed positivity of every \(\mu_a\).
Consequently, every cell of the full refinement is admissible for this perturbed coalition.
The displayed gain bound is correct. Production worth cannot decrease, and the payment change is exactly linear in \(\varepsilon\). The absolute-value bound defining \(K\) is valid even for signed payments.
Since \(K\) is finite, a sufficiently small positive \(\varepsilon\) preserves any strict positive gain. The separate treatment of \(K=0\) is correct. Thus any violation on a full-refinement cell yields an admissible blocking coalition.
This is the crucial reduction, and it requires no unproved continuity assertion.
Every cell of a participating-types refinement is a disjoint union of full-refinement cells. Additivity of the unnormalized sums therefore gives the stated identity for \(F_I(x)\).
Positive-probability constituent cells have nonpositive gains by hypothesis. A zero-probability cell contributes zero because the prior is nonnegative and every world value and payment is finite.
The added vector \(x=0\) causes no discrepancy with the task’s exclusion of the zero coalition: its gain is zero. Both directions of the lemma are valid.
For each fixed \(x\), the production variables for different worlds are independent. Each world’s production problem is feasible and has finite optimal value by the promise. The standard attainment theorem for linear programs therefore applies.
Multiplication by \(P(\omega)\ge0\) preserves the optimized contribution. Worlds with \(P(\omega)=0\) contribute zero and do not affect this equivalence.
Thus the cell LP optimizes exactly the stated gain. Its objective is bounded above by monotonicity of worth and boundedness of the linear payment function on \(0\le x\le\mu\). Unbounded production variables do not invalidate the argument: a feasible LP with finite optimal value attains its optimum.
The zero solution is feasible and has objective zero, so \(Z_J\ge0\). Therefore absence of a strict positive gain is equivalent to \(Z_J=0\).
This correctly accepts equality and checks all relevant coalitions through the refinement lemma. It does not substitute weak blocking for the task’s strict blocking criterion.
The proposed additional production LPs correctly test feasibility in every world, including worlds of zero prior probability.
The output explicitly addresses both the conditional inequalities alone and membership with grand-contract feasibility included. Under either interpretation, its polynomial-time conclusion holds.
Grouping worlds by their tuples of partition-cell labels constructs the full refinement in polynomial time. There are at most \(m\) nonempty cells.
The variable bound \(N=\tau+md\) and inequality bound \(M=2\tau+m(r+d)\) correctly include coalition bounds, production constraints, and production nonnegativity.
The computed rational coefficients have polynomial bit length. Products and sums of at most \(m\) input rationals do not require exponentially many bits; denominator products have bit length bounded by the sum of their factors’ bit lengths.
The invoked rational-LP theorem applies to these explicitly encoded rational programs, including exact comparison of the optimum with zero. The cited [Karmarkar paper](https://www.stat.uchicago.edu/~lekheng/courses/302/classics/karmarkar.pdf) discusses general rational LP reduction and exact optimality.
With at most \(m\) cell LPs and \(m\) feasibility LPs, the claimed bound \(m(\tau+m(r+d)+L)^{O(1)}\) is valid.
No additional mathematical clarification or repair is needed. The output resolves the assigned continuous membership problem.
⟨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.