ICML 2012 Tutorial on Prediction, Belief, and Markets

Tuesday, June 26, Edinburgh

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 an assistant professor in the Computer Science Department at UCLA and an active member of the UCLA Center for Engineering Economics, Learning, and Networks. She completed her Ph.D. at the University of Pennsylvania in 2009, and subsequently spent a year as a Computing Innovation Fellow at Harvard. Her research interests are in machine learning, algorithmic economics, and social computing, all of which she studies using techniques from theoretical computer science. She is the recipient of Penn's 2009 Rubinoff dissertation award for innovative applications of computer technology, a National Science Foundation CAREER award, and best paper or best student paper awards at COLT, ACM EC, and UAI. In her "spare" time, she 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 will be held for the seventh time in 2012.

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:

tutorial_combined_shortened.pdf

Outline of Tutorial:

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
6. BREAK!!!!!!!!!!!!
7. Automated Market Makers
8. Beyond Complete Markets
9. Duality &  Connection to Online Learning
10. Some Additional Topics

Some Useful References:

NOTE: For a slightly longer and fresher list, see the page for our 2013 AAAI Tutorial.

1. Composite Binary Losses. Mark Reid and Bob Williamson, 2010.
2. Information, Divergence and Risk for Binary Experiments. Mark Reid and Bob Williamson, 2010.
3. Composite Multiclass Losses. Elodie Vernet, Bob Williamson, and Mark Reid, 2011.
4. Loss Functions for Binary Class Probability Estimation and Classification: Structure and Applications. Andreas Buja, Werner Stuetzle, and Yi Shen, 2005. 
5. A Utility Framework for Bounded-Loss Market Makers. Yiling Chen and Dave Pennock, 2007.
6. A new understanding of prediction markets via no-regret learning. Yiling Chen and  Jennifer Wortman Vaughan, 2010.
7. An Optimization-Based Framework for Automated Market-Making. Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan, 2011.
8. Liquidity-Sensitive Automated Market Makers via Homogeneous Risk Measures. Othman, A. and Sandholm, T., 2011. 
9. Logarithmic Market Scoring Rules for Modular Combinatorial Information Aggregation. Robin Hanson, 2007.
10. Combinatorial Information Market Design. Robin Hanson, 2003.
11. A Collaborative Mechanism for Crowdsourcing Prediction Problems. Jacob Abernethy and Rafael Frongillo, 2011.
12. A Characterization of Scoring Rules for Linear Properties. Jacob Abernethy and Rafael Frongillo, 2012.