d4-conf-sagt-2024-0006

There is no named hardness or complexity class result in this paper. My best positive case is Theorem 4, proved here: in Kelly markets, for every competence profile \(q\) and induced belief profile \(b\), weighted majority with weights \(w_i\propto 2q_i-1\) chooses the same alternative, including ties, as the market decision obtained by binarizing its equilibrium price \(p_{KC}(b)\). The supporting Lemma 5, attributed to [5] and reproved in the appendix, gives the price explicitly: \(p_{KC}(b)=\frac{1}{n}\sum_i b_i\). These results establish an efficiently computable aggregation rule, though they do not themselves present a complexity classification.

The mirror I would put to a prover is Continuous Kelly Condorcet Aggregation. An instance is a finite support of types \(t=(q_t,y_t)\), where \(q_t\in\mathbb Q\cap(1/2,1)\) is the type’s competence, \(y_t\in\{A,B\}\) its observed signal, and \(\mu_t\in\mathbb Q_{\ge0}\) its population mass, with \(\sum_t\mu_t=1\). Its posterior belief is \(b_t=q_t\) for \(y_t=A\), and \(b_t=1-q_t\) for \(y_t=B\). Each unit of mass represents traders of that type with the paper’s unit endowment and Kelly utility. Find the competitive equilibrium price \(p\) and each type’s per-capita investment in the two securities. A solution must give best responses at \(p\) and satisfy market clearing:
\[ \frac{1}{p}\sum_t\mu_t x_t^A = \frac{1}{1-p}\sum_t\mu_t x_t^B. \]
Then report the price-induced decision: \(A\) if \(p>1/2\), \(B\) if \(p<1/2\), and a tie if \(p=1/2\). This is an equilibrium computation, not a social optimization problem: each type maximizes its expected log payout.

The paper’s Lemma 5 gives the solution directly:
\[ p=\sum_t\mu_t b_t. \]
At that price, type \(t\) invests \(\max\{(b_t-p)/(1-p),0\}\) in \(A\) and \(\max\{(p-b_t)/p,0\}\) in \(B\). Theorem 4’s weighted-majority equivalence extends from sums to these mass-weighted sums. Thus the continuous problem is tractable by a scan over the \(\tau\) supported types, with polynomial bit complexity in \(\tau\) and the rational input length. Its expected direction is tractable.

The regime is a large prediction market or binary-decision crowd with a small number of calibrated competence classes: many traders share a competence class and signal outcome, so \(n\) can be very large while \(\tau\) stays small. Mass means the fraction of participants of each type; aggregate endowment scales with that mass, and the market-clearing price is unchanged by this normalization. This preserves the paper’s market and its price-taking equilibrium. It also matches the authors’ own motivation for competitive equilibrium: participants act as price takers in a large group. The paper notes a continuum-player analogue for Naive-market quantiles in its discussion, which supports the plausibility of population continuity but supplies no complexity result.

This mirror covers Theorem 4’s Kelly-market and competence-weighted-majority correspondence. It does not continuize the outcome space or the uncertainty model: the population is the continuous object. Further questions include whether the same formulation handles continuous competence distributions, whether heterogenous utilities preserve tractability, and whether the taxed-market limit in Theorem 5 extends to type masses.

The weak point is that this gives the programme a clean, author-recognizable continuous computation, but not a hard computational question: the price is an average, and the paper proves no discrete hardness that might dissolve in the continuum. Also, the small-\(\tau\) scenario depends on competence classes being a convincing grouping; if most participants have distinct competences, \(\tau\) may be nearly \(n\).