Answer: NP-hard and undecidable, even for \(m=\tau=1\), fixed logarithmic utilities, and constant program-encoded market coefficients.
Theorem 4.4 — class: other
Given a complete-market, finite-horizon environment, total wealth \(x\), a finite support \(T\) of client types with rational masses \(\mu_t>0\) summing to \(1\), type-specific utility and discount parameters satisfying the paper's assumptions, and a common terminal-wealth utility, find the optimal per-client allocations \(a_t\ge 0\) and common terminal allocation \(a_3\ge 0\), along with their admissible consumption and investment plans, maximizing \(\sum_{t\in T}\mu_t V_t(a_t)+V_3(a_3)\) subject to \(\sum_{t\in T}\mu_t a_t+a_3=x\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Fix binary-rational wealth \(x>0\) and horizon \(h>0\). The market has one riskless asset and \(m\ge1\) risky assets driven by an \(m\)-dimensional Brownian motion with its augmented natural filtration; adapted coefficients \(r,b,\sigma\) give unique strong asset-price solutions, \(\sigma\) is invertible, and the market is complete. Set \(D_s=\exp(-\int_0^s r_u\,du)\), let \(Z_s\) be the density process of its unique equivalent martingale measure, assumed a true martingale, and set \(q_s=D_sZ_s\).
Each type has utility \(U_t\) and a bounded adapted discount rate \(\beta_t\); terminal wealth has utility \(U_3\) and bounded adapted discount rate \(\beta_3\). Discount rates may have either sign. Write \(B_{i,s}=\exp(-\int_0^s\beta_{i,u}\,du)\). Every utility is strictly increasing and strictly concave, belongs to \(C^2((0,\infty))\), has nondecreasing second derivative and marginal utility tending to zero at infinity, and is extended at zero by its limit, possibly \(-\infty\).
For \(i\in T\cup\{3\}\), let \(I_i\) be inverse marginal utility, extended by zero above \(U_i'(0+)\). For every \(y>0\), assume finiteness of \(H_t(y)=\mathbb E\int_0^h q_s I_t(yq_s/B_{t,s})\,ds\) and \(H_3(y)=\mathbb E[q_hI_3(yq_h/B_{3,h})]\), absolute integrability of the corresponding discounted utilities, and differentiability of their expectations with differentiation permitted under expectation and integration.
An admissible plan is self-financing apart from its nonnegative, progressively measurable, pathwise integrable consumption; it receives no subsequent endowment and keeps wealth nonnegative almost surely throughout the horizon. Short positions and borrowing are allowed subject to that wealth condition. Only plans with finite expected utility are considered.
Define \(V_t(a)=\sup\mathbb E\int_0^h B_{t,s}U_t(c_s)\,ds\) over admissible plans starting from \(a\), and \(V_3(a)=\sup\mathbb E[B_{3,h}U_3(X_h)]\) over admissible plans starting from \(a\) with zero consumption. At zero wealth use their extended-real limiting values.
The optimization is to choose \(a_t,a_3\ge0\) and implementing plans maximizing \(\sum_{t\in T}\mu_tV_t(a_t)+V_3(a_3)\), subject to \(\sum_{t\in T}\mu_ta_t+a_3=x\); aggregate consumption and investment are weighted by the same masses.
For a finite computational input, utilities and market and discount coefficient functionals are supplied as programs in the standard computable-analysis representation, with computable nonanticipating coefficient functionals; all stated assumptions are promises. Let \(L\) be the total binary input length, including programs and a rational threshold \(K\). The exact threshold problem asks whether the optimal value is at least \(K\).
Is this exact threshold problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite household with two consumption streams and shared terminal wealth, an optimal sharing rule and implementing plans are analytically characterized by inverse aggregate dual-budget functions; extension to more consumption streams is explicitly discussed ([source](https://arxiv.org/pdf/1402.1052v3)). This establishes no bit-complexity bound; the search located no classification for the program-encoded exact threshold problem above.
The exact threshold problem is NP-hard and undecidable, even with \(m=\tau=1\), fixed logarithmic utilities, zero utility discount rates, and constant market coefficients supplied as computable programs. Consequently, it has no polynomial-time decision algorithm under the stated representation.
The proof computes the optimal value explicitly on a restricted family and then gives reductions whose outputs satisfy every promise.
Fix a computable constant \(\alpha\in[0,1/2]\). Take \(T=\{1\}\), \(\mu_1=1\), \(x=2\), \(h=1\), and \(K=0\). Set
\(U_1(z)=U_3(z)=\log z,\qquad \beta_1=\beta_3=0.\)
Use one risky asset, with initial price \(1\), and constant coefficients
\(r=b=-\alpha,\qquad \sigma=1.\)
The bank account and risky asset have the unique strong solutions
\(S^0_s=e^{-\alpha s},\qquad S_s=e^{(-\alpha-1/2)s+W_s}.\)
Thus \(D_s=e^{\alpha s}\), and the discounted risky price is
\(\widetilde S_s=D_sS_s=e^{W_s-s/2},\qquad d\widetilde S_s=\widetilde S_s\,dW_s.\)
The physical measure is an equivalent martingale measure. Completeness follows from Brownian martingale representation: in the augmented natural Brownian filtration, every integrable discounted payoff has a conditional-expectation martingale representable as a stochastic integral against \(W\). Since \(\widetilde S_s>0\), that integral can be implemented by trading \(\widetilde S\).
For uniqueness, any equivalent measure has a positive density martingale locally representable as \(dZ_s=Z_s\theta_s\,dW_s\). Girsanov’s theorem makes the drift of \(\widetilde S\) under that measure equal to \(\widetilde S_s\theta_s\). The martingale requirement forces \(\theta=0\) almost everywhere. Hence the unique density is \(Z_s=1\), a true martingale, and
\(q_s=e^{\alpha s}.\)
All coefficients are computable nonanticipating functionals: they ignore both time and the observed path.
The utilities satisfy the required conditions because
\(U'(z)=1/z,\qquad U''(z)=-1/z^2,\qquad \frac{d}{dz}U''(z)=2/z^3>0.\)
Their extension at zero is \(-\infty\), and their inverse marginal utility is \(I(y)=1/y\). Consequently,
\(H_1(y)=\int_0^1 e^{\alpha s}\frac{1}{ye^{\alpha s}}\,ds=\frac1y,\qquad H_3(y)=e^\alpha\frac{1}{ye^\alpha}=\frac1y.\)
The corresponding utility expectations are
\(\int_0^1\log I(ye^{\alpha s})\,ds=-\log y-\frac{\alpha}{2},\qquad \log I(ye^\alpha)=-\log y-\alpha.\)
They are absolutely integrable. Differentiation under integration is valid: on every compact interval of positive \(y\), the deterministic integrands and their derivatives are uniformly bounded. Thus every analytic promise holds.
First establish the budget bound without assuming optimality.
For any admissible plan starting from \(a\), discounted self-financing gives
\(M_s:=D_sX_s+\int_0^sD_uc_u\,du=a+\int_0^s\varphi_u\,dW_u\)
for a stochastically integrable trading process \(\varphi\). Nonnegative wealth and consumption imply \(M_s\geq0\). A nonnegative local martingale is a supermartingale; explicitly, localization followed by Fatou’s lemma gives
\(\mathbb E\!\left[e^\alpha X_1+\int_0^1e^{\alpha s}c_s\,ds\right]\leq a.\)
For \(a>0\), the supporting-line inequality for logarithmic utility gives
\(\log c_s\leq\log(ae^{-\alpha s})+\frac{e^{\alpha s}c_s}{a}-1.\)
The inequality also holds in the extended-real sense when \(c_s=0\). Taking expectations and integrating, the budget bound yields
\(\mathbb E\int_0^1\log c_s\,ds\leq\log a-\frac{\alpha}{2}+\frac1a\mathbb E\int_0^1e^{\alpha s}c_s\,ds-1\leq\log a-\frac{\alpha}{2}.\)
Equality is attained by holding only the bank account and choosing
\(c_s=ae^{-\alpha s},\qquad X_s=a(1-s)e^{-\alpha s}.\)
Indeed, this nonnegative wealth satisfies \(dX_s=-\alpha X_s\,ds-c_s\,ds\), and the utility is finite. Therefore
\(V_1(a)=\log a-\frac{\alpha}{2}.\)
For zero consumption, the budget bound gives \(\mathbb E[e^\alpha X_1]\leq a\). Applying the supporting-line inequality at \(ae^{-\alpha}\),
\(\mathbb E\log X_1\leq\log a-\alpha+\frac{\mathbb E[e^\alpha X_1]}{a}-1\leq\log a-\alpha.\)
Holding only the bank account, with \(X_s=ae^{-\alpha s}\), attains equality. Hence
\(V_3(a)=\log a-\alpha.\)
Both value functions tend to \(-\infty\) at zero, as prescribed.
For positive allocations satisfying \(a_1+a_3=2\), the objective is
\(\log a_1+\log a_3-\frac{3\alpha}{2}.\)
Because \(a_1a_3\leq((a_1+a_3)/2)^2=1\), its maximum is attained at \(a_1=a_3=1\). Boundary allocations have value \(-\infty\). Thus the optimal value is exactly
\(\operatorname{OPT}(\alpha)=-\frac{3\alpha}{2}.\)
The two bank-account plans above implement this allocation; their aggregate wealth is \(e^{-\alpha s}(2-s)\geq0\). In particular,
\(\operatorname{OPT}(\alpha)\geq K=0\quad\Longleftrightarrow\quad\alpha=0.\)
Given a machine \(M\) and input \(w\), count execution steps starting at \(1\), and define
\(\alpha_{M,w}=\begin{cases}2^{-s},&\text{if $M(w)\) first halts at step \(s\)},\\0,&\text{if \(M(w)\) never halts}.\end{cases}\)
This is a computable real uniformly in \(M,w\). To approximate it within \(2^{-n}\), simulate the first \(n\) steps. Return \(2^{-s}\) if halting occurs at step \(s\leq n\); otherwise return \(0\).
If halting occurs later, its step satisfies \(s\geq n+1\), so the approximation error is at most \(2^{-(n+1)}\). If it never occurs, the returned value is exact. Every approximation request therefore terminates.
A fixed wrapper containing \(M,w\) supplies the constant coefficient programs \(r=b=-\alpha_{M,w}\). Constructing this wrapper requires no determination of whether the machine halts. Its description length is polynomial in the descriptions of \(M,w\).
Every resulting instance belongs to the promised family above, and
\(\operatorname{OPT}(\alpha_{M,w})\geq0\quad\Longleftrightarrow\quad M(w)\text{ does not halt}.\)
A threshold algorithm terminating correctly on all promised inputs would therefore decide nonhalting, contradicting undecidability of the halting problem. The threshold problem is undecidable even on this restricted family.
Undecidability alone does not supply the required polynomial-time reduction, so we give one explicitly.
Given a Boolean formula \(\phi\), construct a machine \(M_\phi\) that exhaustively checks all assignments. If it finds a satisfying assignment, it loops forever. If it exhausts the assignments without finding one, it halts. Thus
\(M_\phi\text{ does not halt}\quad\Longleftrightarrow\quad\phi\text{ is satisfiable}.\)
Its description consists of a fixed search routine and the embedded formula. Producing this description, the computable-real wrapper, and the remaining fixed market data takes polynomial time in the formula length. The potentially exponential search is performed inside the encoded program, not during the reduction.
The preceding value calculation gives
\(\phi\text{ is satisfiable}\quad\Longleftrightarrow\quad\operatorname{OPT}(\alpha_{M_\phi})\geq0.\)
Since Boolean satisfiability is NP-complete, this is a polynomial-time many-one reduction proving NP-hardness. Every output satisfies all promises, and \(m,\tau,x,h,K\) remain fixed.
The cited paper characterizes allocation through inverse aggregate budget functions ([Theorem 4.4](https://arxiv.org/html/1402.1052v3)). Our family admits precisely such an elementary characterization: \(H_1(y)+H_3(y)=2/y\), so wealth \(2\) gives multiplier \(y=1\) and allocation \(a_1=a_3=1\).
The unresolved computational comparison is exact equality of a program-represented computable constant to zero. Here the optimal value is itself uniformly computable, yet deciding whether it reaches the threshold is undecidable. Thus the hardness persists with fixed normalized utilities and an explicitly solved allocation problem.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes NP-hardness and undecidability for the promised, program-encoded exact threshold problem, even when \(m=\tau=1\). I found no major or minor mathematical issues.
The distinction between program description length and the running time of the encoded programs is essential. The task permits computable coefficient programs without imposing polynomial evaluation time, so both reductions fit the stated representation.
The fixed data \(T=\{1\}\), \(\mu_1=1\), \(x=2\), \(h=1\), and \(K=0\) satisfy the support, mass, rationality, and positivity requirements. The parameter range \(\alpha\in[0,1/2]\) is consistent with every subsequent construction.
The asset-price formulas correctly solve the stated constant-coefficient equations. Discounting gives
\[
\widetilde S_s=e^{W_s-s/2},
\]
which is a true martingale on the finite horizon. Thus the physical measure is an equivalent martingale measure.
The completeness argument correctly invokes Brownian martingale representation in the stipulated augmented natural filtration. The strictly positive discounted risky price permits conversion of the Brownian integrand into a trading strategy. The uniqueness argument also has the correct Girsanov sign: with density dynamics \(dZ_s=Z_s\theta_s\,dW_s\), the discounted risky asset acquires drift \(\widetilde S_s\theta_s\) under the new measure. Its martingale property forces \(\theta=0\) almost everywhere. Consequently, \(Z=1\) and \(q_s=e^{\alpha s}\) are justified.
For logarithmic utility, the derivative calculations establish strict increase, strict concavity, nondecreasing second derivative, and marginal utility tending to zero. The extension at zero and inverse marginal utility are correct.
Both dual-budget calculations give \(1/y\). The corresponding utility integrals are finite and absolutely integrable for every \(y>0\). Uniform bounds on compact positive \(y\)-intervals justify the stated differentiation. The coefficient functionals are constant and nonanticipating; their computability is verified by the later encoding.
Assessment: Every promise required for the restricted family is met.
The discounted wealth-plus-consumption identity correctly follows from self-financing in this market. Its stochastic-integral term is a local martingale, and nonnegative wealth and consumption make the entire process nonnegative.
The theorem used here applies: a nonnegative local martingale is a supermartingale. The resulting bound
\[
\mathbb E\!\left[e^\alpha X_1+\int_0^1e^{\alpha s}c_s\,ds\right]\leq a
\]
has the correct discount factors and direction.
This argument covers arbitrary admissible trading strategies, including those involving borrowing or short positions. It therefore supplies the required upper bound over the full admissible class.
Assessment: Correct.
The logarithmic supporting-line inequalities are evaluated at the correct positive comparison quantities. Their use at zero in the extended-real sense is valid.
The expectation and integration steps are legitimate for the finite-expected-utility plans under consideration. The budget bound also controls the positive part of the logarithmic integrands, so the displayed inequalities do not conceal an undefined cancellation of infinities.
The proposed consumption plan is deterministic, progressively measurable, nonnegative, and pathwise integrable. Its wealth starts at \(a\), remains nonnegative, and satisfies the displayed self-financing equation. It attains the upper bound. Thus
\[
V_1(a)=\log a-\frac{\alpha}{2}
\]
is established for every \(a>0\).
The terminal bank-account plan likewise satisfies admissibility and attains the terminal upper bound, establishing
\[
V_3(a)=\log a-\alpha.
\]
Both formulas tend to \(-\infty\) as \(a\downarrow0\), exactly matching the task’s convention for zero wealth.
Assessment: Correct, including attainability and the zero-wealth boundary.
Because the sole mass equals one, the allocation constraint is exactly \(a_1+a_3=2\). The objective and product bound are correct, and equality occurs at \(a_1=a_3=1\). Boundary allocations cannot compete because their objective is \(-\infty\).
The resulting value
\[
\operatorname{OPT}(\alpha)=-\frac{3\alpha}{2}
\]
has the correct constant and sign. The implementing plans aggregate with the required masses, and their aggregate wealth is correctly calculated.
Since \(\alpha\geq0\), the equivalence
\[
\operatorname{OPT}(\alpha)\geq0\quad\Longleftrightarrow\quad\alpha=0
\]
is exact, including equality at the threshold.
Assessment: Correct.
The approximation program terminates for every requested precision. If halting occurs after the simulated \(n\) steps, the error is at most \(2^{-(n+1)}\), hence within \(2^{-n}\). Halting at an observed step is handled exactly.
Counting steps from one ensures \(\alpha_{M,w}\in[0,1/2]\). The construction is uniform in the machine and input, and it does not require deciding halting when producing the coefficient programs.
The equivalence between a yes-instance of the threshold problem and nonhalting has the correct direction. Every produced input satisfies the promises regardless of whether the encoded machine halts. Therefore, a decision algorithm terminating on all promised inputs would decide nonhalting.
Assessment: Undecidability is established.
The machine \(M_\phi\) behaves as claimed:
Constructing its description requires embedding the formula in a fixed routine. The exhaustive search occurs during execution of the encoded program, so its potentially exponential duration does not invalidate the polynomial-time reduction.
Combining this behavior with the verified threshold equivalence gives a polynomial-time many-one reduction from satisfiability. All outputs remain promised instances with fixed \(m,\tau,x,h,K\).
Assessment: NP-hardness is established independently of the undecidability argument.
The description of the paper’s sharing-rule characterization agrees with [Theorem 4.4](https://arxiv.org/html/1402.1052v3). That citation is contextual: the restricted-family value calculation and both reductions are proved independently.
The concluding representation claim is accurate. A uniformly computable optimal value need not admit a decidable exact threshold comparison. The proof addresses precisely the program-encoded exact decision problem in USER_TASK.
No additional clarification, missing lemma, or repair is required. The prover’s claimed conclusion follows from the written argument.
⟨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.