Robin Hanson invented a wonderful market maker well suited for use in prediction market applications with a long name: the logarithmic market scoring rule market maker, which I’ll abbreviate as LMSR. (In fact, Hanson invented an entire class of market scoring rule market makers, but the logarithmic variant seems the most useful.) Hanson’s two papers on the subject are excellent, but Hanson does not spend a lot of time explaining how LMSR functions as a market maker in the typical sense. Instead, Hanson mostly emphasizes a second, alternate way of thinking about his market maker, as a “sequential shared scoring rule”, which I will not try to explain here. Hanson prefers to describe trader behavior in terms of “changing the price” instead of “buying and selling shares”. In my opinion, most people who encounter LMSR for the first time don’t quite see how beautifully and naturally LSMR can be used as a market maker in a standard prediction market setting. In fact, I am embarrassed to admit that upon my own first reading of Hanson’s papers, I did not fully “get it”. It took my seeing LMSR implemented in practice, by Todd Proebsting at Microsoft Research for Microsoft’s internal prediction markets, to realize how elegantly LMSR can be used as a market maker in an otherwise typical prediction market. LMSR is now being used in several places, including an implementation at InklingMarkets with a wonderfully intuitive interface, the Washington Stock Exchange, BizPredict, and (reportedly) at YooNew. Net Exchange was one of the first to use LMSR, though they seem to favor Hanson’s “change the price” interface over the more widespread “buy and sell shares” interface. As Chris Masse is quick to point out, LMSR has achieved much more widespread use than my own competing invention, the dynamic parimutuel market maker, which so far is being used in only one place: our own Yahoo! Tech Buzz Game.
In this post I will try to explain how to implement LMSR in a way that I believe most people familiar with prediction markets will understand. This interpretation of LMSR is not new: it’s the way Proebsting thinks about LMSR and it’s implicit “between the lines” in Hanson’s papers. But I haven’t seen this interpretation of LMSR written up anywhere, so I’m hoping that others can benefit from this explanation. The following understanding of LMSR was developed over the past few months together with my colleague Yiling Chen.
Suppose there are two outcomes that traders can buy or sell shares of (bet on or against) such that one and only one of the two outcomes is guaranteed to eventually occur. For example, the two outcomes could be “a Democrat wins the 2008 US Presidential election” and “a Democrat does not win the 2008 US Presidential election”. Each share is worth exactly $1 if and only if the trader is correct. In other words, one share of “Democrat wins” pays $1 if, in 2008, a Democrat actually wins the election, and is worthless otherwise. The following description can be easily generalized to any number of (disjoint and exhaustive) outcomes, including the case of combinatorial markets, but for ease of exposition I’ll stick to the two-outcome case.
The market maker keeps track of how many shares have been purchased by traders in total so far for each outcome: that is, the number of shares outstanding for each outcome. Let q1 and q2 be the number (“quantity”) of shares outstanding for each of the two outcomes. The market maker also maintains a cost function C(q1,q2) which records how much money traders have collectively spent so far, and depends only on the number of shares outstanding, q1 and q2. For LMSR, the cost function is:
where “ln” is the natural logarithm function, “e” is the constant e=2.718…, and “b” is a parameter that the market maker must choose. The parameter “b” controls the maximum possible amount of money the market maker can lose (which happens to be b*ln2 in the two-outcome case). The larger “b” is, the more money the market maker can lose. But a larger “b” also means the market has more liquidity or depth, meaning that traders can buy more shares at or near the current price without causing massive price swings.
Traders arrive one at a time and tell the market maker how many shares they want to buy or sell of each outcome. Traders say, for example, “I want to buy 13 shares of outcome 1 — how much will that cost?”, or “I want to sell 250 shares of outcome 2 — how much will you pay me?”. The market maker uses the cost function to answer these questions. The cost to buy 13 shares of outcome 1 is simply C(q1+13,q2) – C(q1,q2). The “cost” to sell 250 shares of outcome 2 is C(q1,q2-250) – C(q1,q2), which will be a negative number (negative cost), meaning that the seller receives money in return for the shares. In general, if a trader wants to buy or sell shares of either or both outcomes so as to change the number of shares outstanding from (q1,q2) to (q1*,q2*), then he or she must pay C(q1*,q2*) – C(q1,q2) dollars. If this amount is negative it means the trader receives money instead of paying money.
Here’s a simple example. Suppose b=100 and no one has purchased any shares yet, so q1=q2=0. A trader arrives who wants to buy 10 shares of outcome 1. The trader must pay:
Now suppose that at some time later, the number of shares outstanding for outcome 1 is q1=50 and the number of shares outstanding of outcome 2 is q2=10. Now the same trader above returns to the market and wants to sell her 10 shares. The trader’s “payment” is:
This is a negative number so it means the trader receives $5.87. So in the end the trader made a round-trip profit of $0.75.
That’s it! Well, almost. If the market maker wants to quote a “current price”, he can. The current price for outcome 1 is:
and similarly for price2. But note that the current price only applies for buying a miniscule (infinitesimal, in fact) number of shares. As soon as a trader starts buying, the price immediately starts going up. In order to figure out the total cost for buying some number of shares, we should use the cost function C, not the price function. (If you remember your calculus: The total cost for buying k of shares of outcome 1 is the integral of the price function from q1 to q1+k. The price function (“price1”) is the derivative of the cost function C with respect to q1, and the cost function is the integral of the price function.)
Finally, although I won’t go into the details here, one can generalize the above so that the market maker can handle limit orders, for example an order to “buy up to 100 shares of outcome 1, each at price less than or equal to $0.80”. But if unfilled limit orders like this are allowed to persist, the market maker logic can get a little complicated.
As I mentioned, Hanson actually invented an entire class of market makers: he shows how to turn any proper scoring rule into a market maker. Yiling Chen and I have derived the cost and price functions corresponding to the quadratic scoring rule. It turns out, however, that the quadratic scoring rule market maker is not very interesting or useful in practice. I’ll save the details for another day. We’re also working on additional classes of market makers that do seem useful, results we hope to report on soon [update: see our paper “A utility framework for bounded-loss market makers”].
I think it is easy to make an imitation to win the game. I’d played this kind of games, e.g. inklingmarkets, which mentioned in this article, and gotted the week-top-1, only spending half hours. I believe that a wonderful market maker should be robust to prevent the users to play tricks and cheat the market maker to win the game.
I’m also embarrassed to confess my late understanding of Hanson’s market scoring rule market maker. What’s more, I strongly agree that the hereby proposed view of Hanson’s valuable mechanism is a much more tangible one.
Thanks George — glad it was useful.
People who are familiar with ordinary financial markets are often the most enthusiastic players in prediction markets, and yes they prefer an interface expressed in terms of quantities to trade. But I still think that for most people the most robust interface is one that asks them for their opinion on a subject, and perhaps also some indication of “confidence,” i.e., how they expect that opinion to respond to time and the opinions of others.
Can you clarify how to implement the market maker for linear markets like “the number, in thousands, of American troops in Iraq in 31/06/07”?
Note: Glad to see this post, spent a day reading R. Hanson’s 2 papers mentioned in the text without having a clue about how to implement the mechanism
The most straightforward way to handle linear outcomes is by breaking up the line into a discrete number of intervals, and then proceeding otherwise as described in the post. Another alternative is to define absolute MIN and MAX possible range on the linear outcome, then just scale the range to be between 0 and 100 and run a single “vote share” type market. Yiling Chen and I have been working on some other, perhaps more satisfactory, market maker mechanisms for handling linear markets, which we hope to report on soon.
I think we still need to know MIN and MAX possible range for the first method you described. Because without that information how can we divide the infinite number line into a finite number of finite intervals?
Let’s assume that we do not set limits but take each user bet (a number predicting the outcome, and a confidence level for that number) as a possible outcome. Then we need a mechanism for incrementing the number of outcomes of the market after the market has been opened, without diminishing the accuracy of the market. Are you familiar with such a method?
The second method you described is quite intuitive, thanks a lot David!
We don’t necessarily need a MIN and MAX for the first method, because the first outcome can be “less than X” and the last outcome can be “greater than or equal to Y”.
You can “split” outcomes into disjoint subintervals at any time (for example IEM occasionally does this, splitting the “rest of field” outcome into “new candidate X” and a new “rest of field”). However with the LMSR market maker, this will increase the market maker’s maximum loss exposure.
Thanks for your comments.
This is a great article. Explains Hanson’s MSR very lucidly. Could you also post a similar explanation of the paper where Hanson talks about how to integrate the order book with the automated market-maker?
Chris Hibbert tackles the integration problem (and it does get complicated). One simple thing you can do with limit orders, which isn’t quite perfect but seems reasonable, and which Todd Proebsting at Microsoft does, is this: After every transaction, simply randomly cycle through all active limit orders, transacting each with the market maker until the limit is reached or the order is exhausted. You may have to iteratively keep cycling through limit orders until quiesence.
I wrote a more detailed explanation of how to integrate market makers and order books. In order to include all the appropriate references, I posted it on my blog.
http://pancrit.blogspot.com/2007/01/integrating-book-orders-and-market.html
The grossly oversimplified version is that you trade with the market maker up to the price limit imposed by the best book order, then trade with the book order. If the market order is filled at that point, you’re done. Otherwise you repeat those steps in a loop treating each book order as a price limit for trading with the book order, and fully consuming each book order before resuming trade with the AMM. There’s nothing specific to the MSR in how you have to approach this problem.
In the multi-dimensional case, there are multiple book orders that provide constraints, and managing the constraints is more work. I put off a detailed explanation of that case until I’ve written better explanations of some of the foundations.
I can’t see how these cost and price functions apply to financial market, i.e DJIA to rise, DJI to fall
I’m getting very confused on what these functions do?
If you want a market to bet on “DJIA rises” or “DJIA falls”, you should be able to used the fomulas as is. Just replace “Democrat wins” with “DJIA rises”. I probably don’t understand your question.
“The parameter “b†controls the maximum possible amount of money the market maker can lose (which happens to be b*ln2 in the two-outcome case).”
I don’t doubt that you are right. But how did you arrive at this result? I can’t figure it out.
johan, good question.
The easiest way to think about it is to consider the value of the cost function C at the beginning and end of the market.
At the beginning, assuming q1=q2=0, then C=b*ln2 .
At the end, in the worst possible scenario for the market maker, q1=infinity and outcome 1 occurs. Then C=q1 and the market maker owes shareholders q1 dollars.
So the market maker took in (q1 – b*ln2) dollars and has to pay out q1 dollars, thus the market maker’s net loss in this worst-possible scenario is (q1 – b*ln2 – q1) = b*ln2 .
(The same answer also comes easily from Hanson’s original interpretation of the market maker as a sequential shared scoring rule.)
I’m a bit confused. Given the set of two outcomes: “a Democrat wins the 2008 US Presidential election†and “a Democrat does not win the 2008 US Presidential electionâ€, selling 250 shares of outcome two seems to me to be logically equivalent to buying 250 shares of outcome one. Yet the market maker does not appear to operate this way. Why not? Thanks.
Rob
You’re right, they are exactly equivalent.
If you work out the total/final amounts you would win or lose if you are right or wrong, you’ll see that they are equivalent even with the market maker.
The apparent difference depends on if/how you implement short selling. The difference is only a matter of accounting and budgeting prior to the realization of the event. After the event happens, all approaches become equivalent.
The approach I like best personally is to disallow short selling. Then traders can buy any outcome(s), and only sell shares of outcomes they already own. I believe this is the most understandable approach for a wide audience. I’ve found that people tend to get confused by short selling.
I have to agree with George regarding difficulties understanding Hanson’s paper. How do you derive the logarithmic scoring rule Si = Ai + B log (Ri) into one equation in the case of two states? In the case of multiple states?
@ george.chou2
Can you shed some light on how to cheat the market maker to win the game? Is it by having more than one account and then driving the prices up or down?
Shahnawaz, you can’t really cheat the market maker in a real-money market.
In a play-money market where every new account starts with some amount of cash, you can cheat by opening up multiple accounts and funneling money from your dummy accounts to your main account.
Hi David,
I am new to prediction markets and your explanation is great. I could understand it easily. The best part is that you have explained it using an example with sample calculations.
How about you doing a follow-up post with sample calculations for explaining combatorial markets. for example, if we want to have a market saying “which 2 of the following 4 teams will play in the finals”. How would that be implemented?
Looking forward to it.
Regards,
Shahnawaz
Shahnawaz,
Thanks for the comment and the kind words. That is a good idea and something I will try to do.
Hi Dave. Thank you very much for this entry. This was very informative. However, I have one question:
I understand how to derive the price function from the cost function and vice versa, however, I do not understand how you get any of the two in the first place given a particular scoring rule. Could you explain? Perhaps using the logarithmic scoring rule as an example?
Thanks a lot,
Sven.
Great explaination, Thanks.
I cannot understand how to start a market where you already know that the responce will tend towards one of the two outcomes. For example, I know that outcome A has roughly a 70% liklihood and outcome B has roughly a 30% chance. I would want the cost equation to reflect this. To start the at 70/30 rather than 50/50 (where q1=q2=0). Can we simply start with q1=70 and q2=30 and go from there?
Whould the cost equation then reflect my new maximum loss, rather than B*ln2?
What about non binary contracts. Let’s say that we have a contract that predicts the price of the new Nokia cell phone. The question would be; “How much would the new phone cost on release date?”. Could really Hanson’s log-approach work here as well? Wouldn’t there be problems getting the price up to the “correct” level (I suppose that the function decays…) Thx.
Some answers to commenters:
Sven: There does not seem to be an easy way to derive the cost function for a particular scoring rule, at least that I know of. Yiling Chen and I have derived cost functions for the log and quadractic scoring rules, but each involves a tedious amount of special-case algebra.
dave mcguinness: Yes, you can/should start q1 and/or q2 at non-zero levels, however it won’t be exactly 70 & 30. Yes, that will change (increase) the maximum possible loss.
mike: Yes, LMSR can handle numeric predictions like this as long as the range is discretized into a bunch of intervals. See for example our implementation for Yoopick.
David: Thanks a lot, but discretizing (sampling) might not suit all applications that well. Just as an example, wouldn’t that be to “guide” the participants or making the market more inefficient to some extent? Anyway, do any of you guys have an idea of what would be the de facto standard market maker algorithm for non binary contracts like the Nokia cell phone price I described above?
Thanks Mike. I believe that in practice discretization shouldn’t be too much of a problem. You could for example discretize down to the nearest penny: I can’t imagine wanting to place a bet at a finer grain than that. Then people can bet on whatever interval they think the Nokia price will fall into.
I have to admit, formulas scare me a little (ok, a LOT). But your examples make it a lot easier to get my head around this. Will have to bookmark and come back to another day! Thanks for the detailed explanation.
I wrote a little paper about applying the LMSR to numerical outcomes, heavily based on this article’s application of the LMSR:
http://built-it.net/srsr.pdf
Thanks Aleks. Fantastic. That is a great paper: extremely well written: clear and entertaining.
One question: will your procedure cause the market maker to have a risk of unbounded loss? This seems to be the trickiest part in moving toward a continuous version.
Thanks again: it’s a great pleasure to have such things arrive on my doorstep.
I don’t think so, as it’s not a mathematical change to the scoring rule, but a way to reduce the ranged problem into a form the scoring rule can understand.
Honestly I don’t see much point in having market makers and order books, in the tests I’ve written, everything is just “the system” and it takes buy and sell orders….I’ve found that usually automated market makers end up taking nearly 100% of the orders, so having a book is pointless, and when playing with fake money, market liquidity is more important than “loss” by the market maker. If the market maker fills all orders according to a single mathematical rule, then it can never lose money (as far as I have been able to test, anyways…)
Thanks David, this post helped me a lot.
However, I cannot implement your solution to Cost for multiple outcomes. For example, what would the Cost function be for a question like the following: “Who will win the election, A B or C?”
What will be the Cost function for three possible outcomes?
Sunwoo: thanks glad it was useful. You might benefit from this exchange I had over email:
Frederic wrote:
> I recently stumbled upon your article “Implementing Hanson’s Market
> Maker ” which was really interesting (I had read both Hanson’s
> articles and couldn’t really figure out everything it contained, nor
> extract the ‘implementation guides’ I would have wanted).
>
> I have a few questions, though, and would be glad if you could spare a
> few minutes to answer me (I know that the article is already almost 3
> years old).
>
> Basically, the cost function is C = b * ln(exp(q1)/b+exp(q2)/b)
>
> – Would this generalize, for n outcomes to C = b *
> ln(exp(q1)/b+exp(q2)/b+exp(q3)/b+…+exp(qn)/b)?
> – If a trader sells short some shares for q1, does this mean that, in
> fact, the amount of q2 will increase? (or q2,q3, … in the
> generalized case?) Because I don’t see negative values in your example
> (and negative values will just make the exp(q1) close to 0). Or is the
> short selling forbidden by this model?
I answered:
* Yes, it generalizes easily and I believe that’s the correct formula (didn’t check completely). See this book chapter for the exact formula: http://blog.oddhead.com/2007/09/17/computational-aspects-of-prediction-markets-book-chapter-and-extended-bibliography/
* “short” selling is a poor concept for a standard type of prediction market where each winning share pays $1 (or any fixed amount). It’s much clearer to think of “buy not q1” rather than “short sell q1”. It’s perfectly fine to “buy not q1” which is equivalent to “buy q2, q3, q4, etc.” for all securities. See: http://blog.oddhead.com/2009/03/17/kiss-prediction-market-lingo-goodbye/
Thanks David, it was very helpful.
I am writing a research paper on http://www.Hubdub.com, and I’m still confused on how they calculate their Payments, outcome Percentage etc. for Hubdub $$.
I was wondering if you could spare a few minutes and check out Hubdub, and briefly explain to how their system works.
Again, thank you.
Hello David,
Very good explanation of Hanson’s scoring rule. Have couple of questions: 1) How do you chosse a value for b for a given market. Does it depend on the market size (i.e number of participants?). I understand your explanation that it controls the maximum money that the market maker can loose (for a 2 outcome case it is b* ln2). So, for example, if I set b = 100, then the max loss = $69, if I choose b = 50, the max loss = $34.5; How do i know which value is correct, because “b” also impacts the price functions? Does it depend on the initial play money? 2) How to choose the correct initial play money for a market?
Thank you.
Jackie, choosing b is more art than science, especially if it’s play money. Too high b and the price doesn’t change enough as people bet. Too low b and the liquidity is too low. It does depend on the number of players and the amount of play money they have. Chris Hibbert suggests having a fairly small b and then integrating an order book together with the market maker. That may complicate the user interface though.
Dear David,
I second the thoughts that this blog makes implementation of LMSR easy to understand.. thanks!..
I have problem with its implementation in dynamically changing price markets. Let’s say the question is “How much will X sell” and you started with 1000. People can bet higher or lower than market price and this is expected to change the market price in return. New bets come in based on the updated price (ie 1055). How do you calculate the up-to-date price in this case – what is the logic/formula behind the scenes? Inkling, for instance, offers this option.
It seems you cannot simply use this: C = b * ln(eq1/b+eq2/b) as with the market with 2 discrete outcomes, as the “higher than market” and “lower than market” bets are placed at different market price points.
Any comments/links will be appreciated! Thank you!
It is amazing how orders of any substance will move the price.
I don’t think so, as it’s not a mathematical change to the scoring rule, but a way to reduce the ranged problem into a form the scoring rule can understand.
It seems you cannot simply use this: C = b * ln(eq1/b+eq2/b) as with the market with 2 discrete outcomes, as the “higher than market†and “lower than market†bets are placed at different market price points.
Hi. Thanks for the comment and the kind words. That is a good idea and something I will try to do.
Knew The News runs the Hanson market maker. Implementation is being based on this article but has been modified and the adaption in the website involves a few additional mechanisms. Nevertheless: Thanks for this great contribution!
kruijs, thanks! I like KnewTheNews and glad this writeup was useful.
Hey Dave, I have a quick question. In this first example (C(10,0)-C(0,0)) I assume that 10 represents the number of shares that are being purchased. Can you tell me what 40 represents in the second equation? C(40,10)-C(50,10).
Thank you and sorry if I missed something obvious.
Colin
Hi Colin. The 40 is the total number of shares sold by the market maker so far. The arguments of the cost function C are the total number of shares sold, not the current number being traded. In the second equation, the total number of shares sold is 50 at first. Then the trader wants to sell 10 shares. The market maker buys back 10 shares. So after the transaction, the total number of shares sold will be 50-10 = 40. Hope that was clear.
Thanks for the amazing explanation.
A financial market maker in the financial markets has a built-in edge, because the market maker quotes the bid/ask spread.
A bookie has a built-in edge referred to as the overround, because their odds do no match the true statistical chance of the final outcome.
A casino obviously has a built in edge on all of its games.
They all have a risk, but all have a slight edge over the long term.
In the case of Hanson’s market maker what exactly is that edge and how do we calculate it? or is there no edge, i.e. it just breaks even over time?
I appreciate your time!
Hi,
Just wondering if you are still working on prediction markets. I’m planning to implement this and your article has proven invaluable, but I would like to see whether I could write to you and ask you additional questions should they arise. Most open source implementations of prediction markets with market-making algorithms are dead from what I can recall.
Thanks a lot,
Jose