Jenn Wortman Vaughan: "A New Understanding of Prediction Markets Via No-Regret Learning"

Date: 

Wednesday, April 21, 2010, 11:45am to 1:00pm

Location: 

Maxwell Dworkin G135

CRCS Lunch Seminar

Date: Wednesday, April 21, 2010
Time: 11:45am – 1:00pm
Place: Maxwell Dworkin G135

Speakers:  Jenn Wortman Vaughan

Title: A New Understanding of Prediction Markets Via No-Regret Learning

Abstract:  Suppose that you are interested in estimating the probability that Google will reinstate its Chinese search engine within the next two years. You might choose to spend hours digging through news articles, reading commentaries, and weighing various opinions against each other, eventually coming up with a reasonably well-informed guess. But you might be able to save yourself a lot of hassle (and potentially obtain a better estimate) by appealing to the wisdom of crowds.

A prediction market is a financial market designed to aggregate information. A typical binary prediction market allows bets along a single dimension, for example, for or against Google reinstating its Chinese search engine by the end of 2011. In this case, bettors might trade securities that pay $1 if and only if Google moves back to China by the specified date. If the current market price of a share of this security is $p, then a rational, risk-neutral bettor should be willing to buy shares if he believes the true probability is greater than p. Conversely, he should be willing to sell shares if he believes the true probability is lower. In this sense, the current price per share provides an estimate of the population’s collective belief about how likely it is that Google will reinstate its search engine.

These estimates have proved quite accurate in practice in a wide variety of domains. Equilibrium theory offers some insight into why prediction markets should converge to accurate prices, but is plagued by strong assumptions and no-trade theorems. Furthermore, this theory says nothing of why particular prediction market mechanisms, such as Hanson’s increasingly popular Logarithmic Market Scoring Rule, might produce more accurate estimates than others in practice. In this talk, I will describe some recent work aimed at understanding the learning power of particular market mechanisms by examining the deep mathematical connections that exist between prediction market mechanisms and common algorithms for “no-regret” learning. I will then describe how this synergy between prediction markets and machine learning can be leveraged to run an efficient market when the space of possible outcomes is complex.

This talk is based primarily on joint work with Yiling Chen. It additionally includes ideas from earlier work with Lance Fortnow, Nicolas Lambert, and David Pennock.

Bio: Jenn Wortman Vaughan is a Computing Innovation Fellow at Harvard University. She completed her Ph.D. at the University of Pennsylvania in 2009. Her research interests are in machine learning, computational aspects of economics, social network theory, and algorithms, all of which she studies using techniques from theoretical computer science. Her recent research has won several best student paper awards, as well as Penn’s 2009 Rubinoff dissertation award for innovative applications of computer technology. 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 fifth time this year. In the fall, Jenn will join the Computer Science Department at UCLA as an assistant professor.

http://people.seas.harvard.edu/~jenn/