As with all my handwritten notes, this has the usual disclaimer: these posts are just so I can use nice indexed search to easily search for my notes, which are sufficient for me to recall talks and papers but probably not much use to anyone else. Slides here
Relevant papers here, here, here, here, and here, and a nice blog post with well organized links here.
Situated in a de facto standard market maker mechanism, this talk presents some recent results on analyzing and designing prediction markets for information aggregation. We take both economic and computational perspectives. From the economic perspective, we engage game theoretic analysis to investigate the equilibrium behavior of informed traders in prediction markets. We examine what information structures lead to truthful play by traders, meaning that traders reveal all of their information honestly as soon as they are able, and when traders have an incentive to lie about their own information, with the intention to strategically mislead other traders and profit later by correcting their errors. From the computational perspective, we design expressive betting languages for combinatorial prediction markets and examine the computational problem of pricing such markets. In our combinatorial markets, traders can submit bets of the form “horse A finishes in position 1, 2, or 5”, “horse C beats horse D”, “a Democrat wins Ohio and Florida”, or “Duke wins a third round game in the NCAA basketball tournament”. We find that pricing such markets are computationally intractable except for the single-elimination tournament betting. This is the first example of a tractable market-maker driven combinatorial market. Joint work of Yilling Chen, Stanko Dimitrov, Lance Fortnow, Sharad Goel, Rica Gonen, Robin D. Hanson, Nicolas Lambert, David M. Pennock, Daniel M. Reeves, Rahul Sami, and Jennifer Wortman Vaughan.
Most betting markets, from Las Vegas to Wall Street, operate similarly: Each allowable bet is explicitly listed and tracked; each bet’s outcome space is low dimensional; and each bet type is managed independently. In this talk, I will survey our attempts to design combinatorial betting mechanisms that support doubly exponentially many allowable bets and propagate information appropriately across logically-related bets. Thus, our mechanisms have the potential to both collect more information and process that information more fully than standard mechanisms. The greater expressiveness comes at a computational cost for the auctioneer, who faces a difficult matching problem to connect up willing traders. In general, the auctioneer must consider complex multilateral matches and full expressiveness renders the matching problem intractable. However, in some cases we have discovered reasonable restrictions on expressiveness that admit polynomial-time matching algorithms.