Problem 10 · Combinatorial market makers · 3 min read

Nobody prices a joint distribution of scientific claims.

Science does not need probabilities on isolated claims. It needs "X works given Y and Z". The outcome space explodes and every known market maker either goes bankrupt or becomes intractable.

Complexity theory Mechanism design Biggest unbuilt thing

Simple assumes nothing

Prediction markets handle one question at a time. Will this drug pass trials, yes or no.

Real questions come in combinations. Does this drug work given the patient has this gene and is already taking that other drug? Now you need prices on every combination of conditions, and the number of combinations doubles with each variable you add. Twenty variables gives you a million outcomes. Fifty gives you more than you could ever store.

The machinery that quotes prices cannot keep up. It either takes on unlimited risk or it needs more computation than exists. Venues now sell simple combinations of events, but for science these markets do not get built, and the questions that matter most stay unpriced. Hanson ran a working version for science between 2010 and 2015, called SciCast. It shut down. Nobody rebuilt it.

Moderate assumes you know what a market is

LMSR prices n outcomes by tracking quantities and evaluating a cost function, with a clean worst-case loss of b·ln(n). Over a combinatorial space n is exponential in the number of base events, so both the storage and the cost function evaluation blow up together.

The known results are discouraging in a specific and useful way. Pricing LMSR over combinatorial spaces is #P-hard in general, the same complexity class as counting satisfying assignments. Approximations exist for restricted structures, for instance when the dependency graph is a tree or has bounded treewidth, and that is exactly where the interesting scientific questions do not live.

What makes it worth attacking anyway is the payoff. A priced joint distribution over hypotheses tells a researcher which experiment removes the most uncertainty per dollar. A nervous system for science, and the closest thing that ever existed was shut down a decade ago while DeSci spent its attention elsewhere.

Technical state of the art and the gap

The obstruction is that LMSR's cost function C(q) = b·ln Σ exp(q_i/b) requires a sum over an exponential outcome set, and computing it exactly for combinatorial securities is #P-hard. Chen and Pennock mapped the tractable islands, and they are narrow.

Four live directions. Approximate pricing with bounded loss, accepting a maker whose worst case exceeds b·ln(n) by a stated factor in exchange for polynomial time. Sampling-based makers using MCMC over the outcome space, which raises the question of whether manipulation through sampling bias is exploitable and nobody has answered it. Restricting to structured spaces and asking the empirical question of whether real scientific hypothesis structures have bounded treewidth, which is checkable and unchecked. And constraint-based pricing, serving only the marginals and conditionals someone actually asks for rather than representing the joint at all, which converts the problem from representation into query answering and may be the practical route.

Combinatorial contracts are no longer hypothetical. Kalshi lists multivariate event contracts in production, 7.6 million unique tickers in one week, though only about a third ever show volume or open interest (arXiv 2609.17610). Three 2026 papers attack the maker side (arXiv 2607.17428, 2603.22596, 2607.18299). The gap that would move things is narrower now: an implementation that prices a real joint distribution over ten to twenty dependent scientific claims with measurable loss bounds, even a slow one.

Where I would start

  1. Read Chen and Pennock on the complexity of LMSR pricing over combinatorial spaces, and find the exact boundary of the tractable cases.
  2. Answer the empirical question nobody has. Take one real research area, write down the dependency graph over its live hypotheses, and measure the treewidth. If it is low, a large piece of the problem dissolves.
  3. Build the query-based maker that prices only what is asked rather than representing the joint. This is the under-attacked direction and it is engineering rather than theory.
  4. Find out what SciCast actually did and why it stopped. It worked. The reasons it ended are worth knowing before rebuilding it.

What counts as a result

A working maker over ten to twenty linked scientific claims with a stated loss bound, however slow. Venues already price combinations of event outcomes, so the bar is the scientific case: dependent claims, a stated bound, and code someone else can run.

Related