Events Calendar

An Optimization-Based Framework for Automated Market-Making

Speaker: Prof. Jenn Wortman Vaughan , UCLA

Talk Title: An Optimization-Based Framework for Automated Market-Making

Abstract: A prediction market is a financial market designed to aggregate information. To facilitate trades, prediction markets are often operated by automated market makers. The market maker trades a set of securities with payoffs that depend on the outcome of a future event. For example, the market maker might offer a security that will pay off $1 if and only if a Democrat wins the 2012 presidential election. A risk neutral trader who believes that the probability of a Democrat winning is p should be willing to purchase this security at any price below p, or sell it at any price above p. The current market price can then be viewed as the traders? collective estimate of how likely it is that a Democrat will win the election.

Market-based estimates have proved to be accurate in a variety of domains, including business, entertainment, and politics. However, when the number of outcomes is very large, it is generally infeasible to run a simple prediction market over the full outcome space. There has been a surge of recent research examining the tractability of running standard prediction market mechanisms (such as the popular Logarithmic Market Scoring Rule) over combinatorial outcome spaces by limiting the space of available securities. While this line of research has led to a few positive results, it has led more often to hardness results or to markets with undesirable properties such as unbounded worst case market maker loss.

We take a different approach. Building on ideas from convex optimization, we propose a general framework for the design of efficient prediction market mechanisms over very large or infinite outcome spaces. We start with an arbitrary space of securities with bounded payoff, and establish a framework to design markets tailored to this space. We prove that any market satisfying a set of intuitive conditions must price securities via a convex potential function and that the space of reachable prices must be precisely the convex hull of the security payoffs. We then show how the convex potential function can be defined in terms of an optimization over the convex hull of the security payoffs. The solution to the optimization problem gives the security prices. Using this framework, we provide an efficient prediction market mechanism for predicting the landing location of an object on a sphere. In addition, we show that we can relax our "no-arbitrage" condition to design a new eff icient market maker for "pair betting" on rank orderings, which is known to be #P-hard to price using existing mechanisms. This relaxation also allows the market maker to charge transaction fees so that the depth of the market can be dynamically increased as the number of trades increases.

This talk is based on joint work with Jake Abernethy and Yiling Chen.


Biography: Jenn Wortman Vaughan is an assistant professor in the Computer Science Department at UCLA. She completed her Ph.D. at the University of Pennsylvania in 2009. Before arriving at UCLA, she spent a year as a Computing Innovation Fellow at Harvard. Her research interests are in machine learning, algorithmic economics, social computing, 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 was held for the fifth time this year.

Host: Prof. David Kempe

Location: Hedco Neurosciences Building (HNB) - Auditorium

Audiences: Everyone Is Invited

Contact: Kanak Agrawal