d4-conf-sigecom-2008-0010

A credible, narrow mirror is to make the traders the continuous population. In a large prediction market, many small traders can follow a modest number \(\tau\) of standardized strategies: the market might have millions of participants but only dozens of distinct order profiles. A type is a complete per-capita portfolio over the securities the market permits, including the relevant belief and trading parameters. Its mass \(\mu_t\) is its fraction of the population. The LMSR market state is then the mass aggregate \(Q_e=\sum_{t=1}^{\tau}\mu_t h_t(e)\), where \(h_t(e)\) is type \(t\)’s position in security \(e\).

For outcome \(\omega\), let \(w_\omega=\exp\!\left(\frac{1}{b}\sum_{e:\,\omega\models e}Q_e\right)\), and let \(Z=\sum_{\omega\in\Omega}w_\omega\). The mirror asks for the exact LMSR quote \(p_S=\sum_{\omega\in S}w_\omega/Z\) for a permitted security \(S\), and the exact cost \(C=b\log Z\). Use exact log-weight inputs, as in the paper’s reductions, and return exact prices and normalizers. A transaction-payment version takes two such societies and returns \(b\log Z(Q')-b\log Z(Q)\).

The lead is Mass-Subset LMSR Pricing. Its instance gives \(n\) candidates, a finite rational-mass society of trader portfolio types, and a designated security \(\langle i\mid j\rangle\), paying when candidate \(i\) finishes in position \(j\). Outcomes are rankings \(\sigma\in S_n\), with \(w_\sigma=\exp\!\left(\frac{1}{b}\sum_i Q_{i,\sigma(i)}\right)\). The question is to compute that security’s quote and the market normalizer \(Z\), hence the cost. Theorem 1 says that exact instantaneous prices and the cost function are each \(\#P\)-hard for LMSR subset betting. The authors prove this here by reducing from the permanent of a \(0\)-\(1\) matrix; the permanent’s hardness is prior work. ([Chen et al., Theorem 1](https://ai.stanford.edu/~nlambert/papers/Chen_et_al_%28EC_2008%29.pdf))

Mass-Pair LMSR Pricing uses the same society input, but types submit positions on pair securities \(\langle i>j\rangle\). Its outcomes are again rankings, with \(w_\sigma=\exp\!\left(\frac{1}{b}\sum_{i,j:\,\sigma(i)<\sigma(j)}Q_{i,j}\right)\). Given a pair query, compute its exact quote and \(Z\). Theorem 3 proves here that exact prices and cost are \(\#P\)-hard, by a reduction from counting the linear extensions of a partial order. The counting problem’s hardness is cited from prior work. ([Chen et al., Theorem 3](https://ai.stanford.edu/~nlambert/papers/Chen_et_al_%28EC_2008%29.pdf))

Mass-2-Clause Boolean LMSR Pricing gives types portfolios over securities for disjunctions of two literals, such as \(X_i\lor X_j\), where literals may be events or their negations. Its outcomes are assignments \(x\in\{0,1\}^N\), with \(w_x=\exp\!\left(\frac{1}{b}\sum_{e:\,x\models e}Q_e\right)\). Given a permitted clause query, compute its exact quote and \(Z\). Theorem 5 proves here that exact prices and cost are \(\#P\)-hard, by reducing from counting satisfying assignments to a \(2\)-CNF formula. ([Chen et al., Theorem 5](https://ai.stanford.edu/~nlambert/papers/Chen_et_al_%28EC_2008%29.pdf))

All three mirrors have the same honest classification: Class B, hardness transfers. Any paper instance with aggregate position vector \(Q\) embeds as a society with one type of mass one and portfolio \(Q\). Thus the hardness persists even at support size \(\tau=1\); it comes from the combinatorics of rankings or Boolean outcomes, not from the number of distinct trader types. The quoted theorems are proved in this paper, while the source counting problems’ hardness is cited. Each mirror also raises a useful next question: which structure in the aggregate position matrix, pair interactions, or clause–event incidence allows exact or approximate pricing despite the general hardness? The paper’s transaction-payment corollaries can be mirrored by the two-society cost-difference query above.

The authors should recognize these as their problems: the outcome spaces, allowed securities, market states, and LMSR pricing rule stay intact; the mass distribution specifies where the aggregate holdings come from. The weakest point is that the paper already represents the market by aggregate outstanding shares \(Q\), so the type distribution adds a population interpretation rather than changing the pricing computation. That makes this a narrow high-multiplicity lift, not a claim that continuization resolves the hardness or that the population itself creates it.