Price Updating in Combinatorial Prediction Markets with Bayesian Networks

David M. Pennock, Lirong Xia
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:647-654, 2011.

Abstract

To overcome the #P-hardness of computing/updating prices in logarithm market scoring rule-based (LMSR-based) combinatorial prediction markets, Chen et al. [5] recently used a simple Bayesian network to represent the prices of securities in combinatorial predictionmarkets for tournaments, and showed that two types of popular securities are structure preserving. In this paper, we significantly extend this idea by employing Bayesian networks in general combinatorial prediction markets. We reveal a very natural connection between LMSR-based combinatorial prediction markets and probabilistic belief aggregation,which leads to a complete characterization of all structure preserving securities for decomposable network structures. Notably, the main results by Chen et al. [5] are corollaries of our characterization. We then prove that in order for a very basic set of securities to be structure preserving, the graph of the Bayesian network must be decomposable. We also discuss some approximation techniques for securities that are not structure preserving.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-pennock11a, title = {Price Updating in Combinatorial Prediction Markets with {B}ayesian Networks}, author = {Pennock, David M. and Xia, Lirong}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {647--654}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/pennock11a/pennock11a.pdf}, url = {https://proceedings.mlr.press/r9/pennock11a.html}, abstract = {To overcome the #P-hardness of computing/updating prices in logarithm market scoring rule-based (LMSR-based) combinatorial prediction markets, Chen et al. [5] recently used a simple Bayesian network to represent the prices of securities in combinatorial predictionmarkets for tournaments, and showed that two types of popular securities are structure preserving. In this paper, we significantly extend this idea by employing Bayesian networks in general combinatorial prediction markets. We reveal a very natural connection between LMSR-based combinatorial prediction markets and probabilistic belief aggregation,which leads to a complete characterization of all structure preserving securities for decomposable network structures. Notably, the main results by Chen et al. [5] are corollaries of our characterization. We then prove that in order for a very basic set of securities to be structure preserving, the graph of the Bayesian network must be decomposable. We also discuss some approximation techniques for securities that are not structure preserving.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Price Updating in Combinatorial Prediction Markets with Bayesian Networks %A David M. Pennock %A Lirong Xia %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-pennock11a %I PMLR %P 647--654 %U https://proceedings.mlr.press/r9/pennock11a.html %V R9 %X To overcome the #P-hardness of computing/updating prices in logarithm market scoring rule-based (LMSR-based) combinatorial prediction markets, Chen et al. [5] recently used a simple Bayesian network to represent the prices of securities in combinatorial predictionmarkets for tournaments, and showed that two types of popular securities are structure preserving. In this paper, we significantly extend this idea by employing Bayesian networks in general combinatorial prediction markets. We reveal a very natural connection between LMSR-based combinatorial prediction markets and probabilistic belief aggregation,which leads to a complete characterization of all structure preserving securities for decomposable network structures. Notably, the main results by Chen et al. [5] are corollaries of our characterization. We then prove that in order for a very basic set of securities to be structure preserving, the graph of the Bayesian network must be decomposable. We also discuss some approximation techniques for securities that are not structure preserving. %Z Reissued by PMLR on 04 October 2026.
APA
Pennock, D.M. & Xia, L.. (2011). Price Updating in Combinatorial Prediction Markets with Bayesian Networks. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:647-654 Available from https://proceedings.mlr.press/r9/pennock11a.html. Reissued by PMLR on 04 October 2026.

Related Material