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.)

Bet2Give&#8217-s user guide:

What is a prediction market?

In a prediction market, traders buy and sell shares of a stock whose closing price is determined by a real-world event in the future. For example, each share of the Clinton Stock will be worth $1 if Hillary Clinton is the Democratic nominee for president in 2008, otherwise, it will be worthless. If you buy the stock at, say, $0.60, and Clinton goes on to win the nomination, then the stock will be worth $1 and you&#8217-ll have made a profit of $0.40 on each share that you bought. Well done!

However, you don&#8217-t have to wait for the stock to expire before making a profit. You can resell your shares at any time, hopefully for a higher price than what you paid for them. Buy low, sell high, it&#8217-s the secret of success.

Prediction markets offer a most entertaining form of betting directly against other people, with no &#8220-middle man&#8221-. They also allow exciting real-time betting during live events such as sports games. Finally, because, you can &#8220-resell&#8221- your bets at any time, the market allows you to control your risk precisely or to cut your losses. This may not be your usual way of placing bets, but it&#8217-s easy to learn and it&#8217-s well worth it for all the reasons above.

How to trade

bet2give()bet2give is a so-called &#8220-double auction&#8221- market, where each participant makes offers to buy and sell the stock at his or her chosen price. When a buyer&#8217-s price matches a seller&#8217-s, a trade happens.

To make a &#8220-buy&#8221- offer, you specify the price you&#8217-re willing to pay for the stock and the number of shares you want to acquire. To make a &#8220-sell&#8221- offer, you specify the price you want to sell your shares at, and a number of shares.

When you send your order to the market, it is entered into the &#8220-order book&#8221- where it joins the pool of other participants&#8217- offers. The offers are sorted by price, so that the best-priced offers to buy or sell are always given trading priority: When the highest-priced &#8220-buy&#8221- offer matches the lowest-priced &#8220-sell&#8221- offer, a trade happens whereby the buyer and seller exchange shares for cash.

Buyers and sellers must agree on price, but they don&#8217-t have to agree on the number of shares being traded. For instance, if the buyer wants 10 shares and the seller is only offering 6, then only those 6 shares are traded and the rest of the buyer&#8217-s offer, for another 4 shares, stays in the order book.

If your offer is priced too high or too low to find a counterpart immediately, it stays visible to all in the order book. It may find a counterpart later if the market moves your way, or you may also cancel it whenever you want.

Trading Strategies

While the outcome is undecided, the market stays open and the trading price moves up and down following supply and demand from the participants. Then, when the market closes, the shares you own are redeemed at the appropriate payoff value.

Strategy 1: Buy low, sell high: The usual way to make money in the market is to &#8220-buy low, sell high.&#8221- This means either buying shares at a lower price than their final payoff value, or buying shares only to sell them back later at a higher price to other participants.

Obviously, the &#8220-buy low, sell high&#8221- strategy only works if the trading price eventually goes up after you buy. If that&#8217-s not the case, you will lose money, but you can still try to cut your losses by selling your shares sooner than later:

Strategy 2: Pre-sell high, buy low: You&#8217-ll want to apply this reverse strategy if you think that the trading price will go down or that the payoff value will be lower than the current trading price. In essence, the market lets you sell shares that you do not yet own, under the strict condition that you must buy them back later. You are hoping, of course, that the price will fall in the meantime so that you can buy the shares back for less money than what you sold them for and pocket the difference.

You are free to choose when to do the buy-back, but if you haven&#8217-t done so by the time the market closes, you will have to buy the shares at the closing price.

How does it work? Technically, pre-selling shares you don&#8217-t own is called &#8220-shorting&#8221- or &#8220-going short,&#8221- and buying them back later is called &#8220-covering your shorts.&#8221- When you go short, you immediately pocket the amount of the sale, but the market also preemptively withholds from your account the maximum potential amount that may be required for the buy-back . Then, when you decide to cover your shorts, the cash that was withheld earlier is automatically used towards that purchase, and you get a refund for the money that wasn&#8217-t used.

In the end, your profit or loss is exactly the difference between the proceeds of the initial sale and the cost of the later buy-back. If the trading price has fallen in the meantime, you make a profit, otherwise, you take a loss.

Strategy 3: Buy a basket: In some cases, like elections, several stocks may be competing against each other so that only one of them will expire at $1 while the others will all expire at $0. In such cases, we give you the possibility to buy baskets of shares containing exactly one share of each stock, for $1. You can then dump the shares you presume will be losers onto unsuspecting buyers, and keep those that you think have a good chance of expiring at $1.

Experienced traders also view this as a cheap way to &#8220-short&#8221- several stocks at once.

The value of your holdings

Your holdings are the shares that you own in each stock, or the shares that you have pre-sold (your shorts). For each stock, the value of your holdings is estimated from the last trading price like this:

• A share&#8217-s current worth is estimated to be exactly the price at which the last trade occured.
• A short&#8217-s worth is estimated to be the difference between the maximum potential value of a share and the last trading price.

Of course, this is only an estimation. The actual liquidation value of your holdings will be determined by the price at which you are effectively able to sell your shares or cover your shorts when you decide to do so.

Liquidifying share/short pairs

If you do many trades, you may encounter a situation in which your portfolio contains both shares owned and shares pre-sold of the same stock. In this case, rather than having to buy-back the shares you pre-sold with cash, you can just use the shares you already own. Each pair of shares owned and pre-sold can be exchanged for exactly the maximum potential value of a share in cash.

NEXT: The Bet2Give real-money betting exchange could facilitate the sponsoring of socially valuable predic
tion markets by foundations and think tanks.

Koleman Strumpf&#8217-s conference webpage:

Prediction markets are a tool for harnessing the wisdom of crowds. Recently, firms have begun to use these markets to leverage the information dispersed among their employees and customers. The markets have been used to improve forecasts of uncertain events, to generate new ideas, and to improve resource allocation within the firm. Prediction markets have great promise for helping firms manage risk, because they can provide more precise estimates of events which are both internal and external to the firm.

The Freakonomics guys (on nuclear energy):

[…] The answer may lie in a 1916 doctoral dissertation by the legendary economist Frank Knight. He made a distinction between two key factors in decision making: risk and uncertainty. The cardinal difference, Knight declared, is that risk — however great — can be measured, whereas uncertainty cannot.

How do people weigh risk versus uncertainty? Consider a famous experiment that illustrates what is known as the Ellsberg Paradox. There are two urns. The first urn, you are told, contains 50 red balls and 50 black balls. The second one also contains 100 red and black balls, but the number of each color is unknown. If your task is to pick a red ball out of either urn, which urn do you choose? Most people pick the first urn, which suggests that they prefer a measurable risk to an immeasurable uncertainty. (This condition is known to economists as ambiguity aversion.) Could it be that nuclear energy, risks and all, is now seen as preferable to the uncertainties of global warming? […]

Previous: The Meaning of Probability, Class Probability, Case Probability, Betting, and Gambling

Previous articles in this series have discussed market makers and how they differ from book order markets, how to improve Liquidity in multi-Outcome claims, and how to integrate a Market Maker into Book order systems. But none of those talked in any detail about how a multi-outcome market maker coordinates prices and probabilities. Those details turn out to be important for an upcoming article on Combinatorial Markets, so I&#8217-ll go through them carefully here.

Researchers use scoring rules as a laboratory tool to convince people to reveal their true expectations about some set of outcomes. Participants are asked to give estimates of the likelihood for a set of outcomes, their scores are some function of the value they gave for the actual outcome. Scoring Rules are called &#8220-Proper&#8221- if they are designed so the participant&#8217-s best strategy is to honestly reveal the probabilities that seem most likely. The Logarithmic Scoring Rule (one of the Proper rules) provides a reward that equals the logarithm of whichever estimate turns out to correspond to the actual value. Since the total of all the estimates must be 1, the participant can only increase some probabilities by decreasing others.

Robin Hanson described how an Automated Market Maker (AMM) that adjusts its prices based on a scoring rule can support unlimited liquidity in a prediction market. If each successive participant in the market pays the difference between the payoff for her probability estimate and that due to the previous participant, the AMM effectively only pays the final participant. If the AMM&#8217-s scoring rule is logarithmic, participants who only update some probabilities don&#8217-t effect the relative probabilities of others they haven&#8217-t modified. (This last effect is only valuable for Combinatorial Markets, which I&#8217-ll talk about in a later post.)

The change in the user&#8217-s payoff is log(newP) - log(oldP) (or equivalently log(newP/oldP)) for each state. For a binary question, the possible gain will be log(newP/oldP), and the cost will be log((1-oldP) / (1-newP)). For the rest of this article, I&#8217-ll use gain and cost rather than the log(...) expressions, since there are only these two, and I&#8217-ll be using them a lot.In multi-outcome markets, the most common approach is to let the user specify a single outcome to be increased or decreased, and to adjust all the other outcomes equally, but this isn&#8217-t the only possibility. This design choice has the useful property that the probabilities of other outcomes will be unchanged relative to one another. Since the other outcomes are treated uniformly, they can be lumped together, which results in the same arithmetic as a binary market. Since those other cases sum to 1-P, the price is cost. It is also reasonable to allow the user to specify either a complete set of probabilities, or particular cases to increase and decrease and how much to change them. Whatever the case, the LMSR adjusts the reward for each outcome to be log(newPi/oldPi). I&#8217-ll describe more possibilities in this vein when I cover the Combinatorial Market.

I hope you found all this interesting in an intellectual sort of way, but you may have noticed that this description isn&#8217-t applicable to markets in which the traders hold cash and securities. The whole thing is couched in terms of participants who will receive a variable payoff, but they don&#8217-t pay for the assets, they merely rearrange their predictions in order to improve their reward.

In order to turn this into an AMM that accepts cash for conditional securities, we have to pay careful attention to the effects of the MSR on people&#8217-s wealth. The effects are easiest to describe in the binary case, and every other case is directly analogous, so I&#8217-ll start there. In a binary market, the participant raises one probability estimate (call it A) from oldP to newP and lowers the probability of the opposite outcome (not A) from 1-oldP to 1-newP. If the trader had no prior investment in this market, the reward will increase by gain.

In order to reproduce that effect in cash and securities, the AMM charges cost in exchange for gain + loss in conditional securities. Why does the trader get securities equal to the cost plus the potential gain? The effect of this is that if A occurs, the participant has paid cost, and received gain + cost, for a net increase of gain over the original position. If A is judged false, the participant has paid cost with no return, which is the effect we hoped to match.

When an AMM supports a multi-outcome market using the approach I described above, one outcome is singled out to increase (or decrease), while all other outcomes move a uniform distance in the opposite direction. If the single outcome is increasing, the exchange is trivial to describe: we charge the trader cost for gain + cost in securities. The effect looks just like the binary case. The user has spent some money and owns a security that will pay off in a situation the trader thought was more likely than its price indicated.

If the trader singles out one outcome to sell (and thus reduce its probability), the difference among the alternatives I described in the first article in this series on Basic Prediction Markets Formats becomes evident. The trader is betting against something, and the market can represent this using short selling, complementary assets, or baskets of goods. The market might allow short selling (like InTrade), a complementary asset (like NewsFutures and Foresight Exchange), or a basket of securities representing all the other outcomes (like IEM). Since there are distinctly different points of view on this question, different markets will make different choices.

In order to support the short sales model, the trader needs to receive the payment first along with a conditional liability. In our model, the trader would receive gain in cash immediately, and securities that required repayment of gain + cost if the outcome (which the trader bet against) occurs. The platform would presumably require the trader to hold reserves to ensure the repayment.

With baskets of goods, the trader would get the appropriate number of shares of each of the other outcomes. The charge would be cost, and that would purchase gain + cost of conditional assets in all other outcomes.

The complementary assets model would charge cost in currency, and provide gain + cost of an asset that paid off if the identified outcome didn&#8217-t occur. The complicated part of this representation is that traders can hold both positive and negative assets. In a 4 outcome market, a trader holding 3 units of A and 2 units of B who sold 4 units of C could be shown equivalent portfolios of either A: 3, B: 2, C: -4 or A: 7, B: 6, D: 4. I think either choice is defensible. The first resembles the transactions the user has made, and so is probably more recognizable- the second provides a more consistent view of possible outcomes. (And looks the same as baskets.) If both positive and negative numbers are shown, the trader has to realize that the negative holdings pay off in all other cases. On the other hand, displaying a portfolio in a 7-outcome market as A: 3, B: 3, C: 3, E: 5, F: 3, G: 3 doesn&#8217-t seem as clear as D: -3, E: 2.

I doubt this detail will be of much interest to most users of Prediction Markets. Luckily for them, the trade-off the logarithmic rule makes between cost and reward just happens to produce prices that match probabilities. But if you are implementing Hanson&#8217-s LMSR, you should understand the alternatives well enough to verify that your market maker correctly implements the design.
Zocalo Prediction Markets support binary and multi-outcome markets with a Market Maker based on the Logarithmic Market Scoring Rule. The design takes advantage of the parallels between the different markets by only implementing the logarithmic rule in one place.

This article is cross-posted from pancrit.org.

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)
• Integrating Book Orders and Market Makers (2007-01-10)
• Conditional and Combinatorial Betting (2007-03-06)

Jed has put his video on YouTube and I finally got to understand how to embed a YouTube video in a WordPress blog post &#8212-simple, just temporarily uncheck the visual editor (in your profile area) and then paste the YouTube code in the writing area of your blog post.

It should work now. (You can either watch this video by clicking on &#8220-play&#8221- or watch it on the YouTube site by double-clicking on it.)

Previous blog posts by Chris F. Masse:

• Collective Error = Average Individual Error – Prediction Diversity
• When gambling meets Wall Street — Proposal for a brand-new kind of finance-based lottery
• The definitive proof that it’s presently impossible to practice prediction market journalism with BetFair.
• The Absence of Teams In Production of Blog Journalism
• Publish a comment on the BetFair forum, get arrested.
• If I had to guess, I would say about 50 percent of the “name pros” you see on television on a regular basis have a negative net worth. Frightening, I know.
• You can’t measure the usefulness of a system by how many resources it consumes.

Bet on It! – (page two – page three + a crappy listing of exchanges) – by Steven Cherry

[…] Chris F. Masse, a [] consultant in Sophia Antipolis, France, who specializes in prediction markets, says that by 2010, “10 percent of Fortune 500 companies will have gone public about their use of internal prediction markets, and probably another 10 percent will be testing some projects.” […]

As [Robin] Hanson notes, “the winners are attracted by losers, just as wolves are attracted by sheep.” […]

I made a point to this journalist, and since he has not published it, I will share it with you. I said that prediction markets, as an information aggregation mechanism, is a meta forecasting tool, since prediction markets feed on all the other forecasting tools. Do you, guys, agree with my censored statement?

I also made a sidebar comment to him. I said that David Perry of Consensus Point is the major evangelizer of the use of internal prediction markets, these days &#8212-once you have acknowledged Google&#8217-s public input. Agree, disagree?

Ron Paul is being silenced, BetFair is victimized in the US, and, finally, Chris Masse is censored &#8212-but we all try to resist. We will defeat these three conspiracies (which I suspect Bo Cowgill is part of), ultimately.

Go reading the article, if you haven&#8217-t done already (and then read Mike Giberson&#8217-s comments). &#8212- Bet on It! – (page two – page three) &#8212- Via Steve Roman

&#8212-

UPDATE: Robin Hanson comments&#8230-

I don’t that much care about terminology here, but I do agree that prediction markets should shine best at the meta level, when competing institutions try to draw what insight they can from other institutions running in parallel.

Via betting market expert Niall O&#8217-Connor, The Guardian:

Tom and Mark are the betting analysts in the security department at the British Horseracing Authority, and the breadth and power of the information at their disposal is remarkable. The sport in general now accepts that Betfair works closely with the regulators to fight corruption. It is still startling, though, to see it at first hand. To the analysts, individual accounts are numbers, not names, and the identities of those behind them remain Betfair&#8217-s business unless the investigators have cause for concern. Every bet placed on Betfair is logged on the system within seconds, while at any one time, around 100 &#8220-flagged&#8221- accounts will be receiving particular attention. Bets are recorded, patterns noted and, where necessary, local stewards informed of suspicious betting patterns. On the other side of the desk, another member of the department is compiling information received from the betting analysts and elsewhere, which may eventually become evidence for a BHA disciplinary panel. [&#8230-]

&#8220-When we first signed the memorandum of understanding with Betfair [which allowed the department access to the exchange&#8217-s betting information] we were sending &#8216-red alerts&#8217- to local stewards all the time,&#8221- he says, &#8220-which meant that we had deep concerns about the betting patterns on a particular horse. Now, I can hardly remember the last time we sent out a red alert. [&#8230-]

Great.

There aren&#8217-t any &#8220-memorandum of understanding&#8221- between TradeSports-InTrade and the US sporting bodies.

Previous: BetFair has an anti-fraud team whereas InTrade-TradeSports has none.

&#8212-

UPDATE: Chris Hibbert comments on the lack of cooperation between TradeSports and the sports bodies (which is a fact)&#8230-

Don’t the US Sporting Bodies consider betting (other than regulated domestic bodies) to be illegal? Why would TradeSports approach them? Why would it read any missives they sent? And vice versa, why would the domestic bodies contact or welcome contact from TS?

If TS offered to provide info on suspicious activities, the American authorities would ask for a list of all Americans in their DB, and then go after anyone they received details on. This isn’t useful to TS. British authorities, OTOH, make a distinction between good customers and bad customers, and believe there are many more of the former than the latter.

UPDATE: Mike Giberson makes a counter-point&#8230-

Chris Hibbert makes a good point, but given that NFL security reportedly maintains contacts with illegal gambling operations to help the NFL detect possible corruption, presumably the NFL and other U.S. sports leagues could work out some arrangement with legal companies operating outside the United States, such as TradeSports, that wouldn’t require the companies to help the U.S. enforce its local laws.

Read the previous blog posts by Chris F. Masse:

• Terrorism Futures
• InTrade-TradeSports and BetFair-TradeFair should take a close look at Cantor Fitzgerald’s strategy to gain a share of the $100 billion U.S. gambling industry.
• The secrecy-seeking Mark Davies is solely to blame for all this mess… but this vibrating BetFair spin doctor has managed to repair the PR damages quite brillantly, it shall be said.
• A Betting Exchange = A Bookmaker —> !??
• BetFair’s new bet matching logic + BetFair Malta’s trading on the multiples
• Dick Cheney, the new Churchill?
• BetFair Malta’s combo market maker (trading algorithm + human market makers) operating on the multiples

Here&#8217-s what Robin Hanson meant&#8230- when he wrote:

[…] markets that give the consequences of electing any particular candidate.

This:

Let U = the unemployment rate, D = Democrats win, and R = Republicans win. An exchange rate between “Pays $U if D” and “Pays $1 if D” gives an estimate of E[U|D]. Similarly, an exchange rate between “Pays $U if R” and “Pays $1 if R” gives an estimate of E[U|R]. We can compare E[U|D] and E[U|R] to see which candidate is expected to have a lower unemployment rate. And we know how to pay off all of these assets, no matter what happens.

More:

Since we can pay off all the assets objectively, predictions of their relative value are also predictions about objective things, not just about opinion. Any information about what employment policies a candidate would choose, and about the consequences of those policies, could be relevant.

More in Robin Hanson&#8217-s paper on &#8220-decision markets&#8221- &#8212-PDF file.

And read Mike Giberson&#8217-s comments on the Patri Friedman blog post. (He likes it and thinks I was too harsh on it.)