An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments

Lirong Xia, David M. PennockIJCAI 2011 · OpenReview

Abstract

Computing the marketmaker price of a security in a combinatorial prediction market is #P-hard. We devise a fully polynomial randomized approximation scheme (FPRAS) that computes the price of any security in disjunctive normal form (DNF) within an $\epsilon$ multiplicative error factor in time polynomial in $1/\epsilon$ and the size of the input, with high probability and under reasonable assumptions. Our algorithm is a Monte-Carlo technique based on importance sampling. The algorithm can also approximately price securities represented in conjunctive normal form (CNF) with additive error bounds. To illustrate the applicability of our algorithm, we show that many securities in Yahoo!'s popular combinatorial prediction market game called Predictalot can be represented by DNF formulas of polynomial size.

Introduction

Prediction markets allow participants to trade on the outcome of events, with prices reflecting the aggregate belief of the crowd. In a "combinatorial" market, users can bet on complex logical combinations of events, such as "Team A wins the championship OR Team B loses in the second round." While these markets offer high expressive power, they present significant computational challenges.

A schematic of a 4-team tournament structure where outcomes at each round depend on previous match winners.

The standard mechanism for managing these markets is the Logarithmic Market Scoring Rule (LMSR). However, calculating the LMSR price requires summing over every possible outcome. For a standard 64-team tournament, there are $2^{63}$ (roughly $9.2 \times 10^{18}$) possible outcomes. This exponential growth makes exact pricing computationally infeasible (#P-hard). This paper introduces the first Fully Polynomial Randomized Approximation Scheme (FPRAS) for this task, using a novel importance sampling technique to estimate market prices efficiently and accurately.

Methodology

The core contribution is a Monte-Carlo approach that treats pricing as a weighted model counting problem. The proposed FPRAS approximates the price of a security represented in Disjunctive Normal Form (DNF).

Importance Sampling and KLM Adaptation

Instead of sampling tournament outcomes uniformly—which is inefficient as most outcomes have near-zero probability—the algorithm samples based on a "not-too-bad" distribution derived from historical pairwise win rates. The authors adapt the Karp-Luby-Madras (KLM) algorithm, originally designed for counting satisfying assignments in DNF formulas, to handle the weighted probabilities inherent in prediction markets.

Dynamic Programming and Bottom-Up Sampling

To make importance sampling tractable, the authors developed a dynamic programming algorithm (CompMarginal) that computes marginal probabilities of tournament sub-trees in polynomial time, given pairwise win rates. This is paired with a specific sampling routine that generates valid tournament valuations consistent with a given betting clause.

Key Insights

A central insight of this work is the use of DNF as a universal language for tournament bets. Most common bets (e.g., "Team A reaches the Final Four") can be represented as DNF formulas of polynomial size. Furthermore, the paper demonstrates that historical win data is essential not just for setting prices, but for the computational process of calculating them. By using historical data as a prior for importance sampling, the algorithm transforms a "needle in a haystack" search into an efficient process.

Results

The algorithm is proven to be an FPRAS, meaning for any error rate $\epsilon > 0$, it outputs an estimate $\hat{I}$ such that $(1 - \epsilon)I \le \hat{I} \le (1 + \epsilon)I$ with at least 75% probability. The runtime is polynomial relative to the number of teams, the size of the DNF formula, and $1/\epsilon$. This represents a massive improvement over the exponential time required for exact calculation and handles a wider variety of securities than previous methods.

Conclusion and Future Work

While the algorithm provides tight error bounds, it remains an approximation. In high-stakes environments, even small $\epsilon$ errors might be exploitable by arbitrageurs. Additionally, the efficiency depends on the importance sampling distribution being a reasonable approximation of the true market belief. Future research will focus on real-time price updates as matches conclude during a tournament.

Summary updated

Abstract

Computing the marketmaker price of a security in a combinatorial prediction market is #P-hard. We devise a fully polynomial randomized approximation scheme (FPRAS) that computes the price of any security in disjunctive normal form (DNF) within an e multiplicative error factor in time polynomial in 1/e and the size of the input, with high probability and under reasonable assumptions. Our algorithm is a Monte-Carlo technique based on importance sampling. The algorithm can also approximately price securities represented in conjunctive normal form (CNF) with additive error bounds. To illustrate the applicability of our algorithm, we show that many securities in Yahoo!'s popular combinatorial prediction market game called Predictalot can be represented by DNF formulas of polynomial size.
BibTeX
@inproceedings{xia2011efficient,
  author = {Lirong Xia and David M. Pennock},
  title = {{An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=Bkb0f4M_bS},
}
Figure