Log-time Prediction Markets for Interval Securities

We design a prediction market to recover a complete and fully general probability distribution over a continuous random variable. Traders buy and sell interval securities, or binary contracts that pay $1 if the outcome falls into an interval and $0 otherwise. We allow traders to express any interval endpoint of arbitrary precision, in service of recovering distributions of any complex shape and number of modes. Our market takes the form of a central automated market maker offering prices for every interval security that traders propose. All market operations can be achieved in time logarithmic in the number of outcomes (that traders distinguish), providing the first computationally efficient market for a continuous variable. We present two designs. The first replicates the popular logarithmic market scoring rule (LMSR) exactly, keeping its bounded-loss guarantee, while utilizing a balanced binary tree to execute all operations exponentially faster than standard LMSR markets. We exploit modularity properties of LMSR to decompose computations along nodes of the tree. The second features two or more parallel LMSR market makers that mediate submarkets with increasingly fine-grained outcome partitions. This design remains computationally efficient for all operations, including arbitrage removal across submarkets, and adds two additional benefits: (1) the ability to flexibly express utility for information at various resolutions by assigning different liquidity values, and (2) the ability to guarantee true constant bounded loss by geometrically decreasing the liquidity in each submarket. We conduct simulation experiments to illustrate the flexibility of our second design, showing that it can converge fast at both coarse and fine resolutions, whereas standard LMSR markets need to pick the preferred outcome resolution ex ante.