Answer: Polynomial-time solvable, including exact rational witnessing societies and all tied minimizers.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 returns exactly the set POΩ(X).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(X\) of feasible plans with rational cost vectors, resident types \(T\) with positive normalized weight vectors \(w^t\), and a nonempty rational polytope \(\mathcal M\subseteq\Delta(T)\) of admissible population shares, compute the plans \(x\in X\) that minimize \(\sum_{t\in T}\mu_t w^t\cdot x\) for at least one \(\mu\in\mathcal M\), returning a witnessing distribution for each.
Input consists of a nonempty explicitly listed set \(X\subseteq\mathbb Q_{\geq0}^{q}\) of \(m\) plan cost vectors, and a list \(T\) of resident types with weights \(w^t\in\mathbb Q_{>0}^{q}\), normalized by \(\sum_{i=1}^{q}w_i^t=1\).
A nonempty rational polytope \(\mathcal M\subseteq\Delta(T)\) is given by explicit rational linear inequalities; its elements are admissible population shares. Every listed type has positive share in at least one admissible distribution.
A society is represented by its support: the list of types with positive mass, each mass encoded as a binary rational. The support size is not the number of possible types. Here \(\tau=|T|\) is the maximum admissible support size; individual distributions may omit zero-mass types.
For \(\mu\in\mathcal M\), define \(C_\mu(x)=\sum_{t\in T}\mu_t(w^t\cdot x)\). Return every \(x\in X\) that minimizes \(C_\mu\) over \(X\) for at least one admissible \(\mu\), together with a rational witnessing distribution for each; include all tied minimizers.
Is this computation solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), \(q\), the number \(h\) of supplied inequalities, and the total binary input length \(L\).
For an explicit finite set of nonnegative cost vectors and polyhedral uncertainty over normalized positive criterion weights, an exact polynomial-time filtering algorithm computes all possibly optimal vectors (Benabbou and Perny, 2015).
That result does not explicitly formulate population-share uncertainty or require witnessing societies; no separate continuous-side result is established here.
The computation is polynomial-time solvable in the binary input model, including the production of rational witnessing societies and all tied minimizers. It requires one rational linear feasibility problem for each listed plan.
Index the types by \(T=\{1,\ldots,\tau\}\) and the plans by \(X=\{x^1,\ldots,x^m\}\). Write the supplied description as
\[ \mathcal M=\{\mu\in\mathbb R^\tau:A\mu\le b,\ \mu\ge0,\ \mathbf1^\top\mu=1\}, \]
where \(A\mu\le b\) consists of the \(h\) supplied inequalities. Adding the simplex constraints is harmless if they already appear in that description.
Precompute the rational numbers
\[ a_{jt}=w^t\cdot x^j=\sum_{i=1}^{q}w_i^t x_i^j. \]
For each \(j\), consider the following system in the \(\tau\) population-share variables:
\[ \begin{aligned} A\mu&\le b,\\ \mu_t&\ge0 &&(t=1,\ldots,\tau),\\ \sum_{t=1}^{\tau}\mu_t&=1,\\ \sum_{t=1}^{\tau}(a_{jt}-a_{kt})\mu_t&\le0 &&\bigl(k\in\{1,\ldots,m\}\setminus\{j\}\bigr). \end{aligned} \]
Call its feasible set \(P_j\).
Claim. The plan \(x^j\) is possibly optimal if and only if \(P_j\) is nonempty.
Proof. The first three groups of constraints are exactly membership in \(\mathcal M\). For any such \(\mu\),
\[ C_\mu(x^j)-C_\mu(x^k) =\sum_{t=1}^{\tau}\mu_t(a_{jt}-a_{kt}). \]
Consequently, the last group holds exactly when \(C_\mu(x^j)\le C_\mu(x^k)\) for every competing plan. This is precisely the condition that \(x^j\) minimizes \(C_\mu\) over \(X\). Both directions follow. \(\square\)
The algorithm solves these systems exactly. Whenever \(P_j\) is feasible, it returns \(x^j\) together with a rational feasible point \(\mu^j\), encoded as the list
\[ \{(t,\mu_t^j):\mu_t^j>0\}. \]
Omitted types have zero mass. The comparison inequalities are non-strict, so every possibly optimal tied plan passes its own feasibility test.
We use the standard rational linear-programming theorem: an explicitly given rational linear system can be tested for feasibility, and a rational feasible point produced when one exists, in time polynomial in its binary encoding length. This theorem permits equalities and feasible sets of smaller affine dimension; it does not require an interior feasible point. See [Trevisan’s linear-programming notes](https://lucatrevisan.wordpress.com/2011/01/24/cs261-lecture-5-linear-programming/).
Here every \(P_j\) is a rational polytope contained in the simplex. Thus it is bounded and closed. The theorem therefore applies directly, including when a plan is optimal only at a boundary distribution.
For completeness, polynomial-size witnesses also follow from a determinant bound.
Each \(a_{jt}\), and hence each difference \(a_{jt}-a_{kt}\), has numerator and denominator of \(O(L)\) bits. Indeed, for one dot product, take as a common denominator the product of the denominators of its input coordinates. The sum of their bit lengths is at most \(L\). The numerator is a sum of \(q\) integer products, adding only \(O(\log q)\) bits. Subtracting two such rationals preserves the \(O(L)\) bound.
Clear denominators separately in every constraint row. Each resulting integer coefficient, including its right-hand side, then has at most
\[ K=O((\tau+1)L) \]
bits.
If \(P_j\) is nonempty, it has a vertex: successively minimize each coordinate over the compact feasible set and restrict to the minimizing face; after all coordinates have been fixed, the resulting face is a singleton.
At a vertex, the active constraint normals span \(\mathbb R^\tau\). Otherwise, a nonzero direction orthogonal to all active normals would preserve their equalities, and sufficiently small perturbations in both directions would preserve all inactive inequalities, contradicting extremality.
Choose \(\tau\) independent active rows. Their equations form an invertible integer system \(D\mu=e\). Cramer’s rule expresses every coordinate as a ratio of integer determinants. Each determinant has absolute value at most
\[ \tau!\,2^{\tau K}, \]
because its expansion contains \(\tau!\) products, each bounded by \(2^{\tau K}\). Thus a vertex witness has, per coordinate, encoding length
\[ O\!\left(\tau(\tau+1)L+\tau\log(\tau+1)\right). \]
In particular, irrational feasibility cannot create an additional possibly optimal plan lacking a rational witnessing society, and the required output has polynomial length.
Replace the normalization equality by two inequalities. Each feasibility problem has \(\tau\) variables and at most
\[ r=h+(m-1)+\tau+2=h+m+\tau+1 \]
inequalities.
A conservative bound on its dense binary encoding length is
\[ B=O\!\left(r(\tau+1)L\right). \]
Let \(\operatorname{LP}(n,s,B)\) denote the bit running time of an exact rational LP algorithm that decides feasibility and returns a rational feasible point, for a system with \(n\) variables, \(s\) inequalities, and encoding length at most \(B\). The rational LP theorem gives
\[ \operatorname{LP}(n,s,B)=\operatorname{poly}(n,s,B). \]
Precomputing all dot products requires \(O(m\tau q)\) rational arithmetic operations. Constructing all comparison coefficients requires \(O(m^2\tau)\) further operations. Using the \(O(L)\) intermediate bit bounds above, a conservative elementary arithmetic bound is \(O(L^3)\) bit operations per operation.
Including reading the input and writing the LP systems, a valid total bound is
\[ O\!\left( L+m\tau(q+m)L^3+mB \right) + m\,\operatorname{LP}(\tau,r,B), \]
where
\[ r=h+m+\tau+1, \qquad B=O\!\left((h+m+\tau+1)(\tau+1)L\right). \]
This is polynomial in all requested parameters \(m,\tau,q,h,L\), and polynomial in the total input length because the plans, types, and inequalities are explicitly listed.
The algorithm uses \(\tau\) share variables without enumerating supports. Each returned society contains exactly its positive-mass types and therefore has support size at most \(\tau\).
Define the aggregate criterion weight by
\[ \bar w(\mu)=\sum_{t=1}^{\tau}\mu_t w^t. \]
Then
\[ C_\mu(x)=\bar w(\mu)\cdot x, \qquad \sum_{i=1}^{q}\bar w_i(\mu)=1. \]
Furthermore, for every criterion \(i\),
\[ \bar w_i(\mu)\ge\min_{t\in T}w_i^t>0, \]
using finiteness of \(T\), positivity of the listed weights, and the simplex conditions. Hence the image
\[ \Omega=\{\bar w(\mu):\mu\in\mathcal M\} \]
is a rational polytope of normalized positive criterion weights.
This connects the problem to the finite-set filtering framework of [Benabbou and Perny (2015)](https://ojs.aaai.org/index.php/AAAI/article/download/9362/9221). The proof above establishes the population-share and witnessing-society requirements directly: it retains the share variables throughout, so no explicit inequality description of the projected polytope \(\Omega\) is needed.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned problem: it gives a polynomial-time algorithm that returns exactly the possibly optimal plans, includes every tied minimizer, and produces rational witnessing societies in the required support representation. No major or minor mathematical issues were identified.
The description
\[
\mathcal M=\{\mu\in\mathbb R^\tau:A\mu\le b,\ \mu\ge0,\ \mathbf1^\top\mu=1\}
\]
correctly combines the supplied inequalities with the simplex restrictions. Repeating restrictions already supplied does not change the feasible set.
The precomputed coefficient \(a_{jt}=w^t\cdot x^j\) is rational. The displayed identity
\[
C_\mu(x^j)-C_\mu(x^k)
=\sum_{t=1}^{\tau}\mu_t(a_{jt}-a_{kt})
\]
is correct.
Consequently, the comparison constraints in \(P_j\) are equivalent to requiring \(x^j\) to have cost no greater than every other listed plan under the same distribution. The proof establishes both directions:
There is no quantifier mismatch: one distribution must satisfy all comparisons simultaneously.
The non-strict inequalities correctly retain ties. Testing each plan separately therefore returns every plan that belongs to an admissible distribution’s minimizing set.
The prover states the required theorem precisely enough: rational linear feasibility admits polynomial-time decision and production of a rational feasible point, with complexity measured in binary encoding length.
Its hypotheses are satisfied as written. Each system has finitely many explicitly constructed rational constraints. Equalities can be represented by two inequalities, as the output subsequently does. Lower-dimensional feasible sets and boundary-only witnesses are permitted; no strict feasibility assumption is introduced.
The cited [Trevisan notes](https://lucatrevisan.wordpress.com/2011/01/24/cs261-lecture-5-linear-programming/) support polynomial-time rational LP solution, rational output of polynomial encoding length, and conversion of equalities to inequalities. The proof uses the stated LP theorem, rather than relying on a numerical approximation or an interior-point heuristic.
The coefficient-length estimate is valid. For each dot product, the total bit length of the participating input numerators and denominators is bounded by \(L\). A product common denominator and the corresponding numerator sum therefore have \(O(L)\) bits; the additional \(O(\log q)\) contribution is absorbed by \(O(L)\) because the coordinates are explicitly listed. Subtracting two such coefficients retains this bound.
Clearing denominators separately in a row with at most \(\tau+1\) rational entries gives the conservative integer coefficient bound
\[
K=O((\tau+1)L).
\]
The vertex-existence argument is sound. Nonempty \(P_j\) is compact, and each successive coordinate minimization produces a nonempty minimizing face. After all coordinates are fixed, that face is a singleton.
The active-normal argument is also correct, including for lower-dimensional polytopes. Equality constraints are included among the active rows. If their normals together with the active inequality normals failed to span the ambient space, the stated two-sided perturbation would contradict extremality.
Selecting \(\tau\) independent active rows yields an invertible integer system. Cramer’s rule applies, and the determinant estimate
\[
|\det D|\le\tau!\,2^{\tau K}
\]
also applies to the matrices with a column replaced by the right-hand side. The resulting per-coordinate encoding bound
\[
O\!\left(\tau(\tau+1)L+\tau\log(\tau+1)\right)
\]
is valid.
Thus real feasibility cannot introduce a plan without a rational witness. The determinant argument establishes witness-size existence; the LP theorem supplies the algorithmic production guarantee.
The constraint count is correct:
\[
h+(m-1)+\tau+2=h+m+\tau+1.
\]
The dense encoding bound
\[
B=O\!\left((h+m+\tau+1)(\tau+1)L\right)
\]
correctly counts rational entries of \(O(L)\) bits. It concerns the rational LP systems, so it need not use the larger row-cleared integer coefficient bound.
The arithmetic counts are valid upper bounds:
The conservative \(O(L^3)\) bit cost per rational arithmetic operation is sufficient with ordinary exact rational arithmetic and reduction. The displayed total bound correctly accommodates construction and the \(m\) exact LP calls. Witness extraction and writing are covered by the LP production guarantee and polynomial output length.
The use of an unspecified polynomial LP running-time function is acceptable: the task requests polynomial-time classification and parameter-dependent running times, not a particular polynomial exponent or a strongly polynomial algorithm.
Because the plans, types, coordinates, and inequalities are explicitly listed, the resulting bound is polynomial in total input length.
The witness encoding retains precisely the positive coordinates and omits zero coordinates, as required. The algorithm uses \(\tau\) variables without enumerating supports or requiring every witness to have full support.
The formulation covers the relevant edge cases directly:
The aggregate-weight identities and positivity bound are correct. The rational linear image \(\Omega\) is a rational polytope of normalized strictly positive weights. The connection to [Benabbou and Perny’s finite-set filtering framework](https://ojs.aaai.org/index.php/AAAI/article/download/9362/9221) is accurate. Crucially, the algorithm does not require an explicit inequality description of that image.
Repair feedback: None required. The population-share formulation and rational witness requirements are established directly.
⟨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.