Computational Aspects Of Prediction Markets

Motivation: aggregating scattered knowledge

DefinitionThe information aggregation problem

An aggregator wants a forecast of an uncertain variable, say the global average temperature in 2020. Many informants hold different, nonindependent pieces of relevant information. The goal is a mechanism that elicits and combines this information into a collective forecast, ideally equal to the omniscient forecast: what someone with direct access to everyone’s information would predict.

DefinitionPrediction market

The aggregator creates a security whose payoff depends on the outcome, e.g. $ $x$ if the 2020 temperature equals $x$ , and lets informants trade it freely. Believers in global warming buy at or above today’s temperature; skeptics sell. The trading price is read as the collective forecast of the expected value.

Also called information markets, Arrow–Debreu securities, contingent claims, event futures, idea futures. (Time value of money ignored.)

IntuitionThe central question

A market can in principle turn private beliefs into a price that knows what everyone knows. But operating it may be computationally intractable, subsidizing it must be done with bounded loss, and even a well-run market may fail to compute the answer. Where exactly are these computational limits?

The chapter locates computation in three places:

Where	Problem	Section
the auctioneer	matching orders over exponentially many combined events	Combinatorial prediction markets
the market maker	updating prices after every trade with bounded loss	Automated market makers
the market as a whole	does the price converge to the right answer, and how fast?	The market as a distributed computer

Background

The partition model of knowledge

DefinitionDefinition 26.1 — partition model

$\Omega$ is the set of states of the world. Exactly one state $\omega\in\Omega$ is true.
Agent $i$ ‘s information is a partition $\pi_i$ of $\Omega$ . She knows which cell contains the true state but can’t distinguish states within a cell.
The combined information $\hat\pi$ is the coarsest common refinement of $\pi_1,\dots,\pi_n$ .

Usually a common prior $P\in\Delta(\Omega)$ is added. Agents form posteriors by conditioning $P$ on their cell.

ExampleFigure 26.1 — three base events

Events $X_1,X_2,X_3$ generate 8 states. For example, $\omega_4 = \omega_{X_1\bar X_2X_3}$ means $X_1$ true, $X_2$ false, $X_3$ true. Agent $i$ knows only whether $X_i$ holds, so $\pi_1 = \{\{\omega_1..\omega_4\},\{\omega_5..\omega_8\}\}$ . Together the three agents pin down the state exactly: $\hat\pi$ is the finest partition, into singletons.

Forecasts.

A forecast is an estimate of $\mathbb{E}[f(\omega)]$ for a commonly known function $f$ .
An event is an $f : \Omega\to\{0,1\}$ .
A joint forecast is a joint distribution over several functions.
The omniscient forecast conditions $P$ on the true cell of $\hat\pi$ .

ImportantAggregation is mechanism design

Each agent’s information is private. The task is a mechanism whose equilibrium output is as close as possible to the omniscient forecast (see mechanism-design). A market pays agents for moving the price toward the truth.

Mechanisms and evidence

Mechanism	How trades happen
call market	batch bids; clear at the $m$ -th or $(m+1)$ -th lowest price, or between ( $m$ = number of sellers)
continuous double auction	trade immediately whenever two orders cross, usually at the earlier bidder’s price
market maker / bookmaker	always willing to buy and sell at posted, changing prices
parimutuel	winners split the total pool in proportion to their stakes

Variables can be binary, discrete, continuous or joint, and combinatorial versions of each mechanism exist.

ExampleEmpirical record

Iowa Electronic Market (since 1988, real money, mostly elections): on average more accurate and less volatile than polls. It reacts within minutes, often before news spreads, even though individual traders are biased.
Marginal-trader hypothesis: accuracy comes from a few active, less biased, price-making traders, not from the average trader.
Options, futures and sports betting odds are accurate forecasts of their underlying variables.
Play-money markets (Hollywood Stock Exchange, NewsFutures, Foresight Exchange) match experts and sometimes real-money markets.
Lab experiments: with enough securities and practice, prices approach omniscient forecasts.
Field: HP’s internal sales market beat official forecasts. Microsoft and Google run internal markets.

NoteEvaluation is comparative

A market can’t surface information nobody has, so accuracy is judged only against other aggregation methods.

Rational expectations

WarningSecurities have no consumption value

People buy a security only because they expect to resell or cash it out higher. Prices carry information about others’ beliefs, which changes each trader’s demand. So the classical fixed-demand-curve model fails.

DefinitionDefinition 26.2 — rational expectations equilibrium (REE)

Traders are risk-neutral Bayesians with a common prior and private information $\pi_i$ . Take $\hat\pi$ to be the finest partition. An REE is a mapping $P^* : \Omega \to \mathbb{R}$ such that, in every state, if each trader conditions demand on $\pi_i$ and on the price $P^*(\omega)$ , the market clears at exactly $P^*(\omega)$ . It is a self-fulfilling state-to-price correspondence.

IntuitionUnpacking the fixed point

Any nonconstant price map $P$ induces a partition $\pi_P$ : seeing the price rules out states that would have produced a different price. Each trader’s effective valuation becomes $\mathbb{E}[v \mid \pi_i(\omega), P(\omega)]$ , which yields a clearing price $\tilde v(\omega)$ . $P$ is an REE iff $\tilde v = P$ : believing in the map and acting on it reproduces the map.

TheoremFully revealing equilibria

REE exist under fairly general conditions. Generically, there are fully revealing REE, with $P^*(\omega_1) \ne P^*(\omega_2)$ whenever $\omega_1 \ne \omega_2$ , so that $\pi_{P^*} = \hat\pi$ : the price reveals everyone’s combined information.

NoteCriticism

REE says nothing about how traders would learn or agree on $P^*$ . The price-formation process must be modelled separately. The market as a distributed computer shows it can fail.

DefinitionEfficient market hypothesis (strong form)

The price fully reflects all information relevant to the security’s value. This is the theoretical case for prediction markets: many small pieces of private information end up in the price.

WarningNo-trade theorems

In a fully revealing REE, everyone conditions on the same information, so they share posteriors and valuations, and nobody trades. More strongly, rational agents won’t trade even out of equilibrium, because a counterparty’s willingness to trade reveals information. Paradox: the price contains everyone’s information, but nobody trades to put it there.

ImportantWhy trade happens anyway

No-trade results are fragile. They need risk neutrality and common knowledge of full rationality. Real sources of expected profit: irrational traders, hedgers, liquidity traders, and a subsidizing market maker.

Combinatorial prediction markets

Setup. A finite set $E$ of Boolean base events $X_1, X_2,\dots$ (“gas costs more than $3”), linearly independent in the sense that no event is determined by the others. Then $|\Omega| = 2^{|E|}$ .

DefinitionComplete market

Let $S_\omega$ pay $1 iff the state is $\omega$ . A market is complete if traders can build a portfolio replicating any $S_\omega$ . Classic results: complete markets can be guaranteed efficient.

CautionCompleteness is exponential

A complete market needs at least $2^{|E|}$ securities. With many base events, even listing them is impossible. There may be far fewer combinations traders care about, which raises two questions: is there a succinct representation for orders, and can matches be found in it?

Two forms of expressive bidding:

Order type	Trader says	Auctioneer problem
combined	”this bundle of securities, each within its limit price, or nothing”	like combinatorial auctions (Chapter 11), but bids are often divisible; called combined value trading
compound	”a security on this Boolean formula over $E$ ”	$2^{2^{\lvert E\rvert}}$ expressible events; a strict superset of combined orders

NoteExecution risk

Combined orders remove execution risk: prices moving midway through a planned series of trades and ruining the earlier ones.

Compound securities and the matching problem

DefinitionConditional security $S_{\phi|\psi}$

For Boolean formulas $\phi,\psi$ over $E$ :

pays $1 if $\phi\wedge\psi$ ;
pays $0 if $\psi\wedge\neg\phi$ ;
cancelled and refunded if $\neg\psi$ .

The unconditional $S_\phi$ is $S_{\phi|\text{true}}$ .

DefinitionOrders and payoff vectors

An order $o$ = ” $q$ units of $S_{\phi|\psi}$ at price $p$ .” Here $q > 0$ is a buy (accepting any price $\le p$ ) and $q < 0$ a sell (any price $\ge p$ ). Divisible orders accept any fraction $\alpha q$ with $\alpha\in(0,1]$ ; indivisible orders accept exactly $q$ or nothing. The payoff vector over states is

\Upsilon^\omega = q\cdot\mathbb 1_{\omega\in\psi}\big(\mathbb 1_{\omega\in\phi} - p\big).

If the auctioneer accepts fractions $\alpha_i$ , its surplus in each state is $\Upsilon_{\text{auc}} = -\sum_i\alpha_i\Upsilon_i.$

DefinitionDefinitions 26.3 / 26.5 — the matching problem

Does there exist $\alpha$ with some $\alpha_i > 0$ such that $\Upsilon^\omega_{\text{auc}} \ge 0$ for every state $\omega$ ? That is, can the auctioneer accept a nonempty set of orders without risk, breaking even at worst?

Indivisible: $\alpha_i\in\{0,1\}$ .
Divisible: $\alpha_i\in[0,1]$ .

ExampleExample 26.4 — two orders that match

$|E| = 2$ , with states ordered $(X_1X_2,\ X_1\bar X_2,\ \bar X_1X_2,\ \bar X_1\bar X_2)$ .

Buy 1 of $S_{X_1X_2}$ at 0.4: $\Upsilon_1 = (0.6, -0.4, -0.4, -0.4)$ .
Sell 1 of $S_{X_1}$ at 0.3: $\Upsilon_2 = (-0.7, -0.7, 0.3, 0.3)$ .

\Upsilon_{\text{auc}} = -\Upsilon_1 - \Upsilon_2 = (0.1, 1.1, 0.1, 0.1) \ge 0.

The orders match. The auctioneer keeps $0.10 cash plus one unit of $S_{X_1\bar X_2}$ .

Complexity of matching

Let $n$ be the input size, which also bounds the number of base events.

	$O(\log n)$ base events (poly many states)	unlimited base events (exponentially many states)
divisible	P (LP)	co-NP-complete
indivisible	NP-complete	$\Sigma_2^p$ -complete

TheoremTheorem 26.6 — divisible matching

Divisible matching is polynomial-time for $O(\log n)$ base events and co-NP-complete in general.

ProofLP, a small certificate for infeasibility, and a SAT reduction

Step 1: The LP (few events). Variables $0\le\alpha_i\le1$ . One constraint per state: $\sum_i -\alpha_i\Upsilon_i^\omega \ge 0.$ Maximize $\sum_i\alpha_i$ . A match exists iff the optimum is $> 0$ . With $O(\log n)$ events there are polynomially many states, so the LP is polynomial. (The chapter notes this approach may miss matchings with exactly zero surplus.)

Step 2: In co-NP (many events). Now there are exponentially many constraints, but each is short and easy to evaluate. With $m\le n$ orders, LP theory says that if the optimum is 0, some $m+1$ constraints already force it. Guess them and solve the small LP. That is a polynomial certificate that no match exists.

Step 3: co-NP-hard, via SAT. Given a formula $\phi$ , take its variables as base events and a single buy order for $S_\phi$ at 0.5.

$\phi$ satisfiable: in a satisfying state the auctioneer pays out, giving surplus $-0.5$ , so no fraction matches.
$\phi$ unsatisfiable: the security never pays, so surplus is $+0.5$ in every state, and it matches.

The key step: a match exists iff $\phi$ is unsatisfiable. So matching is as hard as UNSAT.

∎

TheoremTheorem 26.7 — indivisible matching

Indivisible matching is NP-complete for $O(\log n)$ base events and $\Sigma_2^p$ -complete in general.

NoteProof omitted in the chapter

The chapter omits it for space.

IntuitionWhere the two sources of hardness come from

Indivisibility adds a combinatorial choice (which subset of orders), which gives the NP-type “exists” layer. Exponentially many states add a universal check (surplus $\ge0$ in every state), which gives the co-NP-type “for all” layer. With both, you get $\exists\forall$ , i.e. $\Sigma_2^p$ .

Compact markets: exploit independence

DefinitionBN-structured market

Suppose base events factor as a Bayesian network: $\Pr(X_1\cdots X_{|E|}) = \prod_{k=1}^{|E|}\Pr(X_k\mid\mathrm{pa}(X_k)),$ where the parents $\mathrm{pa}(X_k)$ have smaller indices. Trade only the conditional securities $S_{X_j\mid\mathrm{pa}(X_j)}$ , one per parent configuration. That is $O\big(|E|\cdot 2^{\max_j|\mathrm{pa}(X_j)|}\big)$ securities, far fewer than $2^{|E|}$ when parent sets are small.

TheoremOperational completeness

A BN-structured market is operationally complete (its equilibrium is Pareto optimal for the traders present) if all traders’ risk-neutral independencies agree with the network’s. For traders with constant absolute risk aversion (exponential utility), agreement on Markov independencies suffices.

NoteStated without proof

Completeness in all circumstances still needs $2^{|E|}$ securities.

Automated market makers

Why not just a continuous double auction?

WarningTwo problems with pure order matching

Thin markets. An informed trader may wait forever for a counterparty. Expecting none, traders don’t come: a chicken-and-egg breakdown. It is worst in combinatorial markets, where attention is spread over exponentially many securities.
Revealing intent. Posting a limit order tips off others. Traders play a zero-sum game with each other, so no-trade logic bites.

DefinitionMarket maker

An agent always ready to trade at posted bid and ask prices, which may be equal. It bridges buyers and sellers who arrive at different times.

ImportantSubsidy defeats no-trade

The market maker can lose money, which is a deliberate subsidy. With a subsidy, the no-trade theorems no longer apply, so informed traders can rationally expect to profit. The loss must be bounded, which requires updating prices systematically after every trade.

Desiderata for an automated market maker:

bounded (predictable) loss;
informed traders are motivated to trade whenever their information would move the price;
computing new prices after each trade is tractable.

Market scoring rules (Hanson)

A proper scoring rule pays for a probability report so that truthful reporting is optimal. Hanson turns any such rule into a market maker.

DefinitionCost-function market maker

There are $|\Omega|$ mutually exclusive, exhaustive securities, and $q_j$ is the total quantity of security $j$ held by traders. A cost function $C(q)$ records total trader spending. Moving outstanding shares from $q^{\text{old}}$ to $q^{\text{new}}$ (any bundle, combined or compound order; negative entries are sells) costs $C(q^{\text{new}}) - C(q^{\text{old}}).$ The instantaneous price of $j$ is $\partial C/\partial q_j$ . The winning security pays $1 per share.

Component	Detail
Signature	$C : \mathbb{R}^{\lvert\Omega\rvert}\to\mathbb{R}$
Domain	outstanding shares of every outcome
Codomain	total money collected from traders so far
Prices	the gradient $\nabla C$ , read as the market’s probability forecast

FormulaLogarithmic market scoring rule (LMSR)

C(q) = b\ln\Big(\sum_j e^{q_j/b}\Big),\qquad p_j = \frac{\partial C}{\partial q_j} = \frac{e^{q_j/b}}{\sum_k e^{q_k/b}}.

The maximum loss is $b\ln|\Omega|$ . Larger $b$ means more liquidity (more shares near the current price) but more risk. It is deployed at InklingMarkets, Net Exchange and Microsoft.

DerivationWhy LMSR’s worst-case loss is

b\ln|\Omega|

Start at $q = 0$ , so $C(0) = b\ln|\Omega|$ . The market maker has collected $C(q) - C(0)$ and owes at most $\max_j q_j$ (if the most-held outcome wins). Since $C(q)\ge b\ln e^{\max_jq_j/b} = \max_jq_j$ , $\text{net} = C(q) - C(0) - \max_jq_j \ge -b\ln|\Omega|.$ (This derivation is mine; the chapter states the bound.)

FormulaQuadratic market scoring rule

C(q) = \frac{\sum_jq_j}{|\Omega|} + \frac{\sum_jq_j^2}{4b} - \frac{(\sum_jq_j)^2}{4b|\Omega|} - \frac{b}{|\Omega|},\qquad p_j = \frac{1}{|\Omega|} + \frac{q_j - \bar q}{2b}.

WarningQuadratic is impractical

Prices are linear in quantities, so they would leave $[0,1]$ . The maker can sell only a small fixed number of shares, and once one security hits its cap it can’t accept buys on the others. LMSR accepts arbitrarily large orders.

IntuitionSequential shared scoring rule

Equivalently, the maker starts with an initial probability estimate. Each trader pays the scoring-rule payment for the previous report and receives the payment for her own. Myopically, reporting truthfully is still optimal. The final trader is paid by the maker, so the maker’s loss is at most the maximum payment to the last trader minus the payment from the first.

graph LR
  M["Market maker: initial estimate"] -->|"trader 1 pays score of maker's report"| T1["Trader 1 reports"]
  T1 -->|"trader 2 pays score of trader 1's report"| T2["Trader 2 reports"]
  T2 -->|"..."| TN["Final trader reports"]
  TN -->|"maker pays final trader's score"| M

Dynamic parimutuel markets

DefinitionDynamic parimutuel market

In a parimutuel game, winners split the total pool in proportion to their shares. The dynamic variant makes share prices vary according to a cost function, so traders can sell before resolution. To the trader it acts like a market maker.

FormulaShare-ratio cost function

C(q) = \kappa\sqrt{\sum_j q_j^2},\qquad p_j = \frac{\kappa\,q_j} {\sqrt{\sum_kq_k^2}}.

It is the unique dynamic parimutuel cost function with $p_j/p_k = q_j/q_k$ (price ratios equal share ratios).

DerivationWith

\kappa = 1

: prices below 1, payoffs above 1

Price: $p_j = q_j/\sqrt{\sum q_k^2}\le1$ . The pool is $C(q) = \sqrt{\sum q_k^2}$ , so the payoff per winning share is $C(q)/q_j\ge1$ . Hence a winning bet never loses money.

The mechanism is also arbitrage-free. The maker seeds initial shares $q$ with $C(q)$ dollars, which is its maximum risk.

	Market scoring rule	Dynamic parimutuel
payout per winning share	fixed $1	a share of the total pool (uncertain)
price as forecast	direct probability	less direct
trading strategy	simpler	more complex
appeal	forecasting	risk-seeking gamblers

The market as a distributed computer

Turn the viewpoint inside out: treat market plus traders as a computational device. What can it compute, and how fast?

IntuitionWhere the computation happens

In the traders’ belief updates. Each trader observes the price, a signal combining others’ information, and merges it logically with her own private information. This also addresses REE’s gap: how are equilibrium prices reached? Plausible dynamics can get stuck at an uninformative equilibrium even when a fully revealing one exists.

The Boolean market model

DefinitionBoolean market

$n$ traders, where trader $i$ privately knows one bit $x_i$ . So $\Omega = \{0,1\}^n$ and $\pi_i$ splits $\Omega$ by the value of $x_i$ .
A security $F$ pays $1 iff $f(x) = 1$ , for a commonly known $f : \{0,1\}^n\to\{0,1\}$ .
The traders’ combined information determines $f(x)$ , so an efficient market should converge to price $f(x)$ .

DefinitionPrice formation

Synchronous rounds. Each trader submits money $b_i$ and quantity $q_i$ (no credit or short-sale limits). The market clears at $p = \frac{\sum_ib_i}{\sum_iq_i}.$ Trader $i$ ends with $q_i' = b_i/p$ units and $b_i' = b_i - p(q_i' - q_i) = pq_i$ money: a net buy if $p < b_i/q_i$ and a net sell if $p > b_i/q_i$ . The price is announced, beliefs are updated, and the process repeats until nothing changes.

Simplification: $q_i = 1$ for all $i$ , so $p$ is the average bid.

NoteWhy force $q_i = 1$

It forces trade, sidestepping no-trade theorems without modelling hedgers or subsidies explicitly.
Known volumes help traders learn from prices. This arguably gives them too much power, yet convergence can still fail.

DefinitionAgent behaviour

Agents are risk-neutral, myopic (each round treated as the last), and bid truthfully their current expected value of $F$ . They share a common prior $P$ , update by Bayes’ rule, and this behaviour is common knowledge.

ExampleExample 26.8 — OR, first round

Two traders, uniform prior, $f = x_1\vee x_2$ .

$x_1 = 0$ : $x_2$ is equally likely 0 or 1, so trader 1 bids $0.5$ .
$x_2 = 1$ : $f = 1$ for sure, so trader 2 bids $1$ .

The first-round price is $0.75$ .

Knowledge dynamics and equilibrium

After round $r$ :

the common-knowledge set is $S^r$ (states an outside observer, seeing only prices, considers possible);
trader $i$ ‘s knowledge is $S_i^r = \{y\in S^r : y_i = x_i\}$ .

Start with $S^0 = \Omega$ . The observer knows the map $\text{price}_1(\cdot)$ from states to first-round prices, so $S^1 = \{y\in S^0 : \text{price}_1(y) = p^1\}$ , and so on. Knowledge only shrinks, so the process reaches an equilibrium $(S^\infty, S_i^\infty, p^\infty)$ in finitely many rounds.

TheoremTheorem 26.9 — agreement at equilibrium

P\big(f(y) = 1\mid y\in S^\infty\big) = p^\infty, \qquad P\big(f(y) = 1\mid y\in S_i^\infty\big) = p^\infty\ \ \forall i. \tag{26.1–26.2}

Every trader’s expectation equals the uninformed observer’s, and equals the price.

NoteStated without proof

It follows from known results on common knowledge of aggregates.

WarningAgreement ≠ aggregation

Traders can agree on an expectation strictly between 0 and 1 while their combined information determines $f(x)$ exactly. Their knowledge sets may differ as long as the conditional expectations coincide.

ExampleExample 26.10 — XOR gets stuck

Two traders, uniform prior, $f = x_1\oplus x_2$ .

Trader 1: whatever $x_1$ is, $f = 1$ iff $x_2 = \bar x_1$ , which has probability $\tfrac12$ . So she bids $0.5$ regardless.
Trader 2 likewise always bids $0.5$ .

The price is $0.5$ , which reveals nothing about either bit. Nobody updates, so equilibrium is reached at $p^\infty = 0.5$ . Both traders agree (as Theorem 26.9 requires), yet $f(x)$ is never revealed.

IntuitionWhy XOR fails

Each bid is a function of one bit, and the price is their sum. For XOR, each trader’s expected value is the same whatever her bit is, so the sum carries no signal. A function computable from sums of per-bit contributions must be linearly separable.

Computable aggregates are exactly threshold functions

DefinitionDefinition 26.11 — weighted threshold function

$f$ is a weighted threshold function iff there are reals $w_0,\dots,w_n$ with $f(x) = 1 \iff w_0 + \sum_{i=1}^n w_ix_i \ge 1.$ OR is threshold ( $w_0 = 0$ , $w_i = 1$ ). XOR is not.

TheoremTheorem 26.12 — threshold ⇒ always computed

If $f$ is a weighted threshold function, then for every prior $P$ the equilibrium price of $F$ equals $f(x)$ .

TheoremTheorem 26.13 — non-threshold ⇒ sometimes not

If $f$ is not a weighted threshold function, some prior $P$ makes the price of $F$ fail to converge to $f(x)$ .

TheoremTheorems 26.14–26.15 — convergence time

For a threshold $f$ with $n$ inputs and any prior, the price reaches $p^\infty = f(x)$ within at most $n$ rounds.
Some function $C_n$ on $2n$ inputs, with some prior $P_n$ , needs $n$ rounds in the worst case.

NoteProofs omitted

The chapter omits Theorems 26.12–26.15 for space. It notes that simulations suggest near-constant expected convergence time for almost every threshold function.

ImportantWhat a single security can compute

One market price computes precisely the functions a single linear threshold unit (a perceptron) computes. Anything else, such as XOR, needs several securities combined. How many is open.

Open questions

NoteCombinatorial markets

The bidder’s side: how to choose formulas, quantities and prices, possibly with penalties on bid complexity.
Less expressive bidding languages with polynomial matching that are still useful.
Heuristic or approximate matching; logical-reduction algorithms.
Permutation combinatorics (horse-race orderings: ” $X_1$ wins,” “top 3,” ” $X_1$ beats $X_2$ ”): languages with tractable matching.
Sharing auctioneer surplus with traders, and the incentives this creates.
Matching a single new order against a no-match book (the standard continuous double auction rule).
Computational equilibrium: can a market settle where no bounded agent finds an improvement, yet it isn’t a true equilibrium?

NoteMarket makers

For every polynomially matchable bidding language, is there a polynomial-time market-scoring-rule maker?
Market makers are online algorithms (see online-mechanisms): accept or reject orders one at a time under a worst-case loss budget. Can other online algorithms accept more orders for the same bound?

NoteMarkets as computers

Noisy prices, and misinformed or irrational traders: what is still computable?
Incremental recomputation when a few input bits flip.
A distributed-computing model of decentralized markets.
The complexity of traders’ belief updates.
Replacing the truthful-bidding assumption with game-theoretic rationality.
Average-case convergence over the prior.
The minimum number of threshold securities needed to implement a given function, and security designs that speed up convergence.

Quick reference

Object	Statement	Note
Aggregation problem	elicit and combine private info into the omniscient forecast	mechanism design
Partition model (Def 26.1)	$\pi_i$ partitions $\Omega$ ; combined info $\hat\pi$ = coarsest common refinement	common prior $P$
REE (Def 26.2)	self-fulfilling map $P^*:\Omega\to\mathbb R$	generically fully revealing
Efficient market hypothesis	price reflects all relevant information	foundation for prediction markets
No-trade theorems	rational agents with common knowledge never trade	broken by hedgers, noise, subsidies
Complete market	needs $2^{\lvert E\rvert}$ securities	combinatorial blow-up
$S_{\phi\mid\psi}$	$1 if $\phi\wedge\psi$ , $0 if $\neg\phi\wedge\psi$ , refunded if $\neg\psi$	compound / conditional
Order payoff	$\Upsilon^\omega = q\,\mathbb 1_\psi(\mathbb 1_\phi - p)$
Matching	$\exists\alpha\ne0$ : $-\sum\alpha_i\Upsilon_i \ge 0$ in every state	risk-free acceptance
Ex. 26.4	buy $S_{X_1X_2}$ @0.4 + sell $S_{X_1}$ @0.3 ⇒ $(0.1, 1.1, 0.1, 0.1)$	match
Thm 26.6	divisible: P (few events), co-NP-complete (many)	LP; SAT reduction
Thm 26.7	indivisible: NP-complete (few), $\Sigma_2^p$ -complete (many)
BN market	$O(\lvert E\rvert\,2^{\max\lvert\mathrm{pa}\rvert})$ securities	operationally complete if independencies agree
AMM desiderata	bounded loss; incentive to trade; tractable updates	subsidy defeats no-trade
Cost-function maker	pay $C(q^{\text{new}}) - C(q^{\text{old}})$ ; price $\partial C/\partial q_j$	$1 per winning share
LMSR	$C = b\ln\sum e^{q_j/b}$ , softmax prices	loss $\le b\ln\lvert\Omega\rvert$
Quadratic MSR	prices linear in $q$	only small fixed purchases
Sequential scoring	pay predecessor’s score, receive your own	equivalent to the cost-function form
Share-ratio DPM	$C = \kappa\sqrt{\sum q_j^2}$ , $p_j/p_k = q_j/q_k$	pays a share of the pool
Boolean market	bits $x_i$ ; security pays $f(x)$ ; price = mean bid ( $q_i = 1$ )	myopic truthful Bayesians
Ex. 26.8 (OR)	bids 0.5 and 1 ⇒ price 0.75
Thm 26.9	at equilibrium, all expectations = observer’s = $p^\infty$	common knowledge of aggregates
Ex. 26.10 (XOR)	stuck at 0.5 forever	agreement without aggregation
Threshold function	$f = 1 \iff w_0 + \sum w_ix_i\ge1$	linearly separable
Thms 26.12–26.13	computable for all priors ⟺ threshold
Thms 26.14–26.15	$\le n$ rounds; some instances need $n$

Facts to keep to hand

Rational expectations promises aggregation; computation decides whether you get it. Fully revealing REE exist generically, but the auctioneer may face co-NP- or $\Sigma_2^p$ -hard matching, and natural price dynamics compute only threshold functions.
No-trade theorems explain why subsidies matter. In a zero-sum game among rational traders, willingness to trade reveals information and kills the trade. A bounded-loss market maker injects money so that informed trading becomes profitable. LMSR’s $b\ln|\Omega|$ is literally the price of information.
Complexity has two independent layers. Indivisibility adds an “exists a subset” choice, and exponentially many states add a “for every state” check. Divisible with few states is P, and each added layer climbs one step, up to $\Sigma_2^p$ with both.
Structure is the escape from $2^{|E|}$ . Bayesian-network conditional securities give polynomially many instruments, and they are enough whenever traders’ independencies match the network.
A price is a sum, so it computes linear threshold functions. Each trader contributes a bid that depends on her information, and the price averages them. Functions that are not linearly separable (XOR) can leave every bid uninformative. One security acts like one perceptron.
Agreement is not aggregation. At equilibrium everyone agrees on the price (common knowledge of aggregates), but agreeing on $0.5$ can coexist with the truth being fully determined by what they jointly know.
Market makers are cost functions whose gradient is the forecast. LMSR prices are a softmax, and the quadratic rule has linear prices, which breaks the $[0,1]$ range. The share-ratio parimutuel pays from the pool. The sequential-scoring-rule reading explains why truthful moves are myopically optimal.

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 26 (Pennock, Sami)

Related