Answer: Polynomial-time solvable; every valid instance has a core payoff, constructible in \(\operatorname{poly}(m,\tau,L)\) time.
Proposition 2 — class: other
Given a finite compatibility graph \(H=(U,F)\), a finite set of center types \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), and per-center supplies \(b_t\in\mathbb{Q}_{\ge 0}^{U}\), define each coalition mass \(x\in[0,\mu]\) to have supply \(s_u(x)=\sum_{t\in T}b_{t,u}x_t\) and worth \(\nu(x)=\max\{\sum_{\{u,v\}\in F}z_{uv}: z_{uv}\ge0,\ \sum_{e\ni u}z_e\le s_u(x)\ \forall u\in U\}\). Decide whether there is a nonnegative type-payoff vector \(p\) such that \(\sum_t\mu_t p_t=\nu(\mu)\) and \(\sum_t x_t p_t\ge\nu(x)\) for every coalition mass \(x\in[0,\mu]\).
Let \(H=(U,F)\) be a finite simple undirected compatibility graph, with \(m=|U|\). A society is given by its support: the list of the \(\tau\) center types \(T\) with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Thus \(\tau=|T|\) is the support size, not the number of possible types.
Each type has a supply vector \(b_t\in\mathbb Q_{\ge0}^{U}\), encoded in binary. A coalition is any real vector \(x\in\mathbb R^T\) satisfying \(0\le x_t\le\mu_t\); its supply is \(s_u(x)=\sum_{t\in T}b_{t,u}x_t\).
Its worth is \(\nu(x)=\max\{\sum_{e\in F}z_e:z\in\mathbb R_{\ge0}^{F},\ \sum_{e\ni u}z_e\le s_u(x)\text{ for every }u\in U\}\).
A core payoff is a vector \(p\in\mathbb R_{\ge0}^{T}\) satisfying \(\sum_{t\in T}\mu_tp_t=\nu(\mu)\) and \(\sum_{t\in T}x_tp_t\ge\nu(x)\) for every coalition \(x\). Here \(p_t\) is payoff per unit mass. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether a core payoff exists solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite agents owning disjoint vertex sets, with coalition worth equal to the maximum integral matching size in their induced subgraph, core existence belongs to \(\mathrm{coNP}\) and is \(\mathrm{coNP}\)-complete. [Chen, Hatschka and Simola](https://arxiv.org/html/2508.18449v1)
For that discrete problem, polynomial-time solvability holds when each agent owns at most two vertices, while \(\mathrm{coNP}\)-hardness holds already with at most three. [Benedek et al.](https://link.springer.com/article/10.1007/s10107-025-02200-9)
On the continuous side, cores of nonatomic linear production games have been characterized; the verified source does not state a complexity classification for the binary-support decision problem above. [Billera and Raanan](https://pubsonline.informs.org/doi/10.1287/moor.6.3.420)
Core existence is polynomial-time solvable. In fact, every valid instance has a core payoff, and one can construct such a payoff in time \( \operatorname{poly}(m,\tau,L) \).
The proof uses the fractional matching program exactly as stated in the task.
Write the grand coalition’s supply as
\( S_u=\sum_{t\in T}\mu_t b_{t,u} \).
Its worth is the optimal value of
\( \displaystyle \max_{z\ge 0}\left\{\sum_{e\in F}z_e:\sum_{e\ni u}z_e\le S_u\text{ for every }u\in U\right\}. \)
This program is feasible because \( z=0 \) is feasible. Its feasible region is bounded: for every edge \( e=\{u,v\} \), feasibility implies \( 0\le z_e\le\min(S_u,S_v) \). Thus its optimum is finite and attained.
The linear-programming dual is
\( \displaystyle \min_{y\ge 0}\left\{\sum_{u\in U}S_uy_u:y_u+y_v\ge 1\text{ for every }\{u,v\}\in F\right\}. \)
Indeed, the primal constraint for vertex \( u \) has dual variable \( y_u \), and the column for edge \( \{u,v\} \) has a coefficient of one in exactly the two endpoint constraints.
The dual is feasible: \( y_u=1 \) for every vertex suffices. By strong linear-programming duality, there is an optimal dual vector \( y^* \) satisfying
\( \displaystyle \sum_{u\in U}S_uy_u^*=\nu(\mu). \)
These conclusions also cover \( F=\varnothing \), when both optimal values are zero.
Define the payoff per unit mass of type \( t \) by
\( \displaystyle p_t=\sum_{u\in U}b_{t,u}y_u^*. \)
Because supplies and dual variables are nonnegative, \( p_t\ge 0 \).
For efficiency, interchange the finite sums:
\( \displaystyle \sum_{t\in T}\mu_tp_t =\sum_{u\in U}y_u^*\sum_{t\in T}\mu_tb_{t,u} =\sum_{u\in U}S_uy_u^* =\nu(\mu). \)
It remains to verify every coalition constraint. Fix any coalition \( x \) with \( 0\le x_t\le\mu_t \), and any matching vector \( z \) feasible for its supply \( s(x) \). Dual feasibility, followed by primal feasibility and nonnegativity of \( y^* \), gives
\( \displaystyle \sum_{e\in F}z_e \le \sum_{\{u,v\}\in F}(y_u^*+y_v^*)z_{\{u,v\}} = \sum_{u\in U}y_u^*\sum_{e\ni u}z_e \le \sum_{u\in U}y_u^*s_u(x). \)
By the definition of supply and payoff,
\( \displaystyle \sum_{u\in U}y_u^*s_u(x) = \sum_{t\in T}x_t\sum_{u\in U}b_{t,u}y_u^* = \sum_{t\in T}x_tp_t. \)
Taking the maximum over all feasible \( z \) therefore yields
\( \displaystyle \nu(x)\le\sum_{t\in T}x_tp_t. \)
Since \( x \) was arbitrary, every coalition constraint holds. Together with nonnegativity and efficiency, this proves that \( p \) is a core payoff.
The proof gives the following construction:
For an explicitly bounded dual formulation, impose \( y_u\le 1 \). This does not change the optimum. To see this, replace any feasible \( y \) by \( \widehat y_u=\min(y_u,1) \). For an edge, either both endpoint coordinates remain unchanged, or an endpoint becomes one and the other remains nonnegative; hence its covering constraint still holds. Since \( S_u\ge 0 \), truncation cannot increase the objective.
Consequently, one may solve a rational linear program with \( m \) variables and \( |F|+2m \) inequalities over a nonempty bounded feasible region. Its objective coefficients have polynomial encoding length: each \( S_u \) is a sum of at most \( \tau \) products of input rationals, and a common denominator can be obtained by multiplying their denominators, whose total bit length is polynomial in \( L \).
The standard polynomial-time theorem for rational linear programming therefore applies. Since \( |F|\le m(m-1)/2 \), solving this program, together with the \( O(m\tau) \) rational arithmetic operations before and after it, takes \( \operatorname{poly}(m,\tau,L) \) bit operations. The returned rational payoff also has polynomial encoding length.
For the existence decision alone, every valid input receives “yes”; the polynomial construction establishes the stronger search result.
The cited discrete model uses coalition subsets and maximum integral matchings. ([Chen, Hatschka and Simola](https://arxiv.org/html/2508.18449v1)) Here, coalition worth is already a linear-programming optimum. Its optimal dual prices certify both grand-coalition efficiency and all coalition inequalities, as proved above. Thus the cited discrete hardness does not establish hardness for this continuous model.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated continuous problem: every valid instance has a core payoff, and the proposed construction runs in \(\operatorname{poly}(m,\tau,L)\) bit operations. No major or minor mathematical issues were found.
Each \(S_u=\sum_{t\in T}\mu_tb_{t,u}\) is finite, rational, and nonnegative. Thus \(z=0\) is feasible. For every edge \(e=\{u,v\}\), nonnegativity and the endpoint capacity constraints imply
\[
0\le z_e\le\min(S_u,S_v).
\]
The feasible region is closed and bounded in a finite-dimensional space, so the objective attains a finite maximum. The argument also covers an empty edge set.
The stated dual is correct. Each edge variable has coefficient one in exactly its two endpoint constraints, producing the dual constraint \(y_u+y_v\ge1\). The primal maximization with upper-bound constraints and nonnegative variables gives nonnegative dual variables.
The applicable strong-duality statement is that a feasible finite-dimensional linear program with finite optimal value has an attained dual optimum of equal value. The primal hypotheses were established, and the dual is explicitly feasible at \(y_u=1\). Therefore the asserted optimal vector \(y^*\) and equality
\[
\sum_{u\in U}S_uy_u^*=\nu(\mu)
\]
are justified. Zero objective coefficients, including those arising from vertices with zero supply, do not invalidate this application.
The definition \(p_t=\sum_{u\in U}b_{t,u}y_u^*\) produces a finite nonnegative payoff for every supported type. The efficiency calculation correctly interchanges finite sums and substitutes the definition of \(S_u\).
The calculation uses the required per-unit-mass convention: total payment to type \(t\) is \(\mu_tp_t\). There is no missing mass factor or division by \(\mu_t\).
The proof fixes an arbitrary real coalition \(x\) in the prescribed box and an arbitrary feasible fractional matching \(z\). Every inequality has the correct justification:
Taking the maximum is legitimate: coalition supplies are finite and nonnegative, and the same coordinate bounds used for the grand coalition establish attainment. The argument applies directly to irrational coalition coordinates as well as rational ones. Consequently, it verifies the full universal coalition condition.
The coordinatewise truncation \(\widehat y_u=\min(y_u,1)\) preserves every covering constraint. If neither endpoint changes, its constraint is unchanged. If an endpoint changes, that endpoint becomes one and the other remains nonnegative.
Since \(S_u\ge0\), truncation cannot increase the objective. Conversely, every feasible point of the bounded formulation is feasible for the original dual. These observations justify equality of the optimal values. The stated count of \(|F|+2m\) inequalities is correct when both coordinate bounds are counted.
The encoding argument is valid. Products of input rationals have polynomial bit length, and summing at most \(\tau\) such products using a product denominator keeps numerator and denominator lengths polynomial in the input length.
The applicable rational-linear-programming theorem provides an exact rational optimum in time polynomial in the explicitly encoded program’s length. Its hypotheses hold here: the constraints and objective are rational, the feasible region is nonempty and bounded, and the formulation has polynomial size because \(|F|\le m(m-1)/2\).
The \(O(m\tau)\) arithmetic operations used to form supplies and payoffs operate on numbers of polynomial bit length. Thus both the bit-operation running time and the returned payoff’s encoding length satisfy the claimed polynomial bounds. For decision alone, returning “yes” on every valid instance is justified by the existence proof.
Empty edge sets, isolated vertices, zero supply coordinates, all-zero supplies, and the zero coalition cause no failure. If the vertex set is empty, the empty programs and zero payoffs likewise satisfy the definitions.
The cited discrete model does use coalitions of agents and ordinary maximum matchings, consistent with the prover’s comparison. [Chen, Hatschka and Simola](https://arxiv.org/html/2508.18449v1) The continuous conclusion is established by the written argument independently of that citation.
Actionable feedback: No repair or additional clarification is required.
⟨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.