Answer: \(\mathrm{NP}\text{-hard}\)
CLAIM 2 — class: hardness
Given a fixed event hierarchy, a finite support of trader-portfolio types with rational masses μ_t summing to one, rational per-capita liquidity β, and two legal queried securities E_1 and E_2, determine which has the higher LMSR quote, where q_μ(ω)=∑_t μ_t h_t(ω) and p_μ(E)=∑_{ω∈E} exp(q_μ(ω)/β) / ∑_{ω∈Ω} exp(q_μ(ω)/β).
Let \(T\) be an explicitly given rooted tree with \(m\geq1\) labeled leaves, fixed throughout trading, and let \(N\geq1\) be an integer. The outcome space is \(\Omega=\{0,\ldots,N\}^{m}\); each node \(v\) determines the nonempty set \(S_v\) of its descendant leaves.
A legal sum-with-varying-weights (SVW) security is the event \(a\leq\sum_{i\in S_v}c_i x_i\leq d\), where \(a,d\) are nonnegative integers with \(a\leq d\), and every \(c_i\) is a positive integer chosen separately for that security. Either bound may be omitted; equality securities are allowed. A share pays one on the event and zero otherwise.
A society is given by its support: the list of the \(\tau\) trader-portfolio types with positive binary-rational masses \(\mu_t\), summing to one. Here \(\tau\) is the support size, not the number of possible types. Type \(t\) explicitly lists legal securities \(F_{tj}\) and signed rational share quantities \(s_{tj}\), with negative quantities representing short positions; its payoff is \(h_t(\omega)=\sum_j s_{tj}\mathbf{1}_{F_{tj}}(\omega)\).
Starting from zero outstanding shares, define \(q_\mu(\omega)=\sum_t\mu_t h_t(\omega)\). For positive rational per-capita liquidity \(\beta\), the LMSR quote is \(p_\mu(E)=\frac{\sum_{\omega\in E}\exp(q_\mu(\omega)/\beta)}{\sum_{\omega\in\Omega}\exp(q_\mu(\omega)/\beta)}\).
Given two legal securities \(E_1,E_2\), compare their quotes exactly, reporting either strict ordering or equality. All numerical inputs are binary encoded. State running times in \(m,\tau,L,N,|T|,K\), where \(L\) is the total input bit length and \(K\) is the total number of listed portfolio positions; polynomial time means polynomial in the encoded input size.
Is this exact LMSR quote-comparison problem for a society given by rational masses in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Discrete SVW LMSR pricing is reported to be \(\mathrm{NP}\)-hard for any event hierarchy; the hardness argument compares two legal securities. [Guo–Pennock](https://cs.adelaide.edu.au/~mingyu/publication/aamas2009.pdf). No result specifically settling the rational-mass formulation above was located.
The exact quote-comparison problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even when \(\tau=1\), \(K=1\), \(N=1\), and \(\beta=1\), with an integer share quantity and two nonempty comparison events. The reduction produces strictly opposite orderings in its yes and no cases.
Hardness concerns instances with growing \(m\). The construction works with any rooted-tree shape on the required labeled leaves.
Use the standard \(\mathrm{NP}\)-complete problem positive SUBSET SUM: given positive integers \(w_1,\ldots,w_n\) and a positive integer \(B\), all binary encoded, decide whether some subset sums to \(B\). Assume \(n\geq1\).
Construct a tree with \(m=n+1\) leaves, labeled by coordinates \(x_1,\ldots,x_n,y\), and set \(N=1\). Thus
\(\Omega=\{0,1\}^{n+1}\).
A star suffices, although only the root and the leaf labeled \(y\) will be used.
The society has one type, with mass \(\mu_1=1\). Its portfolio consists of one long share of the leaf security
\(F=\{y=0\}\).
This is legal: its coefficient is \(1\), and both bounds are \(0\). Set \(\beta=1\). Starting from zero outstanding shares, the resulting aggregate payoff is
\(q_\mu(x_1,\ldots,x_n,y)=\mathbf{1}_{\{y=0\}}\).
Ask to compare the two root securities
\(E_1=\left\{\sum_{i=1}^{n}w_i x_i+B y=B\right\}\)
and
\(E_2=\left\{\sum_{i=1}^{n}w_i x_i+B y=0\right\}\).
Both are legal equality securities: every root coefficient is a positive integer, and their bounds are nonnegative integers.
Both events are nonempty. The outcome \((0,\ldots,0,1)\) belongs to \(E_1\), while \((0,\ldots,0,0)\) belongs to \(E_2\). Since \(B>0\), they are disjoint.
Define the number of SUBSET SUM witnesses by
\(s=\left|\left\{x\in\{0,1\}^{n}:\sum_{i=1}^{n}w_i x_i=B\right\}\right|\).
There are two cases for outcomes in \(E_1\).
Consequently,
\(\sum_{\omega\in E_1}\exp(q_\mu(\omega)/\beta)=se+1\).
Similarly, positivity of every coefficient implies that \(E_2\) consists only of the all-zero outcome. That outcome has \(y=0\), so
\(\sum_{\omega\in E_2}\exp(q_\mu(\omega)/\beta)=e\).
For each fixed \(y\), there are \(2^n\) choices of \(x\). Therefore the common, positive denominator is
\(Z=\sum_{\omega\in\Omega}\exp(q_\mu(\omega)/\beta)=2^n(e+1)\).
It follows exactly that
\(p_\mu(E_1)-p_\mu(E_2)=\dfrac{1+(s-1)e}{2^n(e+1)}\).
If the SUBSET SUM instance is a no-instance, then \(s=0\), and the numerator is \(1-e<0\).
If it is a yes-instance, then \(s\geq1\), and the numerator is at least \(1>0\).
Thus
\(\text{SUBSET SUM is satisfiable}\quad\Longleftrightarrow\quad p_\mu(E_1)>p_\mu(E_2)\).
No constructed instance has equal quotes. Hence the decision problem asking whether \(p_\mu(E_1)>p_\mu(E_2)\) is \(\mathrm{NP}\)-hard, and the requested three-way comparison is at least as hard.
Let \(\ell\) be the source SUBSET SUM input bit length. For a star, the constructed parameters satisfy
\(m=n+1,\qquad |T|=m+1,\qquad \tau=K=N=1\).
The only potentially large numerical values are the copied integers \(w_i\) and \(B\). The output bit length satisfies
\(L=O\!\left(\ell+n\log(n+1)\right)\).
The reduction can be written in \(O\!\left(\ell+n\log(n+1)\right)\) bit operations: it copies the input integers and writes the tree, labels, constant-size society, and two coefficient lists.
A comparator running in time polynomial in the encoded input size would therefore solve SUBSET SUM in polynomial time. Indeed, even a running-time bound polynomial in all six parameters \(m,\tau,L,N,|T|,K\) would imply \(\mathrm{P}=\mathrm{NP}\), because \(N,\tau,K\) are constant in this reduction.
More generally, any society in the question can be replaced by a single type of mass \(1\). Retain every listed security \(F_{tj}\), and replace its quantity by the rational number
\(r_{tj}=\mu_t s_{tj}\).
The resulting payoff is exactly
\(\sum_{t,j}r_{tj}\mathbf{1}_{F_{tj}}=\sum_t\mu_t h_t=q_\mu\),
so every quote is preserved. Products of binary-encoded rationals have polynomial encoding length; retaining duplicate positions avoids any need to combine denominators. Using ordinary integer multiplication, this transformation takes \(O(KL^2+L)\) bit operations.
[Guo–Pennock’s Claim 2](https://cs.adelaide.edu.au/~mingyu/publication/aamas2009.pdf) also reduces SUBSET SUM using root and leaf securities. The explicit reduction above settles the stated rational-mass formulation using only integer quantities.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes \(\mathrm{NP}\)-hardness of exact quote comparison even with \(\tau=K=N=1\), \(\beta=1\), and one integer share. No major or minor issues were found.
The stated positive SUBSET SUM problem is the standard \(\mathrm{NP}\)-complete decision problem with binary-encoded positive integers. The restrictions \(n\geq1\) and \(B>0\) are compatible with that problem. Positivity is used explicitly and correctly throughout the reduction.
The constructed tree has \(m=n+1\) labeled leaves and \(N=1\), giving exactly \(\Omega=\{0,1\}^{n+1}\). A star is a valid explicitly represented rooted tree. The assertion about arbitrary tree shapes is justified: the construction uses only the root, whose descendant set contains every leaf, and the leaf labeled \(y\).
Growing \(m\) across reduction instances is consistent with the task: the tree is fixed throughout trading within each instance.
The single mass \(\mu_1=1\) is positive, binary rational, and sums to one. The security \(F=\{y=0\}\) uses the leaf node, coefficient \(1\), and bounds \(a=d=0\), so it is legal. One long share and \(\beta=1\) give exactly
\[
q_\mu(x,y)=\mathbf{1}_{\{y=0\}}.
\]
Thus \(\tau=K=1\), as claimed.
Both events use the root and assign positive integer coefficients to every leaf: \(w_i\) to \(x_i\) and \(B\) to \(y\). Their equality bounds are nonnegative integers.
The stated witnesses establish nonemptiness. The events are disjoint because their defining weighted sum would otherwise have to equal both \(B\) and \(0\), contrary to \(B>0\).
For \(y=0\), membership is precisely the source subset-sum condition. Therefore there are exactly \(s\) outcomes, each with exponential weight \(e\).
For \(y=1\), membership requires \(\sum_i w_i x_i=0\). Since all \(w_i>0\) and all \(x_i\geq0\), every \(x_i\) must be zero. This gives exactly one outcome with weight \(1\). Hence the numerator \(se+1\) is correct.
All coefficients are positive and all coordinates are nonnegative, so \(E_2\) contains only the all-zero outcome. Its weight is \(e\).
Each fixed value of \(y\) allows \(2^n\) assignments to \(x\). Consequently,
\[
Z=2^n e+2^n=2^n(e+1)>0.
\]
The resulting difference
\[
p_\mu(E_1)-p_\mu(E_2)
=\frac{1+(s-1)e}{2^n(e+1)}
\]
is algebraically correct.
In a no-instance, \(s=0\), so the numerator is \(1-e<0\). In a yes-instance, \(s\geq1\), so the numerator is at least \(1>0\). These cases exhaust all possibilities, and equality never occurs.
Thus the constructed instance satisfies
\[
p_\mu(E_1)>p_\mu(E_2)
\quad\Longleftrightarrow\quad
\text{the SUBSET SUM instance is a yes-instance}.
\]
This is a polynomial-time many-one reduction to the strict-comparison decision problem. A three-way comparator immediately decides that problem, establishing the requested hardness. No computation or finite encoding of \(e\) is required by the reduction.
The star has \(|T|=m+1\). The numerical coefficients are copied a constant number of times, while tree references and labels require \(O(n\log(n+1))\) bits under a standard explicit encoding. The stated bound
\[
L=O\bigl(\ell+n\log(n+1)\bigr)
\]
and corresponding construction time are justified.
Since \(n\leq\ell\), the reduction is polynomial in the source encoding length. Moreover, \(N,\tau,K\) remain constant, while \(m,L,|T|\) are polynomially bounded. The claimed consequence for an algorithm polynomial in all six parameters is therefore correct.
Replacing each listed quantity \(s_{tj}\) by \(\mu_t s_{tj}\) preserves the aggregate payoff exactly. Signed rational quantities are permitted, and retaining duplicate positions is compatible with the explicit portfolio-list formulation.
Each rational product has polynomial encoding length. Ordinary multiplication of its numerator and denominator takes \(O(L^2)\) bit operations per position, so \(O(KL^2+L)\) is a valid upper bound. This observation is correct, although the hardness reduction already uses mass \(1\).
The ancillary description of Guo–Pennock’s Claim 2 is accurate: its proof uses root and leaf securities and compares two root securities through a positive subset-sum instance. The submitted reduction is independently complete and does not depend on transferring that paper’s numerical assumptions. [Guo–Pennock, Claim 2](https://cs.adelaide.edu.au/~mingyu/publication/aamas2009.pdf)
None. No additional clarification, lemma, or computation is needed. The proof establishes hardness; it does not claim membership in \(\mathrm{NP}\) or an unconditional separation from \(\mathrm{P}\).
⟨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.