Dave Pennock and Rahul Sami have written a book chapter on Computational Aspects of Prediction Markets. It focuses on computability and complexity issues in markets that handle combination, conditional and compound orders. The article talks about the costs for the auctioneer, and presents the Logarithmic Market Scoring Rule and the Dynamic Parimutuel Auction as two feasible approaches to offering combination or compound markets.

The article is written for (and probably only accessible to) people who understand the language of computability and complexity theory. It does review the economic principles underlying prediction market mechanisms beyond call auctions and the double auction, but only sufficiently to introduce them to Computer Science people who are new to this application area.

The chapter closes with a list of open questions, and I’-d like to highlight a couple of them:

- “-Are there less expressive bidding languages that admit polynomial matching algorithms yet are still practically useful and interesting?”-
**If someone can find a feasible mechanism that supports an interesting subset of a complete combinatorial or conditional claims, we could run markets that provide answers to much more interesting questions.** - The idea of betting on outcome permutations is intriguing. (Apparently I missed this paper at the recent conference in San Diego.)
- “-What is the complexity of finding a match between a single new order and a set of old orders known to have no matches among them?”- I’-m more interested in finding cheap solutions or new ways to pose the problem that are more tractable, but determining the complexity is the first step in the crowd Sami and Pennock are talking to.
- “-The model in Section 1.5 directly assumes that agents bid truthfully. Is there a tractable model that assumes only rationality and solves for the resulting game-theoretic solution strategy?”-
**Wouldn’-t proving incentive compatibility be sufficient to establish that rational agents would bid truthfully?**I expect LMSR to be incentive compatible, though I don’-t know how hard the proof is. I have a vaguer feeling that the Dynamic Parimutuel might also be incentive compatible, though I think the fact that the price isn’-t directly a probability makes the link more tenuous.

I hope the inclusion of this chapter in what appears to be a broad work on computability, efficiency, and algorithm design in games, negotiations, markets, and networks will lead to new ideas that will expand the set of alternative market designs we can make use of. (I have linked to the chapter above- if you want to download the whole book, Pennock’-s blog contains the password that you’-ll need.)

Thanks for excerpting, reviewing and linking to this Pennock paper. Maybe mister Pennock will come on MO talking a bit about his paper.

(((I’m checking “Notify me of follow-up comments via e-mail” so I will received the other comments in my e-mail inbox.)))

Chris M: Thanks for the prompt: I plan to.

Chris H: Thanks for the swift and very insightful review. As for #4, yes proving incentive compatibility would be sufficient. Although there is a difference between myopic incentive compatibility (analyzing a single trade — LMSR is indeed mypoically incentive compatible) and overall incentive compatibility, which is much harder to acheive and analyze. We have some results on overall incentive compatibility for LMSR and DPM which will be published at the Workshop On Internet And Network Economics (WINE 2007):

http://www.math.ucsd.edu/~wawn…..index.html

In general, neither LMSR or DPM are overall incentive compatible in every situation. However, for LMSR we identify a set of situations where it is overall incentive compatible.