Answer: \(\mathrm{NP}\text{-hard}\)
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet V ∗ memu be the value of the optimal MEMU fairness policy, V ub be the value of the optimal MMEU policy π∗ mmeu evaluated with its own objective func- tion defined by (2), and V lb be the value of the optimal MMEU policy π∗ mmeu evaluated with the MEMU value func- tion defined by (5).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-horizon aggregate resource MDP with an explicitly listed state and transition model, τ customer types of positive rational masses μ_t summing to 1, and per-capita allocations subject to mass-scaled resource constraints, compute an MMEU-optimal policy and a valid lower and upper certificate for the MEMU optimum. Each member of type t receives the same trajectory-dependent per-capita cumulative reward G_t^π, so the objectives are max_π min_t E[G_t^π] and max_π E[min_t G_t^π]. For a requested tolerance ε, certify the MMEU policy as ε-optimal whenever the certificate gap is at most ε; otherwise report that the certificate is inconclusive.
A society is given by its support: a list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The input is a finite-horizon MDP with \(n\geq1\) explicitly listed states, an initial state, unary horizon \(H\geq1\), and an explicitly listed menu of \(K\geq1\) allocation actions. For \(m\geq1\) resources, action \(a\) specifies nonnegative rational per-capita allocations \(q_{tj}(a)\); it is feasible in state \(s\) exactly when \(\sum_{t=1}^{\tau}\mu_tq_{tj}(a)\leq b_j(s)\) for every resource \(j\), where budgets are nonnegative rationals. Every state has a feasible action.
Transition probabilities \(P(s'\mid s,a)\) and per-capita rewards \(r_t(s,a,s')\in\mathbb Q\) are explicitly tabulated. Policies are centralized randomized nonstationary Markov policies choosing feasible actions. All members of a type share the same realized reward trajectory; expectations include policy and transition randomness.
Define \(G_t^\pi=\sum_{h=1}^{H}r_t(s_h,a_h,s_{h+1})\), \(F(\pi)=\min_t\mathbb E[G_t^\pi]\), and \(J(\pi)=\mathbb E[\min_tG_t^\pi]\). Both maxima below range over the specified policy class.
Given a positive binary-rational tolerance \(\varepsilon\), compute an MMEU-optimal policy \(\pi_F\in\arg\max_\pi F(\pi)\) and its certificate endpoints \(\ell=J(\pi_F)\), \(u=F(\pi_F)\), satisfying \(\ell\leq\max_\pi J(\pi)\leq u\). Endpoints are exact rational values. Certify \(\pi_F\) as additively \(\varepsilon\)-optimal for MEMU when \(u-\ell\leq\varepsilon\); otherwise report that the certificate is inconclusive. Any MMEU optimizer may be returned.
Is this MMEU-based MEMU certification problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,n,K,H,L\), where \(L\) is the total binary input length, including \(\varepsilon\).
For finite explicitly represented discrete-agent MDPs, MMEU optimization has a polynomial-time algorithm, and evaluating an MMEU optimizer under the two objectives gives the stated MEMU bounds; the lower endpoint is proposed to be estimated by Monte Carlo, without an exact polynomial-time evaluation guarantee. [Zhang and Shah (2015)](https://doi.org/10.1609/aaai.v29i1.9699)
No result settling this precise mass-based certification problem was identified in the search.
The specified problem is \(\mathrm{NP}\)-hard, even with one resource, one action, and rewards in \(\{0,1\}\). Computing an MMEU optimizer and its upper endpoint is polynomial-time solvable. The difficulty lies in the exact lower endpoint; even deciding whether the prescribed certificate is conclusive is \(\mathrm{NP}\)-hard.
Let \(S\) be the state set, and let \(A_s\) denote the feasible actions in state \(s\). These sets can be computed exactly: first calculate each action’s resource loads
\(\displaystyle w_j(a)=\sum_{t=1}^{\tau}\mu_tq_{tj}(a),\)
then compare them with every state’s budgets. This takes \(O(mK(\tau+n))\) rational arithmetic operations. Every \(A_s\) is nonempty by hypothesis.
Define the expected one-step reward
\(\displaystyle \bar r_t(s,a)=\sum_{s'\in S}P(s'\mid s,a)r_t(s,a,s').\)
Computing all these coefficients takes \(O(\tau n^2K)\) rational arithmetic operations.
Introduce occupancy variables \(x_h(s,a)\), for \(a\in A_s\), and a scalar \(z\). Solve the rational linear program maximizing \(z\), subject to
\(\displaystyle x_h(s,a)\geq0,\)
\(\displaystyle \sum_{a\in A_s}x_1(s,a)=\mathbf 1_{\{s=s_{\mathrm{init}}\}},\)
\(\displaystyle \sum_{a\in A_s}x_h(s,a)=\sum_{v\in S}\sum_{a\in A_v}P(s\mid v,a)x_{h-1}(v,a)\quad(2\leq h\leq H),\)
and
\(\displaystyle z\leq\sum_{h=1}^{H}\sum_{s\in S}\sum_{a\in A_s}x_h(s,a)\bar r_t(s,a)\quad(1\leq t\leq\tau).\)
Every admissible policy induces a feasible occupancy vector through
\(\displaystyle x_h(s,a)=\Pr(s_h=s,a_h=a).\)
Conversely, given feasible occupancies, set \(d_h(s)=\sum_{a\in A_s}x_h(s,a)\), and, whenever \(d_h(s)>0\), define
\(\displaystyle \pi_h(a\mid s)=\frac{x_h(s,a)}{d_h(s)}.\)
At states with \(d_h(s)=0\), choose any feasible action. Induction on \(h\), using the initial and flow constraints, shows that this policy has precisely the prescribed occupancies. In particular,
\(\displaystyle \mathbb E[G_t^\pi]=\sum_{h,s,a}x_h(s,a)\bar r_t(s,a).\)
Thus the LP optimum equals \(\max_\pi F(\pi)\), and normalization of an optimal occupancy vector produces an MMEU optimizer.
For completeness, let \(R=\max_{t,s,a,s'}|r_t(s,a,s')|\). Flow conservation implies that occupancies at each stage sum to \(1\), so every type’s expected total reward lies in \([-HR,HR]\). Adding \(-HR\leq z\leq HR\) therefore preserves the optimum and makes the feasible region bounded. It is nonempty because feasible actions exist in every state.
The standard rational linear-programming theorem gives an exact rational optimum and optimizer in polynomial bit time. Its hypotheses hold here: the LP is explicitly represented, rational, feasible, and bounded. It has at most \(HnK+1\) variables and \(O(HnK+Hn+\tau)\) constraints, with total encoding length polynomial in the input parameters. Consequently, computing \(\pi_F\) and \(u=F(\pi_F)\) takes
\(\displaystyle \operatorname{poly}(m,\tau,n,K,H,L)\)
bit operations, and the returned policy has polynomial encoding length.
The support masses enter this construction through feasibility; no expansion into discrete individuals is necessary.
For every policy \(\pi\) and every type \(t\), the pointwise inequality \(\min_vG_v^\pi\leq G_t^\pi\) gives
\(\displaystyle J(\pi)\leq\mathbb E[G_t^\pi].\)
Taking the minimum over \(t\) yields \(J(\pi)\leq F(\pi)\). Since \(\pi_F\) maximizes \(F\),
\(\displaystyle J(\pi)\leq F(\pi)\leq F(\pi_F)=u.\)
The policy space is a nonempty finite product of simplices. Both objectives are continuous, because trajectory expectations are finite sums of products of policy probabilities. Hence their maxima exist, and
\(\displaystyle \ell=J(\pi_F)\leq\max_\pi J(\pi)\leq u.\)
It follows that
\(\displaystyle \max_\pi J(\pi)-J(\pi_F)\leq u-\ell.\)
Therefore \(u-\ell\leq\varepsilon\) is a valid certificate of additive \(\varepsilon\)-optimality.
We reduce from \(\mathrm{3SAT}\) with exactly three distinct variables per clause, an NP-complete restriction. [Tovey (1984)](https://doi.org/10.1016/0166-218X(84)90081-7)
Let the formula be
\(\displaystyle \varphi=\bigwedge_{t=1}^{c}C_t,\)
with variables \(x_1,\ldots,x_d\), where \(c\geq1\). Each clause contains three literals on distinct variables.
Create one type for each clause and one additional type, called the anchor. Thus \(\tau=c+1\).
Choose the positive dyadic masses
\(\displaystyle \mu_t=2^{-t}\quad(1\leq t<\tau),\qquad \mu_\tau=2^{-(\tau-1)}.\)
Their sum is \(1\), since
\(\displaystyle \sum_{t=1}^{\tau-1}2^{-t}+2^{-(\tau-1)}=1.\)
Their total binary encoding length is \(O(\tau^2)\).
Set \(m=K=1\), give the sole action allocation \(0\) to every type, and give every state budget \(0\). The sole action is feasible everywhere. Consequently, there is exactly one policy in the specified class, denoted \(\pi^\circ\); it is necessarily MMEU-optimal.
Use the states
\(\displaystyle S=\{s_0\}\cup\{s_{i,b}:1\leq i\leq d,\ b\in\{0,1\}\},\)
with initial state \(s_0\) and horizon \(H=d\). Thus \(n=2d+1\).
From \(s_0\), transition to each of \(s_{1,0},s_{1,1}\) with probability \(1/2\). From every \(s_{i,b}\) with \(i<d\), transition to each of \(s_{i+1,0},s_{i+1,1}\) with probability \(1/2\). The final-layer states are absorbing.
A horizon-length trajectory therefore determines an assignment \(\alpha\in\{0,1\}^d\), where entering \(s_{i,b}\) sets \(\alpha_i=b\). Every assignment has probability \(2^{-d}\).
For clause type \(t\), the reward on a transition entering layer \(i\) is \(1\) exactly when the assignment to \(x_i\) satisfies a literal of \(C_t\); otherwise it is \(0\).
Because each clause uses distinct variables,
\(\displaystyle G_t^{\pi^\circ}(\alpha)=\#\{\text{true literals of }C_t\text{ under }\alpha\}.\)
The anchor receives reward \(1\) on the first transition and \(0\) thereafter. Its total reward is always \(1\). Set all other tabulated rewards to \(0\), including rewards on absorbing transitions.
Each clause literal is true with probability \(1/2\). By linearity of expectation,
\(\displaystyle \mathbb E[G_t^{\pi^\circ}]=\frac32\quad(1\leq t\leq c),\qquad \mathbb E[G_\tau^{\pi^\circ}]=1.\)
Hence the required upper endpoint is
\(\displaystyle u=F(\pi^\circ)=1.\)
If \(\alpha\) fails to satisfy \(\varphi\), some clause type has total reward \(0\); all rewards are nonnegative, so the realized minimum is \(0\). If \(\alpha\) satisfies \(\varphi\), every clause type has integer total reward at least \(1\), and the anchor has total reward exactly \(1\). Therefore
\(\displaystyle \min_tG_t^{\pi^\circ}(\alpha)=\mathbf 1_{\{\alpha\models\varphi\}}.\)
Writing \(N(\varphi)\) for the number of satisfying assignments, the exact lower endpoint is consequently
\(\displaystyle \ell=J(\pi^\circ)=\frac{N(\varphi)}{2^d}.\)
In particular, exact endpoint computation determines satisfiability by testing whether \(\ell>0\).
Choose the positive dyadic tolerance
\(\displaystyle \varepsilon=1-2^{-(d+1)}.\)
Its binary encoding length is \(O(d)\). The certificate is conclusive precisely when
\(\displaystyle u-\ell\leq\varepsilon \quad\Longleftrightarrow\quad \ell\geq2^{-(d+1)}.\)
If \(\varphi\) is unsatisfiable, then \(\ell=0\), so the certificate is inconclusive. If it is satisfiable, then \(N(\varphi)\geq1\), giving
\(\displaystyle \ell\geq2^{-d}>2^{-(d+1)},\)
so the certificate is conclusive.
Thus the required certificate status equals the satisfiability answer. This is a polynomial-time many-one reduction to the certificate decision on instances with a unique policy.
All tables are explicitly constructible in polynomial time: their sizes are \(O(d^2)\) for transitions and \(O(cd^2)\) for rewards, alongside the polynomial mass encoding and unary horizon. The reduction satisfies every promised input condition. Therefore the full certification problem is \(\mathrm{NP}\)-hard, independently of the freedom to return any MMEU optimizer.
After computing a rational MMEU optimizer by the LP, enumerate all trajectories. There are at most \((nK)^H\). For a trajectory \(\omega=(s_1,a_1,\ldots,a_H,s_{H+1})\), compute
\(\displaystyle p_\omega=\prod_{h=1}^{H}\pi_{F,h}(a_h\mid s_h)P(s_{h+1}\mid s_h,a_h)\)
and
\(\displaystyle v_\omega=\min_t\sum_{h=1}^{H}r_t(s_h,a_h,s_{h+1}).\)
Then \(\ell=\sum_\omega p_\omega v_\omega\), exactly.
The arithmetic has polynomial bit cost per trajectory. To see this, let \(D_P,D_r,D_\pi\) be the products of all denominators in the transition, reward, and returned-policy tables. Every summand’s denominator divides
\(\displaystyle D_r(D_PD_\pi)^H.\)
This common denominator has polynomial bit length because the policy encoding is polynomial and \(H\) is unary. Moreover, every partial sum has absolute value at most \(HR\): its terms satisfy \(|p_\omega v_\omega|\leq p_\omega HR\), and trajectory probabilities sum to \(1\). Hence numerator lengths also remain polynomial.
Computing each trajectory’s rewards and minimum takes \(O(\tau H)\) rational operations. A complete exact algorithm therefore has bit running time bounded by
\(\displaystyle \operatorname{poly}(m,\tau,n,K,H,L) +(nK)^H\,\tau H\,\operatorname{poly}(L,HnK,\tau).\)
Once the endpoints are computed, comparison with \(\varepsilon\) takes polynomial bit time.
There are useful tractable boundaries:
For variable unary \(H\) and variable support size, the hardness reduction applies. Thus polynomial-time MMEU optimization does not imply polynomial-time exact certification unless \(\mathrm P=\mathrm{NP}\). This is consistent with Zhang and Shah’s proposal to estimate the lower endpoint by Monte Carlo; that proposal does not supply the exact rational endpoint required here. [Zhang and Shah (2015), Proposition 1 and subsequent discussion](https://ojs.aaai.org/index.php/AAAI/article/view/9699/9558)
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: exact MMEU-based MEMU certification is \(\mathrm{NP}\)-hard, while computing an MMEU optimizer and its upper endpoint is polynomial-time solvable. The reduction also establishes hardness of deciding whether the prescribed certificate is conclusive. I found no major or minor issues requiring repair.
The resource load \(w_j(a)\) depends only on the action, so computing these loads and comparing them with all state budgets takes the stated \(O(mK(\tau+n))\) rational operations. Positive masses need no expansion into individual agents.
The coefficients \(\bar r_t(s,a)\) correctly average transition-dependent rewards. Their stated computation cost, \(O(\tau n^2K)\) rational operations, accounts for all explicitly tabulated entries. Rational additions and multiplications here produce coefficients of polynomial bit length.
The initial and flow constraints correctly describe state-action occupancies for stages \(1,\ldots,H\). The reward expression includes precisely the \(H\) transitions defining \(G_t^\pi\), including the final transition into \(s_{H+1}\).
Normalizing occupancies at states with positive visitation probability produces a feasible randomized nonstationary Markov policy. At states with zero visitation probability, selecting any feasible action is legitimate; the hypothesis guarantees such an action exists. The stated induction establishes that the recovered policy realizes the prescribed occupancies.
The inequalities involving \(z\) represent the minimum of the types’ expected rewards. Thus maximizing \(z\) gives exactly \(\max_\pi F(\pi)\).
Adding \(-HR\leq z\leq HR\) preserves the optimum, including when rewards are negative or \(R=0\). Occupancies are nonnegative and sum to one at every stage, so the resulting feasible region is bounded and nonempty.
The invoked rational LP theorem is applicable as stated: the LP has rational coefficients, polynomial encoding length, and a nonempty bounded feasible region. Exact rational optimization and policy extraction therefore take \(\operatorname{poly}(m,\tau,n,K,H,L)\) bit operations, with polynomial output length.
The pointwise inequality \(\min_v G_v^\pi\leq G_t^\pi\) holds for every type, without requiring nonnegative rewards. Taking expectations and then minimizing over types gives \(J(\pi)\leq F(\pi)\).
Optimality of \(\pi_F\) consequently supplies the upper bound for every admissible policy. The lower bound follows because \(\pi_F\) itself is admissible.
The policy space is a nonempty finite product of closed simplices and hence compact. Both objectives are continuous: trajectory expectations are finite polynomial expressions in policy probabilities, and taking a finite minimum preserves continuity. Their maxima therefore exist.
Subtracting \(J(\pi_F)\) from the bounds justifies the asserted additive certificate.
The reduction uses an NP-complete satisfiability restriction with exactly three distinct variables per clause. This is consistent with Tovey’s stronger restricted hardness result; the author’s publication summary explicitly identifies the absence of repeated variables within a clause. [Tovey’s publication record](https://sites.gatech.edu/craig-tovey/publications/)
Since \(c\geq1\) and every clause uses three distinct variables, \(d\geq3\). Thus the constructed horizon and tolerance meet the positivity requirements.
The masses are positive dyadic rationals. Their geometric sum is exactly one, including the repeated final mass, and their total binary encoding length is \(O(\tau^2)\).
Zero allocations and zero budgets make the sole action feasible everywhere. With only one action, there is exactly one admissible policy, eliminating any dependence on which MMEU optimizer an algorithm returns.
Starting at \(s_0\), the first transition chooses the value of \(x_1\). Each subsequent transition chooses the next variable’s value. Exactly \(d\) transitions therefore assign all \(d\) variables.
Every assignment has probability \(2^{-d}\), because every prescribed branching transition has probability \(1/2\). Absorption at the final layer introduces no additional rewarded step within the horizon.
A clause’s three distinct variables ensure that each of its literals contributes at its own assignment transition. The clause type’s total reward is therefore its number of true literals.
Every literal is true with probability \(1/2\), so each clause type has expected total reward \(3/2\). Independence between different literals is unnecessary for this expectation calculation.
The anchor’s total reward is always one. Hence \(u=1\).
On an unsatisfying assignment, some clause type receives zero total reward, giving realized minimum zero. On a satisfying assignment, every clause type receives at least one, and the anchor forces the minimum to equal one. Consequently,
\[
\ell=\frac{N(\varphi)}{2^d}.
\]
This is an exact equality, so testing whether the returned lower endpoint is positive decides satisfiability.
The chosen tolerance \(\varepsilon=1-2^{-(d+1)}\) is positive and has polynomial binary encoding length. With \(u=1\), the prescribed comparison becomes
\[
u-\ell\leq\varepsilon
\quad\Longleftrightarrow\quad
\ell\geq2^{-(d+1)}.
\]
An unsatisfiable formula gives \(\ell=0\). A satisfiable formula gives \(\ell\geq2^{-d}>2^{-(d+1)}\). Thus the certificate is conclusive exactly for satisfiable formulas.
The construction has polynomial size, including the explicit transition and reward tables, mass encodings, unary horizon, and tolerance. This establishes the claimed many-one reduction for the certificate decision on the unique-policy subclass.
Although the unique policy is also MEMU-optimal, that does not undermine the reduction: the task requires the particular endpoint-gap certificate, which may legitimately be inconclusive even for an optimal policy.
With the initial state fixed, each stage chooses an action and a successor state, giving at most \((nK)^H\) trajectories. The displayed trajectory probabilities correctly include both policy and transition randomness.
The denominator argument is sound. Each reward total, and therefore its selected minimum, has denominator dividing \(D_r\). Each trajectory probability has denominator dividing \((D_PD_\pi)^H\). Thus every summand shares the stated polynomial-bit-length common denominator.
For any partial sum, nonnegative trajectory probabilities and \(|v_\omega|\leq HR\) give absolute value at most \(HR\). Combined with the common denominator bound, this controls numerator length even when rewards have mixed signs. Exact rational accumulation can therefore be performed with polynomial bit cost per trajectory.
The stated running-time bound follows. The tractable cases \(\tau=1\) and fixed \(H\) are also correct.
Zhang and Shah’s Proposition 1 gives the stated endpoint bounds, and the following discussion proposes Monte Carlo evaluation of the lower bound. The prover correctly distinguishes that proposal from the exact rational evaluation required here. [Zhang and Shah, Proposition 1 and subsequent discussion](https://ojs.aaai.org/index.php/AAAI/article/view/9699/9558)
No additional clarification is needed to make the argument verifiable. The output establishes hardness of the requested certification task, without claiming that its reduction establishes hardness of finding a MEMU-optimal policy.
⟨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.