| paper | d4-conf-atal-2009-0170 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
CLAIM 2
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_μ(ω)/β).
A society is a distribution μ over forecaster types, each type specifying a complete portfolio of allowed securities and its resulting share position h_t(ω) on every outcome. The per-capita aggregate position is q_μ(ω)=∑_t μ_t h_t(ω), and quotes use per-capita liquidity β. For a discrete market with H traders and liquidity b=Hβ, this gives the paper’s same quote.
The paper’s pricing input is already the aggregate share vector, so portfolio-type masses may be only an alternate encoding of that state rather than a computational role for trader multiplicity.
fatal: False
The mirror covers the SAS and SVW pricing hardness results, CLAIM 1 and CLAIM 2. It leaves the SPW pricing algorithm, the prototype, and the discussion of other event operators outside its scope.
A presentational wrinkle: the paper’s two named complexity results are printed as CLAIM 1 and CLAIM 2, not as theorems, propositions, or corollaries. I use the labels as printed.
The strongest mirror is a high-multiplicity version of the paper’s SVW pricing problem. Consider a large prediction market on page views across a hierarchy of web subdomains. Its agents are forecasters, and a type is a complete description of one forecaster’s current portfolio: which allowed securities they hold and in what quantities. The mass \(\mu_t\) of type \(t\) is the fraction of forecasters with that portfolio. This regime is plausible when a platform uses standardized securities and stake sizes, so many participants arrive at the same portfolio; the number of participants \(H\) can then be much larger than the number of portfolio types \(\tau\).
Here is the continuous problem. The outcome space remains discrete, \(\Omega=\{0,\ldots,K\}^n\), with securities defined by the paper’s SVW language on a fixed event hierarchy. An instance gives the hierarchy, a finite support of portfolio types with binary rational masses summing to one, and a positive rational per-capita liquidity \(\beta\). If \(h_t(\omega)\) is the outstanding share position on outcome \(\omega\) contributed by one agent of type \(t\), the per-capita aggregate position is
\[
q_\mu(\omega)=\sum_t\mu_t h_t(\omega).
\]
For a queried legal security covering the event \(E\subseteq\Omega\), the solution is its exact LMSR quote,
\[
p_\mu(E)=
\frac{\sum_{\omega\in E}\exp(q_\mu(\omega)/\beta)}
{\sum_{\omega\in\Omega}\exp(q_\mu(\omega)/\beta)}.
\]
Equivalently, the associated decision question can ask which of two queried securities has the higher price. This continuizes the population of traders; the outcomes and securities remain discrete. It also matches the paper’s pricing semantics exactly: with \(H\) agents, \(\mu_t=H_t/H\), and market liquidity \(b=H\beta\), the paper’s \(q_\omega/b\) equals \(q_\mu(\omega)/\beta\).
The lead anchor is CLAIM 2, proved in this paper. It states that LMSR pricing for SVW is NP-hard for *any* event hierarchy. The reduction uses bets on the leaves and root, so the result does not depend on a specially chosen tree; varying positive weights in the bets encode Subset Sum. In the continuous problem, repeated forecasters holding each of the reduction’s portfolios become masses of those portfolio types. Choosing their rational masses and per-capita liquidity to reproduce the discrete share counts preserves every quote in the reduction. Thus the mirror is expected to be Class B: hardness transfers. The combinatorics live in the weights and event coordinates, not in how many copies of each trader type there are.
A second anchor is CLAIM 1, also proved in this paper. It states that LMSR pricing for SAS is NP-hard even when the securities use only unit weights. Its proof reduces 3-SAT to pricing: the constructed objective security has price greater than \(1/2\) if and only if the formula is satisfiable. The corresponding continuous problem is the same mass-based quote problem, with SAS securities allowed to query arbitrary subsets. For the hardness decision version, the question is whether the queried security’s price exceeds \(1/2\). The discrete reduction embeds by representing each repeated outstanding portfolio as a type mass, so this mirror is also expected to be Class B. Its strength is that the hardness does not require agents to choose unusual weights; unrestricted subsets alone suffice.
These are two distinct anchors for two of the paper’s betting languages, not a claim to mirror the whole paper. In particular, this case does not cover the paper’s SPW algorithm, its prototype, or its discussion of other event operators.
The weakest point is that the paper’s quote depends only on aggregate outstanding shares \(q\), not on the identities or number of traders. The continuous population is therefore a principled high-multiplicity representation of a market state, but it may look to the authors like a refactoring of an input they already regard as canonical. And some real markets may have nearly one portfolio type per participant. The case survives because standardized, repeated portfolio types are a plausible market regime and, in that regime, the mass model preserves the paper’s exact pricing question rather than simplifying it. Whether hardness persists with bounded support size \(\tau\), or whether useful approximate pricing becomes tractable for common portfolio patterns, would be natural next questions.
The best objection is that Claim 1 and Claim 2 are genuine computational results, but the proposed mirrors put the population axis in the wrong place. LMSR pricing takes the aggregate market state as input: the outstanding-share vector \(q\). It does not take a list of traders.
For portfolio types \(t\), the proposed model first computes \(q_\mu(\omega)=\sum_t\mu_t h_t(\omega)\), then prices from \(q_\mu/\beta\). The quote depends only on that normalized aggregate vector. Any two societies with the same \(q_\mu/\beta\) are indistinguishable to the pricing problem, whatever their populations or portfolio-type distributions. The mass representation is therefore a factorization of the market state, not a continuous society on which the result computationally depends.
That applies to both anchors. Claim 2’s reduction encodes Subset Sum through the event weights and the outstanding securities; Claim 1’s encodes satisfiability through the securities and their share counts. Replacing repeated positions with cohort masses can preserve the quotes exactly, as the proponent says. But this establishes that the same aggregate pricing instance can be described with masses; it does not make trader multiplicity part of either pricing problem. The reduction’s structure remains in the securities and outcome coordinates.
The strongest alternative mirror—standardized cohorts of forecasters with common portfolios and per-capita liquidity—has the same limitation. Scaling liquidity with cohort size keeps quotes informative, but then the population size cancels into \(q_\mu/\beta\). Keeping liquidity fixed as cohorts grow instead makes the quotes concentrate on outcomes maximizing average holdings. Either way, population multiplicity supplies no independent computational structure. Adding beliefs or other individual attributes does not help: if pricing uses them only through the resulting holdings, they disappear into \(q\); if they determine trading behavior, the question becomes about a different problem than Claims 1 and 2.
I would not call the negative case airtight. Repeated forecaster portfolios are plausible, and authors could recognize cohort-based market states as a useful input model. But any gain from bounded portfolio support or approximate pricing would appear to come from restrictions on the aggregate LMSR state, rather than from continuizing the population. That is the strongest reason to doubt these anchors are worthwhile continuous mirrors.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.