Answer: The covering problem admits a fully polynomial approximation scheme for every fixed support size.
Proposition 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any fixed number of criteria n > 1, for any MOMDP ⟨S, A, p, r⟩involving n criteria and a discount factor γ ∈(0, 1), for all ε > 0, there ex- ists an ε-covering of Lorenz-optimal tradeoffs whose size is polynomial in |S|, |γ|, |R|, and 1/ε. More- over, there exists an algorithm to construct an ε- covering of Lorenz-optimal tradeoffs in time polyno- mial in |S|, |γ|, |R|, and 1/ε.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix \(n\ge2\). Given a discounted MOMDP with finite state and action sets, transition probabilities, an initial-state distribution, discount factor \(\gamma\in(0,1)\), and positive bounded per-person rewards \(r_i\) for each type \(i\in T=\{1,\dots,n\}\), form a society with type masses \(\mu_i=1/n\). All members of a type share its reward function, and the system uses one stationary randomized policy \(\pi:S\to\Delta(A)\). Let \(v_i^\pi\) be type \(i\)'s expected discounted reward, and let \(\mathcal L_\pi(q)\) be the population Lorenz curve of these type-level per-person rewards. Compute a finite set \(Y\) of feasible policies such that for every Lorenz-optimal attainable profile \(v^\pi\), some \(\pi'\in Y\) satisfies \((1+\epsilon)\mathcal L_{\pi'}(q)\ge\mathcal L_\pi(q)\) for every \(q\in[0,1]\). At \(q=k/n\), \(\mathcal L_\pi(q)\) is the paper's \(k\)-th cumulative sorted reward divided by \(n\), with linear interpolation between these points.
Fix \(n\ge2\). A society is given by its support: the list of \(\tau=n\) types with positive binary-rational masses \(\mu_i=1/n\); \(\tau\) is the support size, not the number of possible types.
The input is a discounted MOMDP with nonempty finite state and action sets \(S,A\), \(m=|S|\), rational transition probabilities, a rational initial-state distribution, rational discount factor \(\gamma\in(0,1)\), and strictly positive rational rewards \(r_i:S\times A\to\mathbb Q_{>0}\). Let \(L\) be the total binary input length, including rational \(\epsilon>0\).
One stationary randomized policy \(\pi:S\to\Delta(A)\) governs the whole society. Each type receives its per-person expected infinite-horizon discounted reward \(v_i^\pi\), evaluated under the initial-state distribution.
Sort these rewards increasingly as \(v_{(1)}^\pi\le\cdots\le v_{(n)}^\pi\). Define the unnormalized population Lorenz curve by \(\mathcal L_\pi(0)=0\), \(\mathcal L_\pi(k/n)=n^{-1}\sum_{j=1}^k v_{(j)}^\pi\), and linear interpolation.
A profile is Lorenz-optimal if no attainable profile has a curve weakly greater everywhere and strictly greater somewhere. Seek a finite set \(Y\) of feasible policies such that every Lorenz-optimal \(v^\pi\) has some \(\pi'\in Y\) satisfying \((1+\epsilon)\mathcal L_{\pi'}(q)\ge\mathcal L_\pi(q)\) for all \(q\in[0,1]\).
Does this covering problem admit a fully polynomial approximation scheme, with runtime and output size polynomial in \(m,|A|,L,1/\epsilon\) for fixed \(\tau=n\), or can such a scheme be ruled out assuming \(\mathrm P\ne\mathrm{NP}\)?
Known results: fixed-dimensional discounted MOMDPs with stationary randomized policies admit a fully polynomial scheme for multiplicative Lorenz covering. [Primary source](https://auai.org/uai2013/prints/papers/208.pdf).
The equal-mass formulation above is exactly that covering problem: division by \(n\) preserves its inequalities, and interpolation makes the breakpoint and whole-curve conditions equivalent. Consequently, this target is already settled.
The covering problem admits a fully polynomial approximation scheme for every fixed support size \(n\). This is the result stated in Proposition 3 of Perny, Weng, Goldsmith, and Hanna, [*Approximation of Lorenz-Optimal Solutions in Multiobjective Markov Decision Processes*](https://auai.org/uai2013/prints/papers/208.pdf).
Here is a direct proof that also verifies the required dependence on binary input length. Rationals are understood to be encoded in binary.
Write \(\alpha\) for the initial-state distribution and \(p(t\mid s,a)\) for the transition probabilities. For a stationary randomized policy \(\pi\), define its discounted occupancy numbers by
\[ x_{sa}^{\pi} = \mathbb E_{\alpha}^{\pi} \left[\sum_{t=0}^{\infty}\gamma^t \mathbf 1_{\{S_t=s,\ A_t=a\}}\right]. \]
These numbers satisfy
\[ x_{sa}\ge 0,\qquad \sum_{a\in A}x_{sa} -\gamma\sum_{t\in S}\sum_{a\in A}p(s\mid t,a)x_{ta} =\alpha_s \quad(s\in S). \]
Let \(X\) denote the polytope defined by these constraints. Summing the balance equations over states gives
\[ \sum_{s,a}x_{sa}=\frac{1}{1-\gamma}. \]
Thus \(X\) is bounded. It is nonempty because every stationary policy supplies a feasible occupancy vector. Each reward coordinate is linear:
\[ v_i(x)=\sum_{s,a}r_i(s,a)x_{sa}. \]
Conversely, every \(x\in X\) is realizable by a stationary randomized policy. Indeed, put \(d_s=\sum_a x_{sa}\) and define
\[ \pi_x(a\mid s)=\frac{x_{sa}}{d_s} \quad\text{when }d_s>0, \]
choosing any action distribution when \(d_s=0\). Then \(x_{sa}=d_s\pi_x(a\mid s)\), including at states with zero occupancy, and the balance equations become
\[ d=\alpha+\gamma P_{\pi_x}^{\mathsf T}d. \]
This equation has a unique solution: if two solutions differ by \(h\), then
\[ \|h\|_1 =\gamma\|P_{\pi_x}^{\mathsf T}h\|_1 \le\gamma\|h\|_1, \]
which implies \(h=0\), since \(\gamma<1\). The actual discounted state occupancies of \(\pi_x\) satisfy the same equation. Consequently, its state-action occupancies equal \(x\), and its reward profile equals \(v(x)\).
Define
\[ r_{\min}=\min_{i,s,a}r_i(s,a),\qquad r_{\max}=\max_{i,s,a}r_i(s,a),\qquad b=\frac{r_{\min}}{1-\gamma},\qquad u=\frac{r_{\max}}{1-\gamma}. \]
Strict positivity and the occupancy sum imply
\[ 0<b\le v_i(x)\le u \quad\text{for every }x\in X\text{ and every }i. \]
Set \(\delta=\min\{\epsilon,1\}\) and \(\beta=1+\delta\). Let \(J\) be the smallest positive integer satisfying \(b\beta^J>u\), and define the rational grid
\[ G=\{b\beta^j:0\le j<J\}. \]
For each tuple \(g=(g_1,\ldots,g_n)\in G^n\), solve the rational linear feasibility problem
\[ x\in X,\qquad v_i(x)\ge g_i \quad(i=1,\ldots,n). \]
Whenever it is feasible, obtain a rational feasible point \(x^g\), recover \(\pi_{x^g}\) as above, and include that policy in \(Y\).
To verify complexity, observe that
\[ \frac{u}{b}=\frac{r_{\max}}{r_{\min}}. \]
Because all rewards have binary encoding length at most \(L\), we have \(r_{\min}\ge 2^{-L}\) and \(r_{\max}\le 2^L\). Hence \(\log(u/b)=O(L)\). Also, for \(0<\delta\le1\),
\[ \log(1+\delta)\ge\frac{\delta}{2}. \]
The minimality of \(J\) therefore gives
\[ J\le 1+\frac{\log(u/b)}{\log\beta} =O\!\left(1+L\left(1+\frac1\epsilon\right)\right). \]
There are \(J^n\) linear programs, a polynomial number for fixed \(n\). Each has \(m|A|\) variables and \(m+n\) equality or inequality constraints, apart from nonnegativity. Each grid number has encoding length \(O(L+JL)\), because it is a product of rational numbers with polynomially bounded exponents.
The standard polynomial-time theorem for rational linear programming supplies feasibility decisions and, for feasible instances, rational witnesses of polynomial encoding length. Its hypotheses hold here: all coefficients are rational and the explicitly represented programs have polynomial size. Recovering policies requires only rational sums and divisions. Thus both runtime and total output length are polynomial in \(m,|A|,L,1/\epsilon\), for fixed \(n\).
Fix any attainable profile \(v\). For each coordinate \(i\), choose the largest grid number \(g_i\le v_i\). Such a number exists because \(v_i\ge b\). Since the next grid level is larger than \(v_i\), including when that level is \(b\beta^J>u\), we have
\[ g_i\le v_i<\beta g_i. \]
The linear program indexed by \(g\) is feasible, witnessed by an occupancy vector attaining \(v\). Its returned policy has a profile \(v'\) satisfying \(v_i'\ge g_i\). Therefore,
\[ (1+\epsilon)v_i' \ge\beta v_i' \ge\beta g_i >v_i \quad(i=1,\ldots,n). \]
This establishes componentwise multiplicative covering of all attainable profiles.
For a vector \(z\in\mathbb R^n\), define its \(k\)-th cumulative sorted reward by
\[ C_k(z)=\sum_{j=1}^k z_{(j)} =\min_{\substack{I\subseteq\{1,\ldots,n\}\\|I|=k}} \sum_{i\in I}z_i. \]
The equality holds because a minimum-sum subset consists of the \(k\) smallest coordinates. For every subset \(I\) of size \(k\), componentwise covering gives
\[ (1+\epsilon)\sum_{i\in I}v_i' \ge\sum_{i\in I}v_i \ge C_k(v). \]
Taking the minimum over \(I\) yields
\[ (1+\epsilon)C_k(v')\ge C_k(v) \quad(k=1,\ldots,n). \]
By the problem’s equal-mass definition,
\[ \mathcal L_\pi(k/n)=\frac{C_k(v^\pi)}{n}. \]
Division by the positive constant \(n\) preserves the preceding inequalities. Hence the returned policy satisfies the required covering inequality at every breakpoint.
On each interval between successive breakpoints, the function
\[ q\longmapsto (1+\epsilon)\mathcal L_{\pi'}(q)-\mathcal L_\pi(q) \]
is affine. Its endpoint values are nonnegative, so every value on that interval is nonnegative. This proves covering on the whole interval \(q\in[0,1]\).
The same interpolation argument shows that breakpoint dominance and whole-curve dominance agree, including strict improvement somewhere. Thus the formulation uses exactly the cumulative-reward Lorenz order. The constructed set covers every feasible profile, and therefore every Lorenz-optimal profile, with the requested polynomial bounds.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned covering problem correctly. The direct argument establishes polynomial runtime and polynomial output size for fixed support size \(n\), and covers every attainable profile. No major or minor mathematical issues were found.
The reference is accurate: Proposition 3 states the existence of a fully polynomial approximation scheme for Lorenz covering in discounted MOMDPs with a fixed number of criteria. The direct proof additionally checks the binary input length dependence required here. [Primary source, Proposition 3](https://auai.org/uai2013/prints/papers/208.pdf).
The discounted occupancy definition is well-defined because \(0<\gamma<1\). Its balance equations correctly account for the initial distribution and discounted incoming transitions.
Summing those equations uses the normalization of each transition distribution and of the initial distribution. It correctly gives
\[
\sum_{s,a}x_{sa}=\frac{1}{1-\gamma}.
\]
Together with nonnegativity, this establishes boundedness. Nonemptiness follows from the existence of a stationary policy, since the action set is nonempty.
The reward formula \(v_i(x)=\sum_{s,a}r_i(s,a)x_{sa}\) correctly expresses each type’s per-person discounted reward under the common policy.
The converse construction handles zero-occupancy states explicitly. When \(d_s=0\), nonnegativity implies \(x_{sa}=0\) for every action, so the identity \(x_{sa}=d_s\pi_x(a\mid s)\) remains valid regardless of the distribution chosen there.
The uniqueness argument is correct: the transpose of a row-stochastic transition matrix is nonexpansive in the stated norm. Since \(\gamma<1\), two solutions of the discounted balance equation must coincide. Thus the recovered stationary randomized policy realizes the entire occupancy vector and all reward coordinates simultaneously.
Finding: The linear representation is exact, including unreachable states and arbitrary rational initial distributions.
Strict positivity gives \(r_{\min}>0\). Combining the reward extrema with the occupancy sum correctly yields \(0<b\le v_i(x)\le u\).
The choice \(\delta=\min\{\epsilon,1\}\) ensures both \(\beta>1\) and \(\beta\le1+\epsilon\). Therefore the grid is finite and its approximation factor is sufficient.
The bound on \(J\) is correct. In particular, the strict stopping condition is handled correctly when \(u/b\) is an exact power of \(\beta\). When \(u=b\), the smallest positive stopping index is \(J=1\), so the grid remains nonempty.
The binary encoding bounds \(r_{\min}\ge2^{-L}\) and \(r_{\max}\le2^L\) are valid conservative bounds for positive binary-encoded rationals. Hence \(\log(u/b)=O(L)\). The inequality \(\log(1+\delta)\ge\delta/2\) applies throughout the stated range and gives the claimed polynomial grid size.
Finding: The grid bounds are valid for all permitted rewards and every rational \(\epsilon>0\).
There are \(J^n\) feasibility problems, which is polynomial for fixed \(n\). Each has the stated number of variables and constraints, apart from nonnegativity constraints.
The grid entries are rational. The encoding-length estimate accounts for the bit lengths of \(b\) and \(\beta\), as well as the exponent \(j<J\). A discount factor arbitrarily close to one does not invalidate this estimate: its encoding is included in \(L\).
The invoked rational linear programming theorem is stated with the necessary conclusions: polynomial-time feasibility decisions and polynomial-length rational feasible witnesses. Its hypotheses are satisfied by the explicitly represented rational programs.
Policy recovery uses rational arithmetic on polynomial-length witnesses. At zero-occupancy states, the permitted choice of any distribution allows a rational deterministic distribution, so these states cause no output-encoding difficulty.
Finding: Both runtime and total policy output length have the required polynomial bounds.
For every attainable profile, each coordinate has a largest grid entry below it because the coordinate is at least \(b\).
The next-level argument correctly includes the last grid entry: the omitted next level exceeds \(u\), hence exceeds every feasible coordinate. Consequently, \(g_i\le v_i<\beta g_i\) holds in every case.
The indexed feasibility problem has a witness attaining the original profile. Its returned profile satisfies \(v_i'\ge g_i\). Since \(\beta\le1+\epsilon\) and \(v_i'>0\), the displayed componentwise covering inequality follows.
Finding: The same returned policy covers all coordinates of the selected profile simultaneously.
The identity expressing \(C_k(z)\) as the minimum sum over subsets of size \(k\) is correct, including tied coordinates.
For every such subset, the prover obtains a lower bound by \(C_k(v)\). Taking the minimum on the left therefore correctly gives
\[
(1+\epsilon)C_k(v')\ge C_k(v).
\]
There is no unjustified interchange of sorting or minimization.
Division by the positive constant \(n\) gives the required breakpoint inequalities. Both curves vanish at zero. Between consecutive breakpoints, their scaled difference is affine, so nonnegative endpoint values imply nonnegativity throughout.
The assertion concerning strict dominance is also correct: an affine difference that is positive somewhere on an interval must be positive at at least one endpoint.
Finding: The constructed set satisfies the whole-curve covering requirement. Covering all feasible profiles is stronger than the requested covering of Lorenz-optimal profiles.
None. The proof settles the intended fixed-support, stationary randomized-policy problem without relying on a degenerate interpretation or an unstated restriction.
⟨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.