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&#8217-d like to highlight a couple of them:

1. &#8220-Are there less expressive bidding languages that admit polynomial matching algorithms yet are still practically useful and interesting?&#8221- 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.
2. The idea of betting on outcome permutations is intriguing. (Apparently I missed this paper at the recent conference in San Diego.)
3. &#8220-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?&#8221- I&#8217-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.
4. &#8220-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?&#8221- Wouldn&#8217-t proving incentive compatibility be sufficient to establish that rational agents would bid truthfully? I expect LMSR to be incentive compatible, though I don&#8217-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&#8217-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&#8217-s blog contains the password that you&#8217-ll need.)