Tractable market making in combinatorial prediction markets
Miroslav Dudik*07, Microsoft Research New York City
Prediction markets are emerging as a powerful and accurate method of
aggregating information from populations of experts (and non-experts).
Traders in prediction markets are incentivized to reveal their
information through buying and selling "securities" for events such as
"Romney to win Florida". The prices of securities reflect the aggregate belief
about the events and the key challenge is to correctly price the securities.
We present a new automated market maker for providing liquidity across
multiple logically interrelated securities. Our approach lies
somewhere between the industry standard---treating related securities
as independent and thus not transmitting any information from one
security to another---and a full combinatorial market maker for which
pricing is computationally intractable. Our market maker, based on
convex optimization and constraint generation, is tractable like
independent securities yet propagates some information among related
securities like a combinatorial market maker, resulting in more
complete information aggregation. Our techniques borrow heavily from
variational inference in exponential families. We prove several
favorable properties of our scheme and evaluate its information
aggregation performance on survey data involving hundreds of thousands
of complex predictions about the 2008 U.S. presidential election.
Joint work with Sebastien Lahaie and David Pennock.
Bio: Miroslav Dudik joined MSR-NYC in May 2012. His interests are in
combining theoretical and applied aspects of machine learning, statistics,
convex optimization and algorithms. He received his PhD from Princeton