| paper | d4-conf-sigecom-2009-0001 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 3.5
statement extracted from the paper’s text layer
Given \(N\) outcomes, an SCPM cost function \(C\), and \(\tau\) trader types with rational masses \(\mu_t\) summing to \(1\), each type \(t\) has a standardized claim bundle \(\mathbf{a}_t\in\{0,1\}^N\) and per-capita quantity limit \(\ell_t\). Assuming prices do not bind, compute the worst-case per-capita loss and an attaining allocation by maximizing \(q_i-C(\mathbf{q})+C(\mathbf{0})\) over outcomes \(i\) and quantities \(0\le x_t\le\mu_t\ell_t\), where \(\mathbf{q}=\sum_t x_t\mathbf{a}_t\).
A society is a distribution over complete order-template types: each type specifies its claim bundle and per-capita quantity cap. The decision variables \(x_t\) are accepted quantities from each type, constrained by its population mass; the objective is worst-case state payout minus the SCPM cost, with quantities and loss measured per population unit.
The mirror’s practical value depends on whether standardized trader cohorts genuinely constrain reachable portfolios; the proposed scenario makes this plausible but does not establish that such limits matter in an application.
fatal: False
The mirror covers Corollary 3.5 and its supporting loss formula in Theorem 3.4, including the boundedness criterion for \(u(\mathbf{s})-s_i\). It leaves the paper’s results on truthfulness, proper scoring, and mechanism unification aside.
My strongest mirror is a population-constrained worst-case-loss problem for the SCPM market maker. Its anchor is Corollary 3.5, proved in this paper: computing the SCPM’s worst-case loss bound is a convex optimization problem, and the loss is bounded if and only if \(u(\mathbf{s})-s_i\) is bounded above. The formula it builds on, from Theorem 3.4 (also proved here), is \(B+C(\mathbf{0})\), where
\[
B=\max_i\max_{\mathbf{s}}\bigl(u(\mathbf{s})-s_i\bigr),
\qquad
C(\mathbf{q})=\min_z\bigl(z-u(z\mathbf{e}-\mathbf{q})\bigr).
\]
The theorem assumes the market starts with no shares. Its loss calculation compares the payout \(q_i\) in outcome \(i\) with the money collected, \(C(\mathbf{q})-C(\mathbf{0})\). These are convex-optimization results, not a bit-complexity theorem for arbitrary representations of \(u\).
Here is the continuous problem I would hand to a prover. Call it Type-Population SCPM Worst-Case Loss. An instance has \(N\) exhaustive outcomes, a concave organizer utility \(u:\mathbb{R}^N\to\mathbb{R}\) with cost function \(C\) as above, and a finite set \(T\) of trader types. Type \(t\) has rational population mass \(\mu_t\), with \(\sum_t\mu_t=1\), and a standard SCPM order: a claim bundle \(\mathbf{a}_t\in\{0,1\}^N\) and per-capita quantity limit \(\ell_t\). Assume the limit prices are nonbinding, so any quantity within those limits can be filled. The decision variable \(x_t\) is the aggregate quantity accepted from type \(t\), with \(0\le x_t\le\mu_t\ell_t\). For \(\mathbf{q}=\sum_t x_t\mathbf{a}_t\), compute
\[
W(\mu)=
\max_{\substack{i\in\{1,\ldots,N\}\\0\le x_t\le\mu_t\ell_t}}
\left[q_i-C(\mathbf{q})+C(\mathbf{0})\right].
\]
A solution gives the worst-case outcome, the accepted quantity from each type, and the loss. Equivalently, using the cost-function definition, this is a finite family of concave maximizations over \(x\) and \(z\). Under an efficient convex-optimization oracle for \(u\) (or an explicit cost function such as LMSR’s), I expect this to be tractable. The paper’s own formula is recovered when the available portfolios range over all \(\mathbf{q}\ge0\).
The regime is a large prediction market in which many traders use a modest menu of standardized claim bundles and quantity limits—for example, recurring retail or automated-trader cohorts placing similar orders. A type records the whole relevant order template, so its members are interchangeable for this calculation. The number of traders can be very large while the number \(\tau=|T|\) of distinct templates stays modest. Mass is the fraction of the trader population, and quantities and losses are measured per unit of that population.
I think the authors could recognize this as their problem: it asks for the same market maker’s worst-case loss, with the same state-contingent payouts and the same path-independent cost function. The population distribution specifies which aggregate portfolios the market can face. This mirror covers the worst-case-loss result, not the paper’s broader results on truthfulness, proper scoring, or mechanism unification.
The soft spot is that Theorem 3.4 already aggregates traders into a share vector \(\mathbf{q}\) and optimizes over all such vectors. The proposed mirror restricts that portfolio space using a type population; it may be viewed as a useful demand-regime version of the paper’s analysis rather than a new complexity question created by continuization. Also, Corollary 3.5 does not establish polynomial bit complexity for every possible \(u\). Those limits make the case modest, but the population model is still a concrete, recognizable extension of the paper’s own computation.
The strongest anchor to resist is Theorem 3.4 and Corollary 3.5. Their worst-case loss is a guarantee over every aggregate portfolio \(\mathbf q\ge 0\) the market can accumulate, with loss \(q_i-C(\mathbf q)+C(\mathbf 0)\). It does not depend on who submits the orders or how many traders submit them. A fixed population of order types therefore changes the adversary: it asks for loss conditional on a chosen demand menu and capacity, rather than the mechanism’s worst-case loss guarantee.
The proposed model is coherent as a constrained exposure calculation, but its nonbinding-price assumption removes the SCPM’s order-acceptance rule. If prices bind, masses and total quantity limits alone do not determine which portfolios are reachable: acceptance depends on the current market state and on order sequence. To model that faithfully, types would need to include contingent strategies over market histories. A finite menu of such strategies can be studied, but the menu then supplies the key restriction; allowing all strategies to recover the theorem’s universal guarantee leaves the population unable to constrain the set of portfolios. This is a modeling fork, not an objection that the continuous answer might be easy.
The best repair is a closed market with many traders using a small set of standardized, bounded order policies. That gives a sensible high-multiplicity regime, and scaling the mechanism with population size can preserve a meaningful per-capita limit. But the resulting question is a population-specific stress test, not a direct continuization of the paper’s general loss result. Its value depends on whether those demand restrictions matter in an application.
I cannot honestly rule out that closed-market version: it is plausible and the authors might recognize it as their problem. So the negative case is weakest precisely at the anchor raised. It narrows the mirror’s generality and relevance; it does not establish that no worthwhile continuous mirror exists.
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.