Answer: Polynomial-time solvable.
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf ln pr (1−p)(1−β) ≤0, the investment game under the rule PRO has a unique dominant strategy equilibrium (0, ..., 0) . Otherwise, the game has a unique dominant strategy equi- librium s∗in which each agent i chooses a positive investment level s∗ i given by s∗ i = 1 ai (r + 1 −β) ln pr (1 −p)(1 −β) . There is no other Nash equilibria.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational \(p,r,\beta\) and a finite-support risk-aversion distribution \((a_j,\mu_j)_{j=1}^{\tau}\), where \(a_j>0\), \(\mu_j\ge 0\), and \(\sum_j\mu_j=1\), compute the unique type-level equilibrium investments under PRO and their average \(̅s=\sum_j\mu_js_j\), exactly or to additive error \(\epsilon\). Each type chooses \(s_j\ge 0\) to maximize the paper's CARA expected utility, with success return \(rs_j\) and bankruptcy award \(\beta s_j\).
A society is given by its support: \(\tau\geq 1\) distinct risk-aversion types \(a_j\in\mathbb{Q}_{>0}\), each with positive binary-rational mass \(\mu_j\), and \(\sum_{j=1}^{\tau}\mu_j=1\). Here \(\tau\) is the support size, not the number of possible types.
The common binary-rational parameters satisfy \(0<p<1\), \(0<r\leq 1\), and \(0<\beta<1\). Each investor chooses an unrestricted investment \(s\in\mathbb{R}_{\geq 0}\).
Under PRO, the bankruptcy award is \(\beta s\); after subtracting the invested principal, net returns are \(rs\) with probability \(p\) and \((\beta-1)s\) otherwise. Type \(a_j\) maximizes \(U_j(s)=-p\exp(-a_jrs)-(1-p)\exp(a_j(1-\beta)s)\).
A type-level equilibrium \(s^*\) assigns each type a maximizing investment; its average is \(\bar{s}^*=\sum_{j=1}^{\tau}\mu_js_j^*\).
Given binary-rational \(0<\epsilon<1\), the computational problem is to approximate every \(s_j^*\) and \(\bar{s}^*\) within absolute error \(\epsilon\). Let \(L\) be the total binary input length, including the precision input; the number of investment opportunities is fixed at \(m=1\).
Is this equilibrium-computation problem solvable in polynomial time in \(\tau\), \(L\), and \(\lceil\log_2(1/\epsilon)\rceil\), or is it NP-hard?
For finite societies, PRO has a unique equilibrium in strictly dominant strategies, with an explicit closed-form characterization ([source](https://research.sabanciuniv.edu/14704/1/Bankruptcy_5_10_10.pdf)). No result settling the bit complexity of the distributional computation problem was identified in the search.
The problem is solvable in deterministic polynomial time in \(\tau\), \(L\), and \(\lceil\log_2(1/\epsilon)\rceil\). The proof below includes an explicit rational-arithmetic algorithm and error bounds.
We use the usual bit model: input rationals have explicitly encoded binary numerators and denominators, and the outputs are dyadic rational approximations.
Put \(b=1-\beta>0\), and define
\(Q=\dfrac{pr}{(1-p)b}\) and \(c_j=a_j(r+b)>0\).
For each type,
\(U_j'(s)=a_jpr\,e^{-a_jrs}-a_j(1-p)b\,e^{a_jbs}\), and
\(U_j''(s)=-a_j^2\bigl(pr^2e^{-a_jrs}+(1-p)b^2e^{a_jbs}\bigr)<0\).
Thus \(U_j'\) is strictly decreasing.
If \(Q\leq1\), then \(U_j'(0)\leq0\). Consequently \(U_j'(s)<0\) for every \(s>0\), so the unique maximizer is \(s_j^*=0\).
If \(Q>1\), then \(U_j'(0)>0\), whereas \(U_j'(s)\) tends to \(-\infty\) as \(s\) tends to infinity. Continuity and strict monotonicity therefore give exactly one stationary point. The utility increases before this point and decreases afterward, so it is the unique maximizer. Solving its first-order condition gives
\(e^{a_j(r+b)s}=Q\).
Hence, in both cases,
\(s_j^*=\dfrac{\max\{0,\ln Q\}}{c_j}\), and
\(\bar s^*=\max\{0,\ln Q\}\sum_{j=1}^{\tau}\dfrac{\mu_j}{c_j}\).
These utilities depend only on the investor’s own investment, so the unique maximizers form the unique type-level equilibrium. This agrees with the finite-society characterization in [Proposition 1 of the supplied source](https://research.sabanciuniv.edu/14704/1/Bankruptcy_5_10_10.pdf).
Crucially, deciding whether the equilibrium is zero requires only the exact rational comparison \(pr\leq(1-p)b\). No approximate logarithm is needed for this decision.
Lemma. Given a positive rational \(x\) of binary encoding length \(B\), and a nonnegative integer \(t\), one can compute a rational \(\ell\) satisfying \(|\ell-\ln x|\leq2^{-t}\) in time polynomial in \(B+t\).
Proof. Find the integer \(k\) for which \(y=2^{-k}x\) satisfies \(1\leq y<2\). Since the numerator and denominator of \(x\) each have at most \(B\) bits, \(|k|\leq B\). Searching this integer range using exact rational comparisons takes polynomial time, and \(y\) has encoding length \(O(B)\).
Set \(z=(y-1)/(y+1)\). Then \(0\leq z<1/3\). For an integer \(N\geq1\), define the rational polynomial
\(T_N(z)=2\sum_{i=0}^{N-1}\dfrac{z^{2i+1}}{2i+1}\).
Integrating the finite geometric identity for \(1/(1-u^2)\) gives
\(\ln\dfrac{1+z}{1-z}=T_N(z)+R_N(z)\), where
\(R_N(z)=2\int_0^z\dfrac{u^{2N}}{1-u^2}\,du\).
For \(0\leq z\leq1/3\),
\(0\leq R_N(z)\leq\dfrac{2z^{2N+1}}{(2N+1)(1-z^2)}
\leq\dfrac34\,9^{-N}\leq2^{-N}\).
Because \(y=(1+z)/(1-z)\), this approximates \(\ln y\). Applying the same construction at \(z=1/3\) approximates \(\ln2\). Therefore
\(\ell=kT_N(1/3)+T_N(z)\)
satisfies
\(|\ell-\ln x|\leq(|k|+1)2^{-N}\leq(B+1)2^{-N}\).
Choose
\(N=t+\lceil\log_2(B+1)\rceil+1\).
The resulting error is at most \(2^{-t}\).
All computations are exact rational operations. Each summand has numerator and denominator lengths \(O(NB+\log N)\). Even summing by multiplying denominators gives intermediate lengths \(O(N^2B+N\log N)\), which are polynomial in \(B+t\). There are polynomially many arithmetic operations on these polynomial-length integers. This proves the lemma. \(\square\)
Let \(P=\lceil\log_2(1/\epsilon)\rceil\). It can be computed by exact comparisons with powers of two.
Every positive input rational is at least \(2^{-L}\): its numerator is a positive integer, and its denominator has at most \(L\) bits. In particular,
\(a_j\geq2^{-L}\) and \(r\geq2^{-L}\), so
\(c_j=a_j(r+b)\geq a_jr\geq2^{-2L}\).
Compute the logarithm with precision parameter
\(t=P+2L+2\).
The lemma yields an approximation \(\ell\) with
\(|\ell-\ln Q|\leq2^{-t}
=\dfrac{2^{-P}2^{-2L}}4
\leq\dfrac{\epsilon c_j}{4}\)
for every type. Thus, whenever \(Q>1\),
\(\left|\dfrac{\ell}{c_j}-s_j^*\right|\leq\epsilon/4\).
The extra precision needed to compensate for small \(a_j\) or small \(r+b\) is therefore only linear in \(L\).
First compute \(b\), \(Q\), and every \(c_j\) exactly.
If \(Q\leq1\), output zero for every investment and for the average. These outputs are exact.
Otherwise, perform the following steps:
\(\widehat s_j=h\lfloor x_j/h\rfloor\).
\(\widehat{\bar s}=h\lfloor A/h\rfloor\).
Clipping to zero cannot increase distance from the nonnegative target \(s_j^*\). Indeed, if \(\ell/c_j<0\), then \(s_j^*\leq|s_j^*-\ell/c_j|\); otherwise clipping changes nothing. Hence \(|x_j-s_j^*|\leq\epsilon/4\).
Rounding down changes each \(x_j\) by less than \(h\), and \(h\leq\epsilon/4\). Therefore
\(|\widehat s_j-s_j^*|\leq\epsilon/4+h\leq\epsilon/2\).
For the average, positivity and normalization of the masses give
\(|A-\bar s^*|
\leq\sum_{j=1}^{\tau}\mu_j|\widehat s_j-s_j^*|
\leq(\epsilon/2)\sum_{j=1}^{\tau}\mu_j
=\epsilon/2\).
The final rounding consequently satisfies
\(|\widehat{\bar s}-\bar s^*|\leq\epsilon/2+h\leq3\epsilon/4<\epsilon\).
Thus every requested output has absolute error at most \(\epsilon\).
The rationals \(Q\) and \(c_j\) have encoding lengths \(O(L)\), because each is obtained through a constant number of rational arithmetic operations on input values. The logarithm lemma therefore runs in time polynomial in \(L+P\). Divisions, rounding, and the weighted sum require polynomially many operations in \(\tau\) on polynomial-length integers.
Large equilibrium investments do not require exponentially long outputs. To verify this, write \(p=u/v\) with integers \(0<u<v\). Then \(1-p=(v-u)/v\geq2^{-L}\); the same argument gives \(b\geq2^{-L}\). Since \(pr\leq1\),
\(Q\leq2^{2L}\).
In the positive-investment case, it follows that
\(s_j^*=\dfrac{\ln Q}{c_j}
\leq2L(\ln2)\,2^{2L}\).
Thus the integer part of each investment requires only \(O(L)\) bits. Our outputs have \(P+2\) fractional bits, so each output has length \(O(L+P)\). The average has the same magnitude bound because it is a convex combination.
This establishes a deterministic polynomial-time algorithm for the stated distributional approximation problem. Under a polynomial-time reduction that would allow this algorithm to solve an NP-hard decision problem, NP-hardness would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated problem correctly. It establishes a deterministic polynomial-time algorithm in the explicit binary rational input model. No major or minor mathematical issues were found.
The definitions \(b=1-\beta>0\), \(Q=pr/((1-p)b)>0\), and \(c_j=a_j(r+b)>0\) are valid under every permitted input.
Both derivatives are correct:
\[
U_j'(s)=a_jpr\,e^{-a_jrs}-a_j(1-p)b\,e^{a_jbs},
\]
\[
U_j''(s)=-a_j^2\left(pr^2e^{-a_jrs}+(1-p)b^2e^{a_jbs}\right)<0.
\]
Thus strict concavity and strict decrease of the derivative hold throughout the domain.
The two cases cover all inputs:
Consequently, the formulas for \(s_j^*\) and \(\bar s^*\) follow. Since utilities do not depend on others’ investments, the unique individual maximizers give the unique type-level equilibrium.
The source citation is accurate: [Proposition 1 and its proof](https://research.sabanciuniv.edu/14704/1/Bankruptcy_5_10_10.pdf) state the corresponding finite-society characterization. The submitted argument establishes the required characterization independently, so it does not rely on an unstated extension of that proposition.
The lemma covers every positive explicitly encoded rational, including values below one.
The normalization \(x=2^ky\), with \(1\leq y<2\), is valid. The bound \(|k|\leq B\), the polynomial search range, and the encoding bound for \(y\) follow from the numerator and denominator bit lengths.
The substitution \(z=(y-1)/(y+1)\) correctly places \(z\) in \([0,1/3)\). Integrating the finite geometric identity gives exactly the stated polynomial and remainder.
The remainder constants check out. At \(z\leq1/3\),
\[
\frac{2z^{2N+1}}{(2N+1)(1-z^2)}
\leq\frac{3}{4(2N+1)}9^{-N}
\leq\frac34\,9^{-N}
\leq2^{-N}.
\]
This also permits using \(z=1/3\) to approximate \(\ln2\).
For either sign of \(k\), the triangle inequality yields the stated error bound \((|k|+1)2^{-N}\). The chosen \(N\) is at least one and provides the required accuracy.
The rational arithmetic size estimates are valid. Powers have bit lengths linear in \(NB\); summing the terms by denominator multiplication still gives polynomial intermediate lengths. The lemma therefore proves polynomial bit complexity, rather than merely bounding the number of arithmetic operations.
The lower bound on positive input rationals is valid under the expressly stated numerator-and-denominator encoding. In particular,
\[
c_j\geq a_jr\geq2^{-2L}.
\]
The definition of \(P\) ensures \(2^{-P}\leq\epsilon\). Hence the specified precision satisfies
\[
2^{-t}\leq\frac{\epsilon\,2^{-2L}}4
\leq\frac{\epsilon c_j}{4}.
\]
Dividing by \(c_j\) therefore gives absolute investment error at most \(\epsilon/4\), uniformly over all types. There is no omitted dependence on the smallest risk-aversion parameter.
The branch \(Q\leq1\) produces exact outputs, using an exact rational comparison.
In the positive branch, clipping cannot increase distance from a nonnegative target. Downward dyadic rounding changes a value by less than \(h\), and \(h\leq\epsilon/4\). The resulting error bound \(\epsilon/2\) for every investment is correct.
Positivity and normalization of the masses justify the average-error estimate without any factor depending on support size. Its final rounding gives error at most \(3\epsilon/4<\epsilon\).
These guarantees also cover \(\tau=1\), arbitrarily small positive masses, and \(Q>1\) arbitrarily close to one.
The encoding lengths of \(Q\) and each \(c_j\) are \(O(L)\), as claimed. The logarithm computation uses precision \(O(L+P)\). Division and floor operations act on integers of polynomial bit length.
The exact weighted sum also remains polynomial in size: its denominators derive from the explicitly encoded masses and the common dyadic denominator. Summation cannot introduce superpolynomial encoding growth.
The output magnitude bound is correct. Explicit binary encoding gives \(1-p\geq2^{-L}\) and \(b\geq2^{-L}\), while \(pr\leq1\). Therefore
\[
Q\leq2^{2L},\qquad
s_j^*\leq2L(\ln2)\,2^{2L}.
\]
Thus large investments require only \(O(L)\) integer bits. The approximation and rounding errors do not alter this asymptotic bound. Each output has \(O(L+P)\) bits, and producing all requested outputs takes polynomial time in the stated parameters.
The final qualification concerning NP-hardness is appropriately conditional: the algorithm proves polynomial-time solvability; excluding compatible NP-hardness unconditionally would require separating \(\mathrm P\) from \(\mathrm{NP}\).
None. No additional mathematical 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.