[Cross-posted from Pancrit.org.]
Dave Pennock gave a gentle introduction to the Market Scoring Rule invented by Robin Hanson. In the comments, Sid asked for an explanation of how to integrate the MSR with an order book. Dave asked me privately if I’-d be willing to tackle that, and this post is the result. Robin’-s short note on integrating an order book and a market maker covers a lot of territory very quickly. In Robin’-s defense, it was written to clarify some ideas in the midst of a conversation we were having at the time, and hasn’-t been cleaned up for publication. I’-ll expand on it here so it has a chance of making sense to others. The paper couches things in terms of the MSR, a particular AMM, but none of the implementation depends on which AMM is used.
There’-s a working example of the integration we’-re talking about in the code for Zocalo. The code that does this is currently in transition since I’-m adding support for multi-outcome markets. For the moment, I recommend reading the code for version 375, since the current code is more complex and possibly incomplete. You can either download the complete source code for release 2006.5 of the Zocalo Prediction Market, or browse the code directly using the SVN interface.
The paper starts by giving a very compressed introduction to the idea of a prediction market and market maker (hereafter AMM for Automated Market Maker). Unless you’-re very familiar with the details and the formalisms that Robin uses to describe them, you’-d be better off reading the original papers (Logarithmic Market Scoring Rules, Combinatorial Information Market Design) than trying to pick anything up from the first four paragraphs of the note.
The fourth paragraph slips into the idea of integrating an order book with the AMM he’-s talked about to that point. (”-If instead [the AMM price resulting from buying the entire quantity is higher than the user’s max marginal price], a portion […] could be traded with the market maker, leaving a book order for the remaining quantity”-). From that point, he talks about how to integrate the two markets.
If new orders get the advantage of any order price overlap
In book order systems, if orders arrive asynchronously, you will often see orders that “-overlap”-, i.e. orders to buy at a higher price than the best offer to sell, or orders to sell lower than the best offer to buy. The system has to have policy about what price to transact at in these cases. The system could tell each party that they got the price they requested, and pocket the difference- it could use the book order’-s price or the new offer’-s price- or it could split the difference in the interest of fairness. If any choice is made other than using the stated price of the order in the book, investors have an incentive to carefully submit bids a little at a time (aka “-structure”- their bids) so they won’-t pay more than they have to if new orders should arrive. Robin argued elsewhere (I can’-t find the reference at the moment) that you should just transact at the book order price so that people submitting market price orders don’-t waste their resources and yours on this optimization.
That choice also simplifies the calculation for accepting new offers. As Robin says, “-each book order […] imposes a constraint on the market maker price”-. The AMM should fulfill orders up to that limit, then let trade continue with the book order. This requires a loop, in which you buy from the AMM until you reach the limit imposed by the best order(s), then trade up to the book order’-s available quantity, then go back to the AMM until you reach the next book order. You can see the approach in Zocalo’-s method Market.buyFromBothBookAndMaker(…-). (The method starts at line 237.)
At every step,
- find the remaining quantity q of the new order
- find the price p available from the best existing order
- if the AMM’-s price is no better than the book order, trade up to q with the book
- otherwise trade with the AMM to the lesser of p or q
The loop stops either when the new order is fulfilled or the price limit specified by the new order is reached.
That’-s the simple version for a one-dimensional AMM. The multi-dimensional version arises if you implement the AMM as described in “-Combinatorial Information Market Design”-. There are two open source implementations of this approach available for reading by hard-core hackers. Robin built an implementation in Lisp, and I wrote a version in E. Neither is more than a demonstration of how the market engine works, since no serious user interface was written for either one.
Rather than attempt to explain how the approach translates to the multi-dimensional case now, I’-d prefer to wait until after I write an explanation of the n-dimensional combination market, and that depends on a gentle introduction to conditional and combinatorial betting which I haven’-t written yet. Having someone ask about Robin’-s note raises my priority for writing these prerequisites.
Other Articles in this series
- PM intro: basic formats (2005-12-30)
- PMs with Open-ended Prices (2006-01-05)
- Looking at Both Sides (2006-04-17)
- Book and Market Maker (2006-04-28)
- Liquidity in N-Way claims (2006-07-19)
- Continuous Outcomes using Bands and Ladders (2006-09-20)