AAAI 2013 Tutorial on Prediction, Belief, and Markets

Sunday, July 24, 2-6pm, Bellevue, WA

Overview:

Prediction markets are financial markets designed to aggregate opinions across large populations of traders. A typical prediction market offers a set of securities with payoffs determined by the future state of the world. For example, a market might offer a security worth $1 if Barack Obama is re-elected in 2012 and $0 otherwise. Roughly speaking, a trader who believes the probability of Obama's re-election is p should be willing to buy this security at any price less than $p and (short) sell this security at any price greater than $p. For this reason, the going price of this security could be interpreted as traders' collective belief about the likelihood of Obama's re-election. Prediction markets have been used to generate accurate forecasts in a variety of domains including politics, disease surveillance, business, and entertainment, and are cited in the media increasingly often.

This tutorial will cover some of the basic mathematical ideas used in the design of prediction markets, and illustrate several fundamental connections between these ideas and techniques used in machine learning.  We will begin with an overview of proper scoring rules, which can be used to measure the accuracy of a single entity's prediction, and are closely related to proper loss functions. We will then discuss market scoring rules, automated market makers based on proper scoring rules which can be used to aggregate the predictions of many forecasters, and describe how market scoring rules can be implemented as inventory-based markets in which securities are bought and sold. We will describe recent research exploring a duality-based interpretation of market scoring rules which can be exploited to design new markets that can be run efficiently over very large state spaces. Finally, we will explore the fundamental mathematical connections between market scoring rules and two areas of machine learning: online "no-regret" learning and variational inference with exponential families.

This tutorial will be self-contained. No background on markets or specific areas of machine learning is required.

Presenter Bios:

Jenn Wortman Vaughan is a Researcher at Microsoft Research, New York City, where she studies algorithmic economics, market design, machine learning, and social computing, using techniques from theoretical computer science, optimization, and probability theory. Jenn came to MSR in 2012 from UCLA, where she was an assistant professor in the computer science department. She completed her Ph.D. at the University of Pennsylvania in 2009, and subsequently spent a year as a Computing Innovation Fellow at Harvard. She is the recipient of Penn's 2009 Rubinoff dissertation award for innovative applications of computer technology, a National Science Foundation CAREER award, a Presidential Early Career Award for Scientists and Engineers, and best paper or best student paper awards at COLT, ACM EC, and UAI. In her "spare" time, Jenn is involved in a variety of efforts to provide support for women in computer science; most notably, she co-founded the Annual Workshop for Women in Machine Learning, which has been held each year since 2006.

Jacob Abernethy is the Simons Postdoctoral Fellow at the University of Pennsylvania, Department of Computer and Information Science, and is hosted by Professor Michael Kearns. In December 2011, he completed his PhD at the University of California, Berkeley, having been advised by Professor Peter Bartlett. Jacob's thesis focused on the problem of online learning in non-stochastic environments, and much of his research has been concerned with the relationship between learning and game theory. He has done recent work in designing combinatorial information markets, the pricing of financial derivatives, and optimizing efficiency in crowdsourcing platforms.

Tutorial Slides:

prediction_belief_and_markets.pdf

Tentative Outline of Tutorial:

Part 1:

1. Introduction
2. Prediction Markets in Practice: Work Well?
3. Proper Scoring Rules and Eliciting Beliefs
4. Bregman Divergences + Proper Scoring Rules
5. Hanson’s Market Scoring Rule

Part 2:

1. Automated Market Makers
2. Beyond Complete Markets
3. Duality &  Connection to Online Learning
4. Some Extensions and Additional Topics

Some Useful References:

(not meant to be complete)

Misc. Links:

1. Probability and Finance, It's Only a Game! by Glenn Shafer and Vladimir Vovk 
2. The Emergence of Probability by Ian Hacking 
3. Noahpinion: Bets do not (necessarily) reveal beliefs 
4. When the Crowd Isn't Wise, post by David Leonhardt at NYTimes, and a counterpoint by Robin Hanson 
5. Whatever Happened to Intrade? by John Cassidy at The New Yorker
6. Questions Surround Millions InTrade Paid CEO at Time of His Everest Death by Philip Bump at The Atlanta
7. Predictious, the new bitcoin-based prediction market 

Proper Losses and Scoring Rules:

1. Strictly Proper Scoring Rules, Prediction, and Estimation. Tilmann Gneiting and Adrian E. Raftery, 2005.
2. Composite Binary Losses. Mark Reid and Bob Williamson, 2010.
3. Information, Divergence and Risk for Binary Experiments. Mark Reid and Bob Williamson, 2010.
4. Composite Multiclass Losses. Elodie Vernet, Bob Williamson, and Mark Reid, 2011.
5. Loss Functions for Binary Class Probability Estimation and Classification: Structure and Applications. Andreas Buja, Werner Stuetzle, and Yi Shen, 2005. 
6. A Characterization of Scoring Rules for Linear Properties. Jacob Abernethy and Rafael Frongillo, 2012.

Market Scoring Rules and Automated Market Makers:

1. Combinatorial Information Market Design. Robin Hanson, 2003.
2. Logarithmic Market Scoring Rules for Modular Combinatorial Information Aggregation. Robin Hanson, 2007.
3. A Utility Framework for Bounded-Loss Market Makers. Yiling Chen and Dave Pennock, 2007.
4. Complexity of Combinatorial Market Makers. Yiling Chen, Lance Fortnow, Nicolas Lambert, David Pennock, and Jennifer Wortman, 2008.
5. A New Understanding of Prediction Markets Via No-Regret Learning. Yiling Chen and  Jennifer Wortman Vaughan, 2010.
6. An Optimization-Based Framework for Automated Market-Making. Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan, 2011.
7. Efficient Market Making via Convex Optimization, and a Connection to Online Learning. Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan, 2013.
8. A Collaborative Mechanism for Crowdsourcing Prediction Problems. Jacob Abernethy and Rafael Frongillo, 2011.
9. An Axiomatic Characterization of Adaptive-Liquidity Market Makers. Xiaolong Li and Jennifer Wortman Vaughan, 2013.
10. Liquidity-Sensitive Automated Market Makers via Homogeneous Risk Measures. Abe Othman and Tuomas Sandholm, 2011.
11. A Tractable Combinatorial Market Maker Using Constraint Generation. Miro Dudík, Sebastien Lahaie and David Pennock, 2012.
12. A Combinatorial Prediction Market for the U.S. Elections. Miro Dudík, Sebastien Lahaie, David Pennock, and David Rothschild, 2012.
13. Cost Function Market Makers for Measurable Spaces. Yiling Chen, Michael Ruberry, and Jennifer Wortman Vaughan, 2013.
14. Information Aggregation in Dynamic Markets with Strategic Traders. Michael Ostrovsky, 2012.
15. Belief Aggregation with Automated Market Makers. Rajiv Sethi and Jennifer Wortman Vaughan, 2013.