Rahul Sami and I wrote a chapter called “Computational aspects of prediction markets” in the book Algorithmic Game Theory, Cambridge University Press, forthcoming 2007.

You can download an almost-final version of our chapter here.

Update 2007/09/19: You can now also download the entire book Algorithmic Game Theory: username agt1user , password camb2agt . If you like it, you can buy it.

In the course of writing the chapter, we compiled an extended annotated bibliography that ended up being too long to publish in its entirety in the book. So we trimmed the bibliographic notes in the book to cover only the most directly relevant citations. You can download the full extended bibliography here.

Here is the abstract of our chapter:

Prediction markets (also known as information markets) are markets established to aggregate knowledge and opinions about the likelihood of future events. This chapter is intended to give an overview of the current research on computational aspects of these markets. We begin with a brief survey of prediction market research, and then give a more detailed description of models and results in three areas: the computational complexity of operating markets for combinatorial events; the design of automated market makers; and the analysis of the computational power and speed of a market as an aggregation tool. We conclude with a discussion of open problems and directions for future research.

If you’re interested in this topic, you might also take a look at our recent paper on Betting on permutations, published after the book chapter was completed.

Finally, for a higher-level treatment, here is a pre-print version of a short letter on “Combinatorial betting” that we submitted to SIGecom Exchanges.