An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments
David Pennock and Lirong Xia
Computing the market maker 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 popular securities in combinatorial prediction markets for tournaments can be represented by DNF formulas of polynomial size.