Prediction Market PowWow at Yahoo! Research NYC Aug 24-26 2011
…was a largely unstructured gathering (think foo camp or unconference) to discuss prediction market research, mostly algorithms. One goal was to compile a list of interesting open problems (which we’ve put here http://doc.bmndr.co/pmop ) and start tackling one or more.
There was no powerpoint, only whiteboard. Hooray!
There was also dinner. And champagne (boy, was there champagne!).
Attendees: * Visitors * Yiling Chen (Harvard) * Sanmay Das (RPI) * Lance Fortnow (Northwestern) * Nicolas Lambert (Stanford) * Abe Othman (CMU) * Mike Ruberry (Harvard) * Rahul Sami (U Michigan) * Florian Teschner (KIT.edu) * Jenn Wortman Vaughn (UCLA) * Christof Weinhardt (KIT.edu) * Lirong Xia (Duke —> Harvard) * Yahoos * Miro Dudik * Sebastien Lahaie * David Pennock * David Rothschild
======
David R., Florian, & Christof: Wizard interfaces for prediction markets + polls vs markets
Sebastien & Miro: Leveraging optimization and learning for market maker algorithms
Building on Jake, Yiling, and Jenn’s optimization framework paper, one idea is to add constraints to the optimization whenever a user creates a new security. If you look at the dual of the optimization problem, then it’s clear that a market maker without constraints is like independent markets for every security, and constraints play the role of finding and fixing arbitrage between the securities. Also in the dual, errors in the cost function are always overestimates, so safe in the aggregate for the market maker. Another part of the proposal is to run an MCMC sampling algorithm in parallel in the background for: (1) setting the prior on a new security, and (2) computing the probability of arbitrary propositions for researching offline when pricing need not be so fast.
We discussed two aspects of the manipulation problem: detection of manipulation, and reducing incentives for manipulation. For detection in lab experiments, we can identify cases in which traders obviously trade against their own information, but detection is harder in the field. David R. briefly described some techniques that he and Justin Wolfers had used to infer manipulation in Intrade markets; looking at price differentials with similar markets, and using the timing of trades to differentiate between rational hedging and trades to maximize the impact on price. For reducing incentives to trade, in situations where traders have an impact on prices, Sanmay described markets he is running in which traders also vote on the outcome. We discussed the possibility of using a different outcome to score each trader (trader i’s outcome cannot be influenced by trader i’s vote), as well as splitting the trader pool into two groups that each determine the other’s outcome. The latter seems to have better protection against arbitrage.
Many of the automated market makers including LMSR can be seen as agents seeking to maintain a constant utility (Chen & Pennock, UAI 2007). To recover LMSR, the utility function is negative exponential. In the case, worst-case loss grows as O(log n) where n is the number of outcomes. If instead, you use log utility, or any “barrier function” where utility goes to negative infinity as wealth goes to zero, then the market maker will have constant bounded utility that does not depend on the number of outcomes. This opens up the possibility of operated bounded-loss market makers on countably infinite or even continuous outcome spaces. Abe develops this theory and also shows how to create a market maker that can slowly ramp up liquidiy so that the bid-ask spread tends toward zero, while still maintaining bounded loss, or even guaranteeing a profit after a certain “point of no return” is reached. This is work based on Abe’s paper with Tuomas at AMMA 2011: http://www.cs.cmu.edu/~aothman/opens.pdf
Mike presented his paper with Yiling and others at Harvard on decision markets. If the decision maker always chooses the best option, and traders know it, then there can be an incentive for traders to misrepresent which option is best to gain more. If the decision maker always chooses an option uniformly at random, then incentives are correct but the whole point of a decision market is gone. Mike shows that the decision maker can choose at random with high weight on the better options and minscule weight on bad options, but then the scoring rule for each conditional market has to be scaled accordingly, paying more in low-probability conditions. Then traders are again incented to be truthful. They also show an equivalence of sorts to combinatorial prediction markets. Based on this paper: http://people.seas.harvard.edu/~mruberry/WINE2011dmwgi.pdf
======
Rahul showed how a market maker algorithm can be used as a black box inside an experts online learning problem to gain some nice robustness properties that previous experts algorithms don’t have. Assume experts, some honest http://www.cs.umass.edu/~wallach/workshops/nips2010css/papers/kutty.pdf. The regret bounds are in a forthcoming manuscript.
This is an open problem we toyed with all three days and have been for years that seems deceptively simply yet remains elusive. Is there a prediction market maker in a two-dimensional “expectation market” where the goal is to predict the expected location on a grid (think of a square dart board) and where if the trader is budget-constrained, his/her best action is to move the price in a straight line toward his/her expected (x,y), rather than first move in the direction that’s the furthest off (i.e., move in the x direction if |p_x - E[x]| > |p_y - E[y]|).
Sebastien described his discovery that cost-function based market makers are closely related to exponential family distributions in the statistics literature. This enables a very general framework for creating market makers that operate on almost any outcome space of any structure. The market maker can support bets on properties of distributions rather than outcomes if preferred, and by the nature of exponential family distributions, the “missing” information will be inferred via maximum etropy. The connection also makes it very easy to derive scoring rules for almost any distribution. In particular, Sebasiten derived a two-dimensional scoring rule that elicits mean and variance simultaneously rather than independently, something previously conjectured but undiscovered, and related to Nicolas’s elicitation complexity paper.
Lance described his Econometrica paper with Rakesh on expert testing. The setting is a single expert who is being judged on his/her forecast accuracy by a tester. (While scoring rules are able to distinguish the accuracy of any two forecasters, they do not necessarily work for deciding whether a single forecaster is informed or not.) The tester wants an algorithm that always passes “the truth”, or an expert who knows and honestly reports the actual true underlying probability distribution. At the same time, the tester wants to never (or rarely) pass an uninformed expert who knows nothing about the true probability distribution and is simply trying to fool the tester. For example, a naive calibration test will always pass the truth but can also be easily fooled. A previous paper showed that any test that passes the truth can also be fooled. But Lance and Rakesh show that if the manipulator is computationally bounded, then he/she cannot fool the tester. Based on this paper: http://www.cs.uchicago.edu/~fortnow/papers/forecast.pdf
======
Sampling algorithms: Sampling approximations of LMSR are hard because of the exponential dependene on q: The price of an outcome is proportional to e^q, so to determine the price of an event (set of outcomes) it’s vital to find the max q, a cmputationally difficult problem.
Approximating the convex optimization approach:
Expectation markets:
Lirong described his UAI 2011 paper that is a generalization of our previous “tournament betting” paper in STOC 2008. The setting is a combinatorial prediction market with discrete outcomes. A natural example is a sports tournament where there are n teams that play n-1 games in a single-elimination tournament, so there are 2^(n-1) total possible outcomes, or complete unfoldings of the tournament. (Another natural example is the US Presidential election where there are 50 states that can each be won by either Obama or the Republican challenger, so there are 2^50 outcomes.) Lirong shows that if an LMSR market maker has current price distribution p and accepts a new bet, then the new price distribution can be computed as the LogOP (a multiplicative average) of the old p and a certain representation of the bet. Moreover, if the old p is represented as a decomposable Bayesian network, and the bet is “stucture preserving”, then the new p can be represented by the same network structure, without adding links, thus maintaining a compact representation and computational tractability. Lirong shows that if you want bets on marginals to be structure preserving, then “LMSR-like” market makers are essentially the only market makers you can use. Lirong characterizes all the structure-preserving bets for LMSR. Roughly, any bet that is a conjunction of variables in a clique in the Bayes net is structure preserving. Based on this paper: http://people.seas.harvard.edu/~lxia/index.htm
We discussed how to modify and where to submit our EC paper on “betting with budgets”.
== THE END =============================================
Old planning discussion: I (Yiling) would like to hear some of the work on market-inspired learning that Rahul and Sebastien independently work on, if it’s in a talkable stage. An informal whiteboard talk would be good.