Answer: Exact equilibrium computation is polynomial-time solvable. Every equilibrium-price binarization agrees with mass-weighted majority, including ties.
Theorem 4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIn Kelly markets, for any competence profile q, and b ∈Bq: M w(bb) = \ pKC(b), where w is such that for all i ∈N, wi ∝2qi −1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of types \(t=(q_t,y_t)\), rational masses \(\mu_t\ge 0\) summing to \(1\), and \(q_t\in\mathbb{Q}\cap(1/2,1)\), where \(b_t=q_t\) for \(y_t=A\) and \(b_t=1-q_t\) for \(y_t=B\), compute a Kelly competitive-equilibrium price \(p\) and each type’s per-capita investments \(x_t^A,x_t^B\). Require type-wise best responses under unit per-capita endowment and market clearing, \(\frac{1}{p}\sum_t\mu_t x_t^A=\frac{1}{1-p}\sum_t\mu_t x_t^B\); determine whether binarizing \(p\) agrees with majority using weights \(2q_t-1\) and masses \(\mu_t\).
A society is given by its support: a nonempty list of \(\tau\) types \(t=(q_t,y_t)\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\), \(q_t\in\mathbb Q\cap(1/2,1)\), and \(y_t\in\{A,B\}\). Set \(b_t=q_t\) when \(y_t=A\), and \(b_t=1-q_t\) otherwise. Here \(\tau\) is the support size, not the number of possible types; \(m=2\) is the number of alternatives and \(L\) is the total input bit length. State running times in \(m,\tau,L\).
At price \(p\in(0,1)\), securities for \(A\) and \(B\) cost \(p\) and \(1-p\), respectively, and pay one unit precisely in their corresponding state. Each type has unit per-capita endowment and chooses investments \(x_t^A,x_t^B\geq0\) with \(x_t^A+x_t^B\leq1\) and \(x_t^Ax_t^B=0\), retaining cash \(c_t=1-x_t^A-x_t^B\).
A type's best response maximizes \(b_t\ln(c_t+x_t^A/p)+(1-b_t)\ln(c_t+x_t^B/(1-p))\) over all these choices, including switching securities and abstaining; use \(\ln0=-\infty\). A Kelly competitive equilibrium consists of type-wise best responses at a fixed price satisfying \(p^{-1}\sum_t\mu_tx_t^A=(1-p)^{-1}\sum_t\mu_tx_t^B\). Zero aggregate investment is permitted when these conditions hold.
Binarization selects \(A\) for \(p>1/2\), \(B\) for \(p<1/2\), and \(\{A,B\}\) at equality. Mass-weighted majority compares \(\sum_{t:y_t=A}\mu_t(2q_t-1)\) with \(\sum_{t:y_t=B}\mu_t(2q_t-1)\), returning the same set-valued tie convention.
Can an exact equilibrium price and per-capita investment profile always be computed in polynomial time in \(\tau,L\), or is this computation \(\mathrm{NP}\)-hard? Does binarizing every equilibrium price always agree with mass-weighted majority?
For finite societies with equal endowments, Kelly equilibrium-price binarization equals majority with weights proportional to \(2q_i-1\). [Condorcet Markets](https://arxiv.org/pdf/2306.05028)
Finite Kelly markets with arbitrary normalized trader wealth have a wealth-weighted mean-belief equilibrium price; this result concerns finite traders rather than a distribution of unit-endowment types. [Learning Performance of Prediction Markets with Kelly Bettors](https://arxiv.org/pdf/1201.6655)
An exact equilibrium price and investment profile can always be computed in polynomial time. Every equilibrium-price binarization agrees with mass-weighted majority, including ties.
In fact, the equilibrium price and profile are unique. They are
\(\displaystyle p^\star=\sum_{t=1}^{\tau}\mu_t b_t,\qquad x_t^{A\star}=\frac{\max\{b_t-p^\star,0\}}{1-p^\star},\qquad x_t^{B\star}=\frac{\max\{p^\star-b_t,0\}}{p^\star}.\)
A conservative running-time bound is \(\displaystyle O(m\tau L^3)\) bit operations, where \(m=2\). The proof below works directly with the support and does not expand masses into individual traders.
Fix a type with belief \(b\in(0,1)\) and a price \(p\in(0,1)\). The constraint that at most one security is purchased means every feasible investment belongs to one of two branches.
Investing \(x\in[0,1)\) in security \(A\) gives utility
\(\displaystyle U_A(x)=b\ln\!\left(1+\frac{1-p}{p}x\right)+(1-b)\ln(1-x).\)
Investing \(x\in[0,1)\) in security \(B\) gives utility
\(\displaystyle U_B(x)=b\ln(1-x)+(1-b)\ln\!\left(1+\frac{p}{1-p}x\right).\)
Both branches give utility zero at \(x=0\). At \(x=1\), both give utility \(-\infty\), because both states have strictly positive subjective probability.
Differentiation gives
\(\displaystyle U_A'(x)=\frac{b-p-(1-p)x}{(p+(1-p)x)(1-x)},\qquad U_B'(x)=\frac{p-b-px}{(1-p+px)(1-x)}.\)
The denominators are strictly positive for \(x\in[0,1)\). We therefore obtain the following exhaustive cases.
Consequently, at every fixed price, the unique best response is
\(\displaystyle x^A(b,p)=\frac{\max\{b-p,0\}}{1-p},\qquad x^B(b,p)=\frac{\max\{p-b,0\}}p.\)
These investments are feasible: at most one is positive, and any positive investment is strictly less than one. This argument checks switching securities as well as abstention; the purchased security need not match the type’s signal.
For the best response just derived, the difference between the quantities of the two securities purchased by a type is
\(\displaystyle \frac{x^A(b,p)}p-\frac{x^B(b,p)}{1-p}=\frac{b-p}{p(1-p)}.\)
This identity holds in all three cases, including \(b=p\). Thus aggregate excess demand is
\(\displaystyle \frac1p\sum_t\mu_t x_t^A(p)-\frac1{1-p}\sum_t\mu_t x_t^B(p)=\frac{\sum_t\mu_t b_t-p}{p(1-p)},\)
where we used \(\sum_t\mu_t=1\).
Since \(p(1-p)>0\), market clearing holds if and only if
\(\displaystyle p=\sum_t\mu_t b_t.\)
Each belief lies strictly between zero and one. Their average under positive masses summing to one therefore also lies strictly between zero and one. Hence \(p^\star\) is an admissible price, and its best-response profile clears the market.
Conversely, every equilibrium must use the unique best responses at its price, so the same identity forces its price to equal \(p^\star\). The equilibrium profile is consequently unique as well.
Zero-investment case. Aggregate investment is zero precisely when all beliefs equal \(p^\star\). Indeed, positivity of every mass makes zero aggregate investment equivalent to every type investing zero; the best-response formulas then imply \(b_t=p^\star\) for every type. Conversely, these equalities imply abstention by every type. Thus the permitted zero-investment equilibrium is fully covered.
Write the input masses and derived beliefs as
\(\displaystyle \mu_t=\frac{a_t}{d_t},\qquad b_t=\frac{h_t}{e_t},\)
with positive integer denominators. Computing \(b_t\) from \(q_t\) requires either retaining its numerator or subtracting that numerator from its denominator.
Define integers
\(\displaystyle D=\prod_{t=1}^{\tau}d_te_t,\qquad N=\sum_{t=1}^{\tau}a_th_t\,\frac{D}{d_te_t}.\)
Every indicated division is exact, and \(p^\star=N/D\).
The sum of the bit lengths of these input denominators is \(O(L)\), so \(D\) has \(O(L)\) bits. Moreover, \(0<N<D\), because \(N/D=p^\star\in(0,1)\). Each summand and every partial sum is nonnegative and at most \(N\), so these also have \(O(L)\) bits.
For each type, compute
\(\displaystyle R_t=h_tD-e_tN.\)
The sign of \(R_t\) determines the investment:
Cash is then \(c_t^\star=1-x_t^{A\star}-x_t^{B\star}\). All output numerators and denominators have \(O(L)\) bits.
There are \(O(m\tau)\) arithmetic operations on integers of \(O(L)\) bits. Schoolbook arithmetic therefore produces exact, possibly unreduced fractions in \(O(m\tau L^2)\) bit operations. If reduced fractions are required, ordinary Euclidean reduction gives the conservative overall bound
\(\displaystyle O(m\tau L^3),\qquad m=2.\)
Thus the computation is polynomial in the support size and total binary input length.
Let the majority margin be
\(\displaystyle M=\sum_{t:y_t=A}\mu_t(2q_t-1)-\sum_{t:y_t=B}\mu_t(2q_t-1).\)
By the definition of \(b_t\), we have \(2b_t-1=2q_t-1\) for an \(A\)-signal type and \(2b_t-1=-(2q_t-1)\) for a \(B\)-signal type. Therefore,
\(\displaystyle 2p^\star-1=\sum_t\mu_t(2b_t-1)=M.\)
It follows that:
Since the equilibrium price is unique, this proves agreement for every equilibrium price.
The finite equal-endowment counterparts are Lemmas 4–5 and Theorem 4 of [Condorcet Markets](https://arxiv.org/pdf/2306.05028). The finite wealth-weighted mean-belief result appears in [Learning Performance of Prediction Markets with Kelly Bettors](https://arxiv.org/pdf/1201.6655).
The proof above independently establishes the result for the stated distribution of unit-endowment types, including zero aggregate investment, and supplies a polynomial-time algorithm for its compressed rational representation.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves both questions correctly: exact equilibrium computation is polynomial-time solvable, and every equilibrium-price binarization agrees with mass-weighted majority, including ties. No major or minor mathematical issues were found.
The task’s assumptions imply \(b_t\in(0,1)\) for every type. Thus both subjective state probabilities are strictly positive, as required by the endpoint and derivative arguments.
The two security-specific branches exhaust the feasible investment set because \(x_t^Ax_t^B=0\). Their shared point \(x=0\) represents the same abstention profile. At \(x=1\), one state has zero terminal wealth, so utility is indeed \(-\infty\). No feasible boundary choice is omitted.
Substitution of cash \(c=1-x\) into the objective gives exactly the two displayed branch utilities.
Recomputing the derivatives confirms
\(U_A'(x)=\frac{b-p-(1-p)x}{(p+(1-p)x)(1-x)}\) and
\(U_B'(x)=\frac{p-b-px}{(1-p+px)(1-x)}\).
Both denominators are positive throughout \(x\in[0,1)\).
When \(b>p\), the claimed \(A\)-branch optimizer lies in \((0,1)\): its numerator is positive, and \(b<1\) gives \(b-p<1-p\). The derivative changes from positive to negative there, proving unique branch optimality. Its utility strictly exceeds abstention because the derivative at zero is positive. The other branch is strictly decreasing, so switching securities cannot improve utility.
When \(b<p\), the symmetric reasoning applies to the \(B\)-branch optimizer \((p-b)/p\), which lies in \((0,1)\) because \(b>0\).
When \(b=p\), each branch is strictly decreasing away from zero, so abstention is the unique global best response.
Consequently, the asserted best-response formulas, feasibility, and uniqueness are all established. The reasoning checks global choice across both securities rather than merely a first-order condition within one branch.
The type-wise quantity difference
\(\frac{x^A(b,p)}p-\frac{x^B(b,p)}{1-p}=\frac{b-p}{p(1-p)}\)
is correct for each of the three belief-price cases.
Summing with masses and using their normalization gives the stated aggregate excess-demand formula. Since \(p(1-p)>0\), clearing is equivalent to \(p=\sum_t\mu_tb_t\).
Positive masses and interior beliefs ensure that this weighted average is an admissible interior price. Its best-response profile therefore gives existence. Conversely, uniqueness of best responses and the clearing identity force every equilibrium to have that price and profile.
The zero-investment discussion is also correct: nonnegative investments and strictly positive masses make zero aggregate investment equivalent to abstention by every type. The formulas identify this precisely with all beliefs equaling the equilibrium price. This includes a singleton support.
The common-denominator construction is valid without requiring reduced input fractions. Each \(d_te_t\) divides \(D\), so every indicated division is exact, and \(N/D\) is the required weighted mean.
The denominator product has \(O(L)\) bits because its logarithm is bounded by the total encoded denominator length. Positivity and \(0<N<D\) bound every summand and partial sum by \(D\). The other intermediate products likewise involve integers of \(O(L)\) bits.
The sign test using \(R_t=h_tD-e_tN\) correctly determines whether \(b_t\) exceeds the price. Substitution into the best-response expressions confirms both output-fraction formulas. Their denominators are positive because \(0<N<D\), and all output components have \(O(L)\) bits.
There are \(O(m\tau)\) arithmetic operations, with \(m=2\). Schoolbook multiplication and division support the stated \(O(m\tau L^2)\) bound for unreduced output. The \(O(m\tau L^3)\) bound including ordinary Euclidean reduction is conservative and valid. No expansion into individual traders is needed.
The signal-dependent identities for \(2b_t-1\) are correct. Mass normalization then gives exactly \(2p^\star-1=M\).
Therefore positive, negative, and zero majority margins correspond respectively to prices above, below, and equal to \(1/2\). Both rules use the same tie convention. Price uniqueness justifies the quantifier “every equilibrium price.”
The cited finite-market statements are present in [Condorcet Markets](https://arxiv.org/pdf/2306.05028) and [Learning Performance of Prediction Markets with Kelly Bettors](https://arxiv.org/pdf/1201.6655). They serve as contextual comparisons; the submitted argument independently proves the required result for the specified support representation. There is no unverified theorem application on which its conclusion depends.
Required clarification or repair: none.
⟨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.