Answer: \(\mathrm{NP}\)-complete
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe following decision problem is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many complete MDP types \(T\), rational masses \(\mu_t\) summing to \(1\), each type’s local capacity limits, and per-capita stocks \(\bar b_o\), choose bundle masses \(y_{t,w}\ge 0\) over each type’s locally feasible integral bundles \(W_t\). Require \(\sum_{w\in W_t} y_{t,w}=\mu_t\) for every type and \(\sum_{t\in T}\sum_{w\in W_t} y_{t,w}w_o\le \bar b_o\) for every resource \(o\). Is there such an assignment with \(\sum_{t\in T}\sum_{w\in W_t} y_{t,w}V_t(w)\ge Y\), where \(V_t(w)\) is the maximum expected discounted reward for type \(t\) under bundle \(w\)?
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge 1\) non-consumable resource types and \(K\ge 1\) capacity dimensions. Each type supplies an explicitly tabulated finite discounted MDP \((S_t,A_t,p_t,r_t,\alpha_t)\), including its initial probability distribution, and action requirements \(\rho_t(a,o)\in\{0,1\}\). The common discount factor satisfies \(0<\gamma<1\); rewards are signed rationals. Every type has a resource-free, zero-reward action that leaves the state unchanged.
Resource capacity costs \(\kappa(o,c)\ge 0\) are common to all types; local bounds \(b_t(c)\ge 0\) and per-capita stocks \(\bar b_o\ge 0\) are rational. All numerical input is encoded in binary.
Define \(W_t=\{w\in\{0,1\}^m:\sum_o\kappa(o,c)w_o\le b_t(c)\text{ for every }c\}\). These sets are implicit, not enumerated input.
Under bundle \(w\), precisely the actions satisfying \(\rho_t(a,o)\le w_o\) for every resource \(o\) are enabled. Resources are allocated once before execution, are never consumed or reallocated, and types' MDPs operate independently thereafter.
Let \(V_t(w)\) be the maximum expected total discounted reward from \(\alpha_t\) in the MDP restricted to those enabled actions; stationary deterministic policies suffice, and ties do not affect this value.
Given a rational threshold \(Y\), the decision problem asks whether there exist real masses \(y_{t,w}\ge 0\) satisfying \(\sum_{w\in W_t}y_{t,w}=\mu_t\) for every \(t\), \(\sum_t\sum_{w\in W_t}y_{t,w}w_o\le\bar b_o\) for every \(o\), and \(\sum_t\sum_{w\in W_t}y_{t,w}V_t(w)\ge Y\).
Is this mass allocation decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
State running times in \(m,\tau,K,n,a,L\), where \(n=\max_t|S_t|\), \(a=\max_t|A_t|\), and \(L\) is the total binary input length.
The discrete single-agent capacity-constrained policy decision problem is \(\mathrm{NP}\)-complete, already with binary action requirements and one capacity dimension; discrete multiagent welfare decision is also \(\mathrm{NP}\)-complete. [Dolgov and Durfee](https://ai.stanford.edu/~ddolgov/papers/dolgov_resourceMDP_jair06.pdf)
No published complexity classification for the exact mass allocation problem above was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds already with \(\tau=1\), \(K=1\), \(\gamma=\tfrac12\), unit capacity costs, rewards in \(\{0,1\}\), and absorbing states.
Allowing real masses does not remove the hardness: when stocks impose no additional restriction, the welfare of a mixture cannot exceed the best locally feasible bundle value.
The [Dolgov–Durfee paper](https://ai.stanford.edu/~ddolgov/papers/dolgov_resourceMDP_jair06.pdf) establishes hardness for discrete capacity-constrained policies. The reduction below proves hardness directly for the stated mass allocation problem.
Fix a type \(t\) and a locally feasible bundle \(w\). Let \(A_t(w)\) denote its enabled actions. The resource-free action ensures that this set is nonempty.
Define the Bellman operator by
\( (T_wv)(s)=\max_{a\in A_t(w)}\left(r_t(s,a)+\gamma\sum_{s'}p_t(s'\mid s,a)v(s')\right). \)
Because transition probabilities sum to one, this operator is a contraction with factor \(\gamma<1\) in the maximum norm. It therefore has a unique fixed point \(v^*\), the optimal state-value vector.
It can be obtained from the rational linear program
\( \displaystyle \min_v\sum_{s\in S_t}v(s), \)
subject to
\( \displaystyle v(s)\ge r_t(s,a)+\gamma\sum_{s'}p_t(s'\mid s,a)v(s') \qquad(s\in S_t,\ a\in A_t(w)). \)
To verify this formulation, any feasible vector satisfies \(v\ge T_wv\). Monotonicity gives \(v\ge T_w^kv\) for every \(k\), and contraction implies \(T_w^kv\to v^*\). Thus every feasible vector dominates \(v^*\) coordinatewise. Since \(v^*\) itself is feasible, it is the unique minimizer.
This linear program has at most \(n\) variables and \(na\) inequalities, with explicitly represented rational coefficients. Polynomial-time algorithms for rational linear programming therefore compute
\( \displaystyle V_t(w)=\sum_s\alpha_t(s)v^*(s) \)
exactly in \(\operatorname{poly}(n,a,L)\) bit operations.
The resulting rational value has polynomial binary length. Indeed, choose an optimal stationary deterministic policy \(\pi\). Its value satisfies
\( \displaystyle (I-\gamma P_\pi)v_\pi=r_\pi. \)
The matrix is invertible because \(\|\gamma P_\pi\|_\infty=\gamma<1\). Clearing denominators and applying determinant bounds shows that the solution, and hence \(\alpha_t^\mathsf{T}v_\pi\), has binary length polynomial in \(n\) and \(L\). This remains true when \(\gamma\) is close to one.
Consider the finite allocation polytope \(Q\) defined by the type-mass equalities, stock inequalities, and nonnegativity, without the welfare threshold.
Although its columns are implicit in the input, their number is finite: at most \(\tau2^m\). The polytope is nonempty because every type can receive the empty bundle. It is bounded because
\( \displaystyle 0\le y_{t,w}\le\mu_t. \)
Consequently, the linear welfare objective attains its maximum at a vertex of \(Q\).
Suppose a vertex has \(q>\tau+m\) positive coordinates. Restrict the coefficient matrix of the type-mass equalities and all stock inequalities to these coordinates. It has \(\tau+m\) rows and \(q\) columns, so there is a nonzero vector \(d\) in its nullspace.
For sufficiently small \(\varepsilon>0\), both \(y+\varepsilon d\) and \(y-\varepsilon d\), with zero perturbation outside the positive coordinates, remain nonnegative. They preserve every type mass and every stock usage. They are therefore two distinct feasible points whose midpoint is \(y\), contradicting extremality.
Thus every vertex has at most \(\tau+m\) positive coordinates. In particular, every yes-instance has an allocation meeting the threshold with this support bound.
Let a vertex have \(q\le\tau+m\) positive coordinates. The type equalities and tight stock inequalities, restricted to these coordinates, must have column rank \(q\).
Otherwise, a nonzero null direction would preserve these constraints. Small perturbations in both directions would preserve nonnegativity and the remaining stock inequalities, which have positive slack, again contradicting extremality.
Choose \(q\) independent rows. The positive masses are the unique solution of
\( \displaystyle By=d, \)
where \(B\) is an invertible \(q\times q\) matrix with entries in \(\{0,1\}\), and the entries of \(d\) are input masses or stocks.
Clearing the denominators in \(d\), followed by Cramer’s rule and Hadamard’s determinant bound, gives a binary-length bound of
\( \displaystyle O\!\left(q\bigl(L+\log(q+1)\bigr)\right) \)
for each mass. Hence these masses have polynomial-size rational representations.
A certificate can list at most \(\tau+m\) tuples, each containing:
The verifier checks local capacities, type masses, stocks, and policy enablement. It evaluates each listed policy by solving its rational linear system, then checks that the weighted policy values meet \(Y\).
This is sound because each listed policy’s value is at most \(V_t(w)\). It is complete because a maximizing vertex can be equipped with optimal stationary deterministic policies.
The certificate size and verification time are both \(\operatorname{poly}(m,\tau,K,n,a,L)\). Therefore the problem belongs to \(\mathrm{NP}\).
Let a \(3\)-SAT instance have variables \(x_1,\ldots,x_d\) and clauses \(C_1,\ldots,C_h\), with \(d,h\ge1\). We construct one type.
For each variable, create two resources \(o_{i,+}\) and \(o_{i,-}\), representing its positive and negative literals. Thus
\( \displaystyle m=2d,\qquad \tau=1,\qquad \mu_1=1. \)
Use one capacity dimension with
\( \displaystyle \kappa(o,1)=1,\qquad b_1(1)=d. \)
Therefore a bundle is locally feasible exactly when it contains at most \(d\) resources.
Set every per-capita stock to one:
\( \displaystyle \bar b_o=1. \)
These stock constraints impose no additional restriction: for any mass-one allocation, the mass receiving a given resource is at most one.
Let \(N\) be the smallest power of two satisfying \(N\ge d+h\). Create:
Give every state initial probability \(1/N\), and set \(\gamma=\tfrac12\). All states are absorbing under every action.
For every literal \(\ell\), create an action \(a_\ell\) requiring exactly the resource representing \(\ell\). Add a resource-free action \(a_0\) with zero reward everywhere.
Define rewards as follows:
This satisfies all premises. In particular, the action requirements are binary, and \(a_0\) is a resource-free, zero-reward action leaving the state unchanged.
Call a variable state covered when the bundle contains at least one of its two literal resources. Call a clause state covered when the bundle contains a resource representing a literal in that clause. Let \(c(w)\) be the number of covered variable and clause states.
At a covered state, an enabled action can earn reward one forever, giving discounted value
\( \displaystyle \sum_{k=0}^\infty(1/2)^k=2. \)
At an uncovered state, every enabled action earns zero. Since all states are absorbing, it follows exactly that
\( \displaystyle V_1(w)=\frac{2c(w)}{N}. \)
Set the decision threshold to
\( \displaystyle Y=\frac{2(d+h)}{N}. \)
Every bundle has value at most \(Y\), with equality precisely when it covers every variable state and every clause state.
Suppose the formula has a satisfying assignment. Select exactly one resource for each variable: its positive resource when the variable is true, and its negative resource otherwise.
The resulting bundle contains \(d\) resources and is locally feasible. It covers every variable state. Since the assignment satisfies every clause, it also covers every clause state. Thus its value is \(Y\).
Assigning the entire mass to this bundle gives a yes-instance of mass allocation.
Conversely, suppose a feasible mass allocation reaches the threshold. Since its total mass is one and every bundle value is at most \(Y\),
\( \displaystyle \sum_w y_{1,w}\bigl(Y-V_1(w)\bigr)\le0. \)
Every summand is nonnegative, so every positive-mass bundle has value \(Y\). At least one such bundle exists.
Choose one. Covering every variable state requires at least one resource for each of the \(d\) variables. Local feasibility permits at most \(d\) resources. Hence the bundle contains exactly one literal resource for each variable.
These choices define a truth assignment. Every clause state is covered, so every clause contains a selected literal, which is true under this assignment. The formula is therefore satisfiable.
The construction has
\( \displaystyle m=2d,\quad \tau=K=1,\quad n=N<2(d+h),\quad a=2d+1. \)
Transitions, rewards, initial probabilities, and requirements can all be explicitly tabulated in polynomial time. All probabilities and thresholds are dyadic rationals, and all numerical magnitudes are polynomially bounded.
Thus this is a polynomial-time many-one reduction from \(3\)-SAT. Combined with membership in \(\mathrm{NP}\), it proves \(\mathrm{NP}\)-completeness.
An exact deterministic algorithm can enumerate the bundles, compute their values, and solve the resulting allocation linear program.
There are at most \(\tau2^m\) type-bundle pairs. Testing local feasibility and identifying enabled actions takes
\( \displaystyle O\!\left(\tau2^m m(K+a)\right)\operatorname{poly}(L) \)
bit operations. Computing all feasible bundle values takes
\( \displaystyle \tau2^m\operatorname{poly}(n,a,L). \)
The final allocation linear program has at most \(\tau2^m\) variables, \(\tau\) type equalities, \(m\) stock inequalities, and rational coefficients of polynomial binary length. Its solution time is
\( \displaystyle \operatorname{poly}(\tau2^m,\tau+m,n,L). \)
Together, these give an exact deterministic bound of
\( \displaystyle 2^{O(m)}\operatorname{poly}(m,\tau,K,n,a,L). \)
Consequently, the problem is polynomial-time solvable for every fixed \(m\). For unrestricted \(m\), it is \(\mathrm{NP}\)-complete, so a polynomial-time algorithm in all the stated input parameters would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly. The mass allocation decision problem is $\mathrm{NP}$-complete, and the proof establishes hardness under all the restrictions claimed. The certificate argument handles real allocation masses rigorously. The running-time bounds are valid.
No major or minor mathematical issues were found.
The Bellman argument is valid. For any feasible bundle, the resource-free action ensures a nonempty enabled action set. Since each transition row is a probability distribution, the Bellman operator is a contraction with factor $\gamma$ in the maximum norm. Signed rewards cause no difficulty in this finite discounted setting.
The linear program correctly computes the optimal value vector. Its constraints are exactly $v\ge T_wv$. Monotonicity justifies iterating this inequality, and contraction gives convergence to $v^*$. Therefore every feasible vector dominates $v^*$ coordinatewise. The fixed point is itself feasible, so minimizing the sum of coordinates uniquely selects it.
The polynomial-time claim is justified. The invoked rational linear programming result applies to an explicitly represented rational LP with at most $n$ variables and $na$ inequalities. The preceding argument establishes feasibility and an attained finite optimum, so exact optimization applies.
The polynomial bit-length claim is also valid. Optimal stationary deterministic policies are available by the problem’s premises. For such a policy, $I-\gamma P_\pi$ is invertible because $\|\gamma P_\pi\|_\infty<1$. Clearing rational denominators and applying determinant bounds yields polynomial binary length for its value vector and initial-distribution value. This argument depends on the binary encoding of $\gamma$, not on a lower bound on $1-\gamma$, so it remains valid when $\gamma$ is close to one.
The allocation polytope is nonempty and bounded. Giving each type the empty bundle satisfies local capacities and stocks because all bounds are nonnegative. Nonnegativity and the type-mass equations imply $y_{t,w}\le\mu_t$. The number of coordinates is finite, so a welfare maximum exists and is attained at a vertex.
The support bound is correct. If a vertex had more than $\tau+m$ positive coordinates, the restricted matrix of type equations and stock usages would have a nonzero null direction. A sufficiently small perturbation in either direction preserves nonnegativity, all type masses, and every stock usage. The resulting two distinct feasible points contradict extremality.
This argument validly uses all stock rows, including slack ones: preserving their usages certainly preserves feasibility.
The rank argument for rational masses is correct. If the type equations and tight stock constraints had deficient column rank on the positive support, a nonzero null direction would preserve them. The remaining stock inequalities have positive slack, so sufficiently small perturbations preserve those as well. This again contradicts extremality.
Consequently, selecting $q$ independent rows produces an invertible square system with entries in $\{0,1\}$. Its right-hand side consists of input masses and stocks. Cramer’s rule and Hadamard’s bound justify the stated mass bit-length bound
$$
O\!\left(q\bigl(L+\log(q+1)\bigr)\right).
$$
The bound is conservative but sufficient.
Certificate verification is sound and complete. The verifier checks all allocation constraints and evaluates each certified enabled stationary policy exactly. A policy value cannot exceed the corresponding optimal bundle value, so reaching the threshold with certified policy values implies a yes-instance. Conversely, a maximizing vertex can be equipped with optimal policies, giving a certificate for every yes-instance.
The number of listed bundles, their descriptions, their masses, and their policies all have polynomial total size. Exact linear-system evaluation and rational comparisons take polynomial time. Thus membership in $\mathrm{NP}$ is established.
The construction meets the input requirements. It uses one type, one capacity dimension, $2d$ resources, unit capacity costs, local capacity $d$, and stocks equal to one. Every action requirement is binary. The resource-free action has zero reward and leaves the state unchanged.
Uniform initial probabilities $1/N$ and the threshold are dyadic rationals. Every transition is deterministic and absorbing, and rewards belong to $\{0,1\}$.
The stocks impose no restriction beyond total mass. With one type of mass one and binary resource indicators, the total mass assigned any particular resource is at most one.
The bundle-value computation is exact. At a covered state, an enabled action earns reward one at every time step, giving value
$$
\sum_{k=0}^{\infty}(1/2)^k=2.
$$
At an uncovered state, every enabled action has zero reward. Absorption prevents reaching any other state. Averaging over the uniform initial distribution gives precisely
$$
V_1(w)=\frac{2c(w)}{N}.
$$
Hence every bundle value is at most $Y$, and equality holds exactly when all variable and clause states are covered.
The forward implication is valid. A satisfying assignment selects exactly one literal resource per variable. The resulting bundle has size $d$, covers every variable state, and covers every clause state. Allocating all mass to it reaches $Y$.
The reverse implication correctly handles arbitrary real mixtures. Since total mass is one and every bundle value is at most $Y$, reaching the threshold forces every positive-mass bundle to have value $Y$. The index set is finite, and total mass is positive, so at least one such bundle exists.
Covering all $d$ variable states requires at least one resource from each variable’s pair. Capacity permits at most $d$ resources, so the chosen bundle contains exactly one from every pair. These choices define a consistent assignment. Covering each clause state then means that clause contains a selected, true literal.
Thus feasibility implies satisfiability.
The reduction has polynomial size. The stated parameters satisfy
$$
m=2d,\qquad \tau=K=1,\qquad n=N<2(d+h),\qquad a=2d+1.
$$
Even explicitly tabulating all transitions, rewards, and requirements requires only polynomial space and time in the formula size. The restriction to source instances with $d,h\ge1$ does not affect hardness.
The reduction is independent of the cited Dolgov–Durfee result; that citation supplies context rather than a necessary proof step.
The enumeration algorithm is valid. Checking capacities and enabled actions has the stated bound, computing each bundle value is polynomial in the explicit MDP encoding, and the final allocation LP has at most $\tau2^m$ variables with polynomial-length coefficients.
Applying polynomial-time rational LP optimization to this explicit LP gives the overall bound
$$
2^{O(m)}\operatorname{poly}(m,\tau,K,n,a,L).
$$
Therefore the fixed-$m$ polynomial-time conclusion is justified. For unrestricted $m$, the reduction and certificate argument establish $\mathrm{NP}$-completeness.
No clarification or repair is required.
⟨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.