Answer: Polynomial-time solvable: exact cutoff evaluation and rational atomic optimal-plan construction belong to \(\mathrm{FP}\).
Theorem 4 — class: algorithmic
Given a finite type set \(T\), rational population masses \(\mu\), a query mass vector \(x\le\mu\) with \(\lVert x\rVert_1\le\kappa\), and a rational piecewise-affine worth function \(w(q)\) on an explicitly encoded finite union of rational polyhedra of permitted profiles \(q\) with \(\lVert q\rVert_1\ge\delta>0\), compute the maximum welfare and an optimal coalition plan:
\[
\operatorname{OPT}_w(x)=\max_{\lambda\ge0}\left\{\int w(q)\,d\lambda(q):\int q\,d\lambda(q)=x\right\}.
\]
Can this transformed value and plan be computed in time polynomial in |T|, the input bit length, and the profile description, using \(\operatorname{OPT}_w(x)\) below the cutoff and the original worth above it?
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Permitted coalition profiles form \(Q=\bigcup_{j=1}^{m}P_j\), where each \(P_j\) is explicitly described by rational weak linear inequalities and lies in \(\{q\in\mathbb R_{\ge0}^{\tau}:q\le\mu,\ \lVert q\rVert_1\ge\delta\}\), with rational \(\delta>0\). On each piece, the worth \(w:Q\to\mathbb R_{\ge0}\) is given by a rational affine formula; formulas agree on overlaps.
Let \(k,r\) be positive integers with \(r\ge2\) and \(k<r/2\), and set \(\kappa=k/r\). A query is a binary-rational vector \(0\le x\le\mu\) with \(\lVert x\rVert_1\le\kappa\).
For \(Q_x=\{q\in Q:q\le x\}\), a coalition plan is a finite nonnegative Borel measure \(\lambda\) on \(Q_x\) satisfying \(\int_{Q_x}q\,d\lambda(q)=x\); its welfare is \(\int_{Q_x}w(q)\,d\lambda(q)\). Plan weights are arbitrary nonnegative real numbers, without integrality or probability normalization.
Define \(\operatorname{OPT}_w(x)=\max_{\lambda}\int_{Q_x}w(q)\,d\lambda(q)\), reporting infeasibility when no plan exists; the empty plan gives \(\operatorname{OPT}_w(0)=0\). The cutoff transformation uses this value when \(\lVert x\rVert_1\le\kappa\), and retains \(w(x)\) for permitted profiles above the cutoff. A finite rational atomic plan consists of rational profiles and nonnegative rational weights.
Can the cutoff value and a finite rational atomic optimal coalition plan be computed in polynomial time in \(m,\tau,L\), where \(L\) is the total binary input length, including \(k,r,\delta\), or is this computation NP-hard?
For \(n\) discrete agents with explicitly tabulated nonnegative coalition worths, the analogous transformation replaces each coalition of size at most \(kn/r\) by its optimal partition value and is computable in \(O\!\left(\sqrt n\,r^n2^{kn/r}/\bigl(k^{kn/r}(r-k)^{(r-k)n/r}\bigr)\right)\) arithmetic operations. [Service–Adams (2010)](https://cdn.aaai.org/ojs/7636/7636-13-11166-1-2-20201228.pdf)
No result settling this exact distribution-and-profile problem was identified in the literature search.
Result. For every supplied query, the cutoff value and a finite rational atomic optimal plan are computable exactly in deterministic polynomial time in \(m,\tau,L\). Infeasibility is also decidable in polynomial time. When feasible, an optimal plan with at most \(m\) atoms suffices.
The proof gives an exact reduction to rational linear programming.
1. Constructing the linear program. Write the input descriptions as
\(P_j=\{q\in\mathbb R^\tau:A_jq\le b_j\}\), with worth formula
\(w(q)=c_j^{\mathsf T}q+d_j\) on \(P_j\). All these coefficients are rational, and all vector inequalities below are coordinatewise.
Fix a query \(x\), and put
\(R_j=P_j\cap\{q:0\le q\le x\}\).
Thus \(Q_x=\bigcup_{j=1}^mR_j\).
For each piece introduce a scalar \(\alpha_j\) and a vector \(y_j\in\mathbb R^\tau\). Their intended meanings are the total plan weight assigned to that piece and its total contributed profile. Consider the following linear program:
\[ \begin{aligned} \text{maximize}\quad& \sum_{j=1}^m\bigl(c_j^{\mathsf T}y_j+d_j\alpha_j\bigr),\\ \text{subject to}\quad& \sum_{j=1}^m y_j=x,\\ &\alpha_j\ge0,\qquad 0\le y_j\le\alpha_jx &&(j=1,\ldots,m),\\ &A_jy_j\le b_j\alpha_j &&(j=1,\ldots,m),\\ &\mathbf1^{\mathsf T}y_j\ge\delta\alpha_j &&(j=1,\ldots,m). \end{aligned} \]
Here \(\mathbf1\) is the all-ones vector. The final inequalities explicitly encode the promised minimum coalition size.
Although the constraints contain \(\alpha_jx\), this is a linear program: \(x\) is fixed input data.
2. Every Borel plan gives a feasible LP solution with the same welfare. Each \(R_j\) is compact, because it is defined by weak linear inequalities and is contained in the bounded box \([0,x]\). Consequently, \(Q_x\) is compact. The worth function is Borel measurable and bounded on \(Q_x\), since it has finitely many affine formulas agreeing on overlaps.
Let \(\lambda\) be any feasible plan. Its total weight satisfies
\(\delta\lambda(Q_x)\le\int_{Q_x}\mathbf1^{\mathsf T}q\,d\lambda(q)=\mathbf1^{\mathsf T}x=\lVert x\rVert_1\).
In particular, its welfare is finite.
To avoid counting overlaps twice, partition \(Q_x\) into the disjoint Borel sets
\(E_1=R_1\) and
\(E_j=R_j\setminus\bigcup_{i<j}R_i\) for \(j>1\).
Define
\(\alpha_j=\lambda(E_j)\) and
\(y_j=\int_{E_j}q\,d\lambda(q)\).
Since the sets partition \(Q_x\), feasibility of the plan gives
\(\sum_jy_j=x\).
Every point of \(E_j\) satisfies
\(0\le q\le x\),
\(A_jq\le b_j\), and
\(\mathbf1^{\mathsf T}q\ge\delta\).
Integrating these inequalities proves all the remaining LP constraints.
Finally, the affine formula on \(P_j\) gives
\[
\int_{Q_x}w(q)\,d\lambda(q)
=\sum_{j=1}^m\int_{E_j}
\bigl(c_j^{\mathsf T}q+d_j\bigr)\,d\lambda(q)
=\sum_{j=1}^m
\bigl(c_j^{\mathsf T}y_j+d_j\alpha_j\bigr).
\]
Thus this passage preserves welfare exactly.
3. Every feasible LP solution gives an atomic plan with the same welfare. Suppose \((\alpha_j,y_j)_{j=1}^m\) is LP-feasible.
If \(\alpha_j=0\), the constraint \(0\le y_j\le\alpha_jx\) forces \(y_j=0\). Discard these indices.
For each remaining index define
\(q_j=y_j/\alpha_j\).
Dividing its constraints by the positive number \(\alpha_j\) yields
\(0\le q_j\le x\),
\(A_jq_j\le b_j\), and
\(\mathbf1^{\mathsf T}q_j\ge\delta\).
Hence \(q_j\in R_j\subseteq Q_x\).
Let \(D_q\) denote the unit Dirac measure at \(q\), and define
\(\lambda=\sum_{j:\alpha_j>0}\alpha_jD_{q_j}\).
This is a finite nonnegative Borel measure, with at most \(m\) atoms, and
\[
\int_{Q_x}q\,d\lambda(q)
=\sum_{j:\alpha_j>0}\alpha_jq_j
=\sum_{j=1}^my_j=x.
\]
It is therefore a feasible plan. Its welfare equals
\[
\sum_{j:\alpha_j>0}\alpha_jw(q_j)
=\sum_{j=1}^m
\bigl(c_j^{\mathsf T}y_j+d_j\alpha_j\bigr).
\]
Agreement of the worth formulas on overlaps ensures that this equality remains valid when an atom belongs to several pieces.
Together, the two directions prove both equivalence of feasibility and equality of attainable welfare values.
4. Attainment and the zero query. Summing the minimum-size constraints gives
\(\delta\sum_j\alpha_j\le\sum_j\mathbf1^{\mathsf T}y_j=\lVert x\rVert_1\).
Thus
\(0\le\alpha_j\le\lVert x\rVert_1/\delta\).
Also, nonnegativity and \(\sum_jy_j=x\) imply \(0\le y_j\le x\).
The LP feasible set is therefore closed and bounded. If nonempty, it is compact, so its linear objective attains a maximum. Section 3 converts a maximizing solution into an optimal plan. This proves that the maximum in the definition of \(\operatorname{OPT}_w(x)\) is attained whenever a plan exists.
When \(x=0\), these same bounds force every \(\alpha_j\) and \(y_j\) to vanish. The resulting plan is empty and has value zero, as required.
5. Exact computation and output size. Let \(s\) be the total number of inequalities in the descriptions of the pieces. The constructed LP has \(m(\tau+1)\) variables and \(s+O(m\tau+\tau)\) constraints. Its coefficients are copied from the input or are \(0\), \(1\), or their negatives. Repeating the query coordinates across the pieces increases the encoding length by only a polynomial factor. Hence the LP has total binary encoding length polynomial in \(m,\tau,L\).
We use the standard rational linear programming theorem: an explicitly given rational LP can be solved exactly in time polynomial in its binary encoding length, detecting infeasibility and returning a rational optimum when one exists. Polynomial-time LP algorithms and the polynomial encoding bounds for rational vertices are discussed in [Karger’s LP algorithm notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) and [LP structure notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html).
The hypotheses hold here: the LP is explicitly described, all coefficients are rational, and its feasible set is bounded. Lower-dimensional feasible sets are allowed by this theorem.
For completeness, the rational output-size bound follows from the vertex characterization. A nonempty bounded rational polytope has an optimal vertex. With \(N=m(\tau+1)\), that vertex is uniquely determined by \(N\) linearly independent active constraints. Clearing denominators gives an integer system whose entries have polynomial bit length. Cramer’s rule expresses its coordinates as ratios of determinants. For entries bounded in absolute value by \(M\), each such determinant is bounded by \(N!M^N\), whose bit length is polynomial in the LP encoding length.
Take the rational optimal solution returned by an exact polynomial-time algorithm. Section 3 constructs the output atoms using
\(q_j=y_j/\alpha_j\) whenever \(\alpha_j>0\).
Division of polynomial-length rational numbers produces polynomial-length rational numbers. There are at most \(m\) atoms, each with \(\tau\) rational coordinates and one rational weight. Thus both constructing and writing the optimal plan take polynomial time. The optimal value is the rational LP objective value.
6. The cutoff transformation. For the supplied query, first compare \(r\lVert x\rVert_1\) with \(k\) using exact rational arithmetic. At or below the cutoff, solve the LP above and return either infeasibility or its value and reconstructed optimal plan.
For a permitted profile above the cutoff, test the explicitly given piece inequalities and evaluate the affine formula of any containing piece. Agreement on overlaps makes the result well-defined, and these operations also take polynomial time.
The essential structural fact is that an arbitrary plan’s contribution within a piece can be replaced by one weighted average profile: convexity preserves permission, and affinity preserves welfare. The unrestricted nonnegative weights make this replacement admissible.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The reduction preserves feasibility and welfare in both directions, proves attainment, and yields an exact polynomial-time algorithm with a rational optimal plan containing at most \(m\) atoms. No major or minor mathematical issues were found.
USER_TASK: explicitly described rational polyhedral pieces, an affine worth formula on each piece, agreement on overlaps, a strictly positive minimum profile mass, and unrestricted nonnegative real plan weights. It does not introduce an integrality or probability-normalization requirement. Its complexity claim concerns evaluation at a supplied query and construction of that query’s optimal plan.The zero-weight case is handled correctly: \(\alpha_j=0\) forces \(y_j=0\). Thus homogenization introduces no spurious contribution from a piece with zero assigned weight, including an empty piece.
The bound
\[
\delta\lambda(Q_x)\le\lVert x\rVert_1
\]
is correct. It follows by integrating the promised pointwise minimum coalition size and using the plan’s moment constraint. Positivity of \(\delta\) is essential and is explicitly supplied.
Integrating each pointwise linear inequality gives exactly the asserted LP inequalities. This remains valid for signed coefficients because the coordinate functions are bounded and the measure is finite. Additivity over the finite partition gives \(\sum_jy_j=x\).
The welfare identity is also exact: the affine constant contributes \(d_j\lambda(E_j)=d_j\alpha_j\), while the linear part contributes \(c_j^{\mathsf T}y_j\). There is no omitted normalization factor.
The finite sum of weighted Dirac measures is an admissible finite nonnegative Borel measure. Its moment equals \(x\), and its welfare equals the LP objective. Agreement of worth formulas on overlaps justifies evaluating an atom using its assigned piece’s formula. If several constructed profiles coincide, the measure has fewer distinct atoms, so the bound of at most \(m\) atoms remains valid.
Together, these directions establish equality of the attainable welfare sets, not merely an upper bound or an approximation.
For \(x=0\), positivity of \(\delta\) forces all weights and aggregate profiles to vanish; the zero LP solution is feasible and reconstructs the empty plan with value zero. Zero coordinates of a nonzero query also cause no difficulty. Empty pieces and an empty permitted union introduce no false feasible nonzero plan.
The invoked rational LP theorem is stated sufficiently precisely for this application: exact polynomial-time solution of an explicitly encoded rational LP, with infeasibility detection and a rational optimal solution when a finite optimum exists. The constructed LP satisfies its hypotheses, including in lower-dimensional cases. The cited [LP algorithm notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial-time solution, lower-dimensional feasibility, and recovery of exact optimal vertices.
The separate output-size argument is valid. A bounded nonempty rational polytope has an optimal vertex, and its active constraint normals contain a full-rank selection in the ambient variable space; full dimensionality of the polytope is unnecessary. Clearing denominators has polynomial bit cost. Cramer’s rule and the bound \(N!M^N\) establish polynomial coordinate encoding length, consistent with the cited [LP structure notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html).
Reconstruction divides polynomial-length rational coordinates by positive polynomial-length rational weights. This preserves polynomial encoding length, even when a weight is numerically very small. The number of output coordinates is polynomial, and exact objective evaluation is likewise polynomial.
No repair or additional clarification is needed. The established complexity is polynomial time in the binary input model requested by the task; the proof does not claim a strongly polynomial algorithm.
⟨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.