Answer: The decision problem belongs to \(\mathrm{P}\), with running time polynomial in \(m,\tau,\beta,L\).
Theorem 4.7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLPareto-Egal-Determine and LPareto-Balc-Determine are co-NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite applicant and position type sets \(A\) and \(B\), rational masses \(\mu\) and \(\nu\), finitely many layers with type-level positional scores \(p^\ell_{ab}\) and \(q^\ell_{ba}\), and a rational feasible transport plan \(\pi^0\), decide whether there exists another feasible plan \(\pi'\) with the same marginals such that \(E_\ell(\pi') \le E_\ell(\pi^0)\) for every layer and \(E_{\ell^\star}(\pi') < E_{\ell^\star}(\pi^0)\) for some layer, where \(E_\ell(\pi)=\sum_{a,b}\pi_{ab}(p^\ell_{ab}+q^\ell_{ba})\).
Let \(A\) and \(B\) be nonempty finite sets of applicant and position types, with strictly positive binary rational masses satisfying \(\sum_{a\in A}\mu_a=\sum_{b\in B}\nu_b=1\). A society is given by its support: the list of types with positive mass and their masses. Write \(\tau=|A|+|B|\) for the total support size, not the number of possible types, and \(m=|B|\).
There are \(\beta\geq1\) layers. In each layer, every type strictly ranks all opposite-side types; \(p^\ell_{ab}\) and \(q^\ell_{ba}\) are their one-based positions in these rankings. Layers have unit weight.
A feasible plan is any real matrix \(\pi\geq0\) satisfying \(\sum_b\pi_{ab}=\mu_a\) and \(\sum_a\pi_{ab}=\nu_b\); masses may split among partners. Define \(E_\ell(\pi)=\sum_{a\in A,b\in B}\pi_{ab}(p^\ell_{ab}+q^\ell_{ba})\). The input includes a feasible binary rational plan \(\pi^0\). Let \(L\) be the total binary input length.
Is deciding whether there exists a feasible plan \(\pi'\) with \(E_\ell(\pi')\leq E_\ell(\pi^0)\) for every layer and \(E_{\ell^\star}(\pi')<E_{\ell^\star}(\pi^0)\) for some layer in P, with running time polynomial in \(m,\tau,\beta,L\), or is it NP-hard?
For discrete perfect matchings with strict complete preferences, deciding whether a given matching is layer Pareto-optimal under egalitarian dissatisfaction is co-NP-hard; deciding whether a dominating matching exists is NP-hard ([source](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p1373.pdf)). No result settling this exact continuous decision problem was located.
The decision problem is in \(\mathrm{P}\). A single rational linear program decides it in time polynomial in \(m,\tau,\beta,L\), including an exact test for strict improvement.
Write \(n=|A|=\tau-m\), and define the integer coefficients and rational thresholds
\(c^\ell_{ab}=p^\ell_{ab}+q^\ell_{ba}\), and \(r_\ell=E_\ell(\pi^0)\).
Because the rankings are strict and complete, \(1\le p^\ell_{ab}\le m\) and \(1\le q^\ell_{ba}\le n\). Consequently, \(2\le c^\ell_{ab}\le\tau\).
Let \(K\) consist of all matrices \(x\) satisfying:
Thus \(K\) is precisely the set of feasible plans that weakly improve upon \(\pi^0\) in every layer.
Consider the linear program
\(\displaystyle \max_{x\in K}G(x),\qquad G(x)=\sum_{\ell=1}^{\beta}\left(r_\ell-\sum_{a\in A,b\in B}c^\ell_{ab}x_{ab}\right).\)
Equivalently, its objective is a constant minus a linear function with coefficients \(C_{ab}=\sum_{\ell=1}^{\beta}c^\ell_{ab}\).
The set \(K\) is nonempty because \(\pi^0\in K\). It is closed because its defining constraints are finitely many linear equalities and weak inequalities. Moreover, nonnegativity and the marginal constraints imply \(\sum_{a,b}x_{ab}=1\), so every coordinate lies in \([0,1]\). Therefore \(K\) is compact, and the continuous function \(G\) attains its maximum. Denote this maximum by \(v\).
For every \(x\in K\), each summand \(r_\ell-E_\ell(x)\) is nonnegative.
Suppose a dominating plan \(\pi'\) exists. Then \(\pi'\in K\), and at least one of these summands is strictly positive. Hence \(G(\pi')>0\), which implies \(v>0\).
Conversely, suppose \(v>0\), and let \(x^\star\in K\) attain the maximum. Its layer improvements are all nonnegative and have strictly positive sum. At least one is therefore strictly positive. Thus \(x^\star\) is feasible, satisfies \(E_\ell(x^\star)\le E_\ell(\pi^0)\) in every layer, and satisfies a strict inequality in some layer.
We have proved the exact equivalence:
\(\displaystyle \text{A dominating feasible plan exists}\quad\Longleftrightarrow\quad v>0.\)
The algorithm consequently returns “yes” exactly when the optimal value is positive.
We use the standard rational linear-programming theorem: a linear program with binary-encoded rational data can be solved in time polynomial in its encoding length; when its feasible set is nonempty and its optimum is finite, an exact rational optimal solution and value can be obtained. Polynomial-time solvability of rational linear programming originates with [Khachiyan’s theorem](https://www.mathnet.ru/eng/dan42319).
Here all the hypotheses hold: the coefficients are rational, \(K\) is nonempty, and compactness ensures a finite attained optimum. It remains to verify that constructing the program does not cause excessive encoding growth.
There are \(nm=m(\tau-m)\) variables, \(\tau\) marginal equalities, and \(\beta\) layer inequalities, together with nonnegativity constraints. All these counts are polynomial in the requested parameters.
To bound the thresholds’ encoding lengths, let \(D\) be the product of the denominators of the entries of \(\pi^0\), using denominator \(1\) for zero entries. Their total binary length is at most \(L\), so \(\log_2D=O(L)\). Every \(D\pi^0_{ab}\) is a nonnegative integer, and
\(\displaystyle Dr_\ell=\sum_{a,b}c^\ell_{ab}(D\pi^0_{ab})\)
is an integer. Since \(\sum_{a,b}\pi^0_{ab}=1\) and \(c^\ell_{ab}\le\tau\), it satisfies \(0\le Dr_\ell\le\tau D\). Hence each \(r_\ell\) has binary encoding length \(O(L+\log\tau)\), even before reducing the fraction.
The objective coefficients satisfy \(C_{ab}\le\beta\tau\), so their binary lengths are \(O(\log(\beta\tau))\). The objective constant \(\sum_\ell r_\ell\) has denominator dividing \(D\) and numerator at most \(\beta\tau D\). The marginal masses already occur in the input.
Thus the complete linear program has encoding length polynomial in \(m,\tau,\beta,L\), and its coefficients can be constructed using polynomial-time integer arithmetic. Applying rational linear programming and comparing the exact rational optimum with zero gives the required polynomial-time algorithm. No numerical tolerance or assumed minimum improvement is needed.
The cited paper’s Theorem 4.7 concerns domination by discrete perfect matchings. [Wen, Zhou, and Guo](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p1373.pdf) prove the corresponding hardness result.
Here plans may split masses, so the feasible set under the layer bounds is a rational polytope, and the decision reduces exactly to linear optimization over it. The discrete hardness result therefore does not settle this continuous problem.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The prover resolves the continuous decision problem correctly. The LP formulation, strict-improvement criterion, and binary encoding bounds are valid. No major or minor mathematical issues were found.
The proof uses precisely the task’s feasible real matrices, allowing masses to split. It imposes no integrality or additional matching restriction.
Since both supports are nonempty, \(n=\tau-m\geq1\) and \(m\geq1\). Strict complete rankings give \(1\leq p^\ell_{ab}\leq m\) and \(1\leq q^\ell_{ba}\leq n\), hence \(2\leq c^\ell_{ab}\leq\tau\). The coefficient bounds are correct and depend on support size.
The nonnegativity and marginal constraints are exactly the feasibility requirements. Substituting \(r_\ell=E_\ell(\pi^0)\), the layer inequalities are exactly the required weak improvements.
Therefore, \(K\) contains all and only the feasible plans weakly improving every layer. The supplied feasibility of \(\pi^0\) establishes \(\pi^0\in K\).
Summing the row constraints gives \(\sum_{a,b}x_{ab}=1\). Together with nonnegativity, this bounds every coordinate between zero and one.
The finitely many linear equalities and weak inequalities define a closed set. Thus \(K\) is nonempty, closed, and bounded in a finite-dimensional real space, so it is compact. The linear objective is continuous and attains a finite maximum. All hypotheses of the compactness and extreme-value results are satisfied.
For every \(x\in K\), all quantities \(r_\ell-E_\ell(x)\) are nonnegative.
If a dominating plan exists, at least one of these finitely many quantities is positive, so their sum is positive and \(v>0\).
Conversely, if \(v>0\), an attaining optimizer has nonnegative layer improvements with positive sum. At least one layer improvement must therefore be positive. This establishes exactly the requested existential strict inequality.
There is no cancellation issue because the layer constraints enforce nonnegativity of every summand.
The prover explicitly states the standard theorem needed: binary-encoded rational LPs admit polynomial-time solution, with an exact rational optimum and optimizer when feasible with finite optimum.
The constructed program has rational constraint and objective data; feasibility and finiteness were established above. The theorem therefore applies as written. Exact comparison of the returned rational optimum with zero decides strict improvement without a numerical tolerance. The historical attribution to Khachiyan is accurate. [Khachiyan’s publication](https://www.mathnet.ru/eng/dan42319).
The product \(D\) of the input plan denominators has logarithm bounded by their total encoding length, hence \(\log_2D=O(L)\). Each \(D\pi^0_{ab}\) is an integer.
Consequently, \(Dr_\ell\) is an integer. Nonnegativity, total mass one, and \(c^\ell_{ab}\leq\tau\) imply \(0\leq Dr_\ell\leq\tau D\). Both numerator and denominator therefore have \(O(L+\log\tau)\) bits. Reduction of the fraction is unnecessary for this bound.
The objective constant’s denominator divides \(D\), and its numerator is bounded by \(\beta\tau D\), as claimed.
There are \(nm=m(\tau-m)\) variables, \(\tau\) marginal equalities, \(\beta\) layer inequalities, and \(nm\) nonnegativity constraints. Even a dense representation has polynomial size in the requested parameters.
The bound \(C_{ab}\leq\beta\tau\) gives the claimed coefficient encoding length. Constructing these quantities uses polynomially many arithmetic operations on integers of polynomial bit length.
Redundant marginal equalities cause no difficulty. The argument also covers \(\beta=1\), singleton supports, zero entries of \(\pi^0\), and \(v=0\). No positivity gap or nondegeneracy assumption is required.
The cited Theorem 4.7 concerns discrete matchings and establishes co-NP-hardness of the Pareto-optimality test; its proof explicitly establishes NP-hardness of the complementary domination problem. [Wen, Zhou, and Guo, Theorem 4.7](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p1373.pdf).
The prover correctly distinguishes that domain from the continuous feasible plans audited here.
Actionable feedback: No repair or additional clarification 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.