| paper | d4-conf-sigecom-2010-0043 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial bit-time solvable. For \(K=\log(1/\mu_{\min})\), the computed weights satisfy \(\widehat R_H\leq\min\{H,K/\eta+\eta H/8+H\delta/2\}\). Tuning before play gives \(\sqrt{HK/2}+H\delta/2\), with arbitrarily small additional slack for a binary-rational learning rate. For \(\tau=1\), regret is zero. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite support of forecaster types with rational masses \(\mu_a>0\), horizon \(H\), and losses \(\ell_{a,t}\in[0,1]\) revealed each round, compute online weights using the weighted-LMSR update \(w_{a,t}\propto\mu_a\exp(-\eta\sum_{s<t}\ell_{a,s})\). What running time and regret guarantee against the best supported type can be achieved as functions of support size, input bit length, and requested precision?
A society of repeated forecasting services, where each type \(a\) has mass \(\mu_a\) and identical advice and losses. The weighted cost function \(C_\mu(q)=b\log\sum_a\mu_a e^{q_a/b}\) gives prices \(p_a(q)\propto\mu_a e^{q_a/b}\); with \(q=-\epsilon L\), these are the learner's type weights. For weighted LMSR, the update is explicit over the support and Theorem 4 yields regret at most \(2\sqrt{H\log(1/\mu_{\min})}\).
Theorem 4 does not bound the runtime for a general cost function, and multiplicity here mainly determines the prior rather than creating a harder computational problem.
fatal: False
The mirror covers Theorem 4's expert-learning guarantee for type-aggregated forecasters, including its weighted-LMSR instance; it leaves the paper's market-scoring-rule equivalence and its treatment of trading over event outcomes aside.
The best defensible mirror is a high-multiplicity version of the paper’s expert-learning problem. Treat the experts as a large cohort of forecasters or forecasting services. A type is a complete advice-and-loss behavior: experts of the same type give the same advice and incur the same loss whenever the learner observes the same history. If \(n_a\) of \(n\) experts have type \(a\), their mass is \(\mu_a=n_a/n\). A realistic regime is a large ensemble with many repeated instances of a small menu of forecasting pipelines, so \(n\) is large while the support size \(\tau\) is moderate.
The question is High-Multiplicity Type-Weighted FTRL. Its input is the rational type distribution \(\mu\), a horizon \(H\), losses \(\ell_{a,t}\in[0,1]\) revealed one round at a time, and a convex cost function \(C\) over the \(\tau\) types. Require \(C\) to have valid, \(\phi\)-stable prices \(p=\nabla C\), initial prices \(p(0)=\mu\), and a known bound \(B\) on market-maker loss. At round \(t\), the learner chooses a distribution \(w_t\in\Delta_\tau\) using only past losses; its loss is \(\sum_a w_{a,t}\ell_{a,t}\). The task is to compute the online distributions with regret at most \(\sqrt{2B\phi H}\) against the best supported type. A solution is an online update algorithm and its guarantee, with running time measured in \(\tau,H\), input bit length, and requested precision.
My lead anchor is Theorem 4, proved in this paper. It says: for any valid convex cost function \(C\) with \(\phi\)-stable prices, let \(\alpha_C\) be its penalty function. The expert-learning algorithm whose weights are \(p(-\epsilon L_{t-1})\), with
\[
\epsilon=\sqrt{\frac{2\sup_{p,p'\in\Delta_N}(\alpha_C(p)-\alpha_C(p'))}{\phi T}},
\]
has, for every sequence of losses in \([0,1]\), regret at most
\[
\sqrt{2T\phi\sup_{p,p'\in\Delta_N}(\alpha_C(p)-\alpha_C(p'))}.
\]
This is an algorithmic performance result, not a polynomial-time or hardness classification. The paper provides no comparable hardness anchor, and I would not claim one.
The mirror has a particularly clean discrete-to-continuous dictionary. For weighted LMSR, set
\[
C_\mu(q)=b\log\!\left(\sum_a\mu_a e^{q_a/b}\right).
\]
Its prices are the exponentially weighted type masses. Grouping \(n_a\) identical experts in the ordinary \(n\)-expert market gives exactly these aggregate prices; this is an identity, not a limiting approximation. The associated penalty is \(b\sum_a w_a\log(w_a/\mu_a)\). Here the update is an explicit \(\tau\)-term softmax, and Theorem 4 gives regret at most \(2\sqrt{H\log(1/\mu_{\min})}\). Thus the weighted-LMSR instance is tractable in the support size, while the broader family asks which cost functions admit efficient pricing or regularized optimization. That pricing question is where a general complexity landscape could arise.
The paper’s authors have a plausible reason to recognize this as their problem: they explicitly identify market prices with weights over experts and connect convex markets to FTRL. The mirror keeps the same online losses, market updates, and best-expert benchmark; it compresses repeated experts into population mass. It covers the market-to-learner and convex-market portion of the paper, not its full account of forecasters trading over event outcomes. It also generates concrete follow-ups: which market families permit efficient price computation over a support of size \(\tau\), and how robust the update is when many nominally identical forecasters have small behavioral differences?
The weakest point is that this is a border case for ChoCo. Experts in the paper are advice sources over which an algorithm distributes weight; they are not voters making a social choice, and the theorem studies regret rather than a complexity class. The continuous object here is genuinely the population of repeated expert instances, but the paper’s own motivating market treats the probability distribution over outcomes as the market state. I would sell this as a narrow, credible mirror of its expert-learning results—not as evidence that the whole paper is already a continuous computational social choice study.
Theorem 4 is the only strong anchor, but it gives a regret guarantee, not a computational complexity result. It assumes a valid market with bounded loss and sufficiently stable prices, then derives regret for the corresponding learner. It does not specify how the cost function is represented or bound the time needed to compute its prices. The paper’s computational question is closer to its discussion of pricing over large outcome spaces; that work concerns the outcome space, not the number of traders or experts.
The expert-cohort interpretation is the strongest repair. With repeated forecasting services, \(\mu\) is a sensible prior over expert types, and weighted LMSR updates preserve the theorem’s guarantee. But this makes multiplicity matter only through the prior: the comparator is still the best supported type, and the learner still computes over the \(\tau\) types. If the types have arbitrary expert-specific loss streams, identical advice does not ensure identical losses; grouping them requires restricting the paper’s adversarial model or defining types by full behavior across histories. Either choice is coherent, but it supplies a new population interpretation for the learning problem rather than exposing a population-dependent computational question in Theorem 4.
The more ambitious version would ask which type-indexed cost functions permit efficient price computation. That question needs a representation for the cost function and for any implicit type universe. With an explicit support of size \(\tau\), weighted LMSR is just a \(\tau\)-coordinate update. If an implicit, large type space makes pricing difficult, the computational challenge lies in representing and searching that space; the society-as-a-list-of-supported-types model no longer captures it. A continuum of traders fares no better: the market state already aggregates trades, so trader count does not enter the price computation.
That is the best case against the anchor: the proposed mirror has a population story, but its computational content comes from the chosen market family or type-space representation, not from continuizing the population. I cannot make the universal negative airtight, though. A cohort of repeated forecasting services is plausible, and the paper’s expert-learning interpretation gives its authors a credible reason to recognize weighted high-multiplicity learning as an extension of their problem. The objection is strongest against calling Theorem 4 a ChoCo complexity mirror; it does not rule out the narrower extension.
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.