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

Xia, Lirong; Pennock, David M.

doi:10.5591/978-1-57735-516-8/IJCAI11-083

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

Lirong Xia, David M. Pennock

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 452-456.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-083

Abstract

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 ε multiplicative error factor in time polynomial in 1ε 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.

Lirong Xia, and David M. Pennock. 2011. An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 452–456. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-083

@inproceedings{ijcai2011p83,
  title     = {An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments},
  author    = {Xia, Lirong and Pennock, David M.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {452--456},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-083},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-083},
}

TY  - CPAPER
TI  - An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments
AU  - Xia, Lirong
AU  - Pennock, David M.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 452
EP  - 456
DO  - 10.5591/978-1-57735-516-8/IJCAI11-083
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-083
ER  -