A New Understanding of Prediction Markets Via No-Regret Learning

DSpace/Manakin Repository

A New Understanding of Prediction Markets Via No-Regret Learning

Citable link to this page


Title: A New Understanding of Prediction Markets Via No-Regret Learning
Author: Chen, Yiling; Wortman Vaughan, Jennifer

Note: Order does not necessarily reflect citation order of authors.

Citation: Yiling, Chen and Jennifer Wortman Vaughan. 2010. A new understanding of prediction markets via no-regret learning. In 11th ACM Conference on Electronic Commerce: June 7-11, 2010, Cambridge, MA, 189-198. New York, NY: Association for Computing Machinery.
Full Text & Related Files:
Abstract: We explore the striking mathematical connections that exist between market scoring rules, cost function based prediction markets, and no-regret learning. We first show that any cost function based prediction market can be interpreted as an algorithm for the commonly studied problem of learning from expert advice by equating the set of outcomes on which bets are placed in the market with the set of experts in the learning setting, and equating trades made in the market with losses observed by the learning algorithm. If the loss of the market organizer is bounded, this bound can be used to derive an \(O( \sqrt T)\) regret bound for the corresponding learning algorithm. We then show that the class of markets with convex cost functions exactly corresponds to the class of Follow the Regularized Leader learning algorithms, with the choice of a cost function in the market corresponding to the choice of a regularizer in the learning problem. Finally, we show an equivalence between market scoring rules and prediction markets with convex cost functions. This implies both that any market scoring rule can be implemented as a cost function based market maker, and that market scoring rules can be interpreted naturally as Follow the Regularized Leader algorithms. These connections provide new insight into how it is that commonly studied markets, such as the Logarithmic Market Scoring Rule, can aggregate opinions into accurate estimates of the likelihood of future events.
Published Version: doi:10.1145/1807342.1807372
Other Sources: http://arxiv.org/abs/1003.0034
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:8896228
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search