Notes on Pennock, Combinatorial Betting (with Chen, Fortnow, Goel, Kilian, Lambert, Nikolova, Wellman, and Wortman)

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.

Advertisements
Notes on Pennock, Combinatorial Betting (with Chen, Fortnow, Goel, Kilian, Lambert, Nikolova, Wellman, and Wortman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s