Tuesday, March 06, 2007

Conditional and Combinatorial Betting

After people have used Prediction Markets for a while and have gotten used to their ability to provide forecasts, they start thinking about different scenarios. Who would be the best Republican to face Clinton? How are the prospects for a market boom or crash effected by the winner of the election? How will poverty be affected by a proposed World Bank program? These kinds of questions can be posed in a number of ways using Prediction Markets. Markets can allow betting on conditional (if) or conjunctive (and) questions. Either one can be used to answer the what if questions, but they provide different choices to the bettors, and some make it easier for observers to decode the answers.

The easiest compound question to pose is a simple conjunction of two others. InTrade had separate markets in whether Bush would be reelected in 2004 ("BUSH"), and whether Osama bin Laden ("OSAMA") would be captured before the election. Justin Wolfers and Eric Zitzewitz asked InTrade to add a single combined contract that would pay off if both came true. Their paper, Experimental Political Betting Markets and the 2004 Election shows how the prices on these three contracts can be combined to show how one event would be likely to effect the other.

InTrade created three separate claims to cover combinations of the two base questions. They were "Bush wins election" (BUSH), "Osama is captured before the election" (OSAMA), and the combination: BUSH&OSAMA which would have paid out if both the others came true. Wolfers and Zitzewitz estimated the market's conditional probability by comparing the price of OSAMA with the price of BUSH&OSAMA. If the price levels were rational, the difference between the two prices had to equal the chance that Osama would be captured and Bush would not be reelected. Since the market price of BUSH&OSAMA was 91% as high as the price of Osama, they concluded that that represented the conditional probability. A weakness of this conclusion is that while investors and arbitrageurs have an incentive to ensure that the price of BUSH is correct relative to ~BUSH, (and OSAMA with respect to ~OSAMA), there's no bet that lets an arbitrageur exploit superior knowledge of the conditional probabilities.

Sometimes investors believe they know how one outcome will effect another, and want to bet directly on that linkage. If you were confident before the election that Osama's capture would raise the probability of Bush's reelection to 95% (above the level the the market prices implied), having the conjunctive bets didn't provide a bet that would have looked beneficial to you. You might think you could buy Bush&Osama (because you believe Bush's chances are improved if Osama is captured) and sell ~Bush&Osama (because this is the outcome your view says is least likely), but you'd lose both bets if Osama wasn't captured (which is an outcome your prediction doesn't specify.)

Conjunctive claims allow observers to deduce connections between claims, but since the investors aren't directly rewarded based on the conditional probabilities, they have little incentive to ensure that the implicit conditional probabilities reflect their understanding of the connections between the outcomes. In order to evaluate different proposals we have to look at what investors would spend up-front, and then compare the possible outcomes and how the investor's earnings change in each situation.

If Bush is a 60% favorite to be re-elected, and the market thinks there's only a 10% chance Osama will be captured before the election, the odds on the conjunctions might be:

 Bush reelectedBush defeated
Osama captured .09 .009
Osama free .5 .4

If you think Osama's capture would improve Bush's prospects to 95%, what should you buy or sell? Your prediction says that the ratio of Bush&Osama to ~Bush&Osama should be 19:1, but doesn't have anything to say about Bush&~Osama or ~Bush&~Osama. If you buy Bush&Osama and sell ~Bush&Osama, you can make the prices match your beliefs better, but you'll lose money if Osama isn't captured. In order to support conditional bets directly, market operators have to find ways to allow traders to buy positions without exposing themselves to risks due to the independent cases.

A contract that acts like a conditional bet directly (written as BUSH|OSAMA, pronounced as "Bush given Osama" or "Bush conditional on Osama") would pay off if Bush is elected, and return your investment if Osama bin Laden isn't captured. That gives investors the right incentive.

 Bush reelectedBush defeated
Osama capturedGain $1 Lose investment
Osama free Return investmentReturn investment

In order to support betting on conditional probabilities, the bets have to be able to return the investors' money in particular cases. I know of three detailed proposals that have this property. They are: betting on arbitrary boolean expressions, representing the complete cross-product of possible outcomes (providing a complete set of Arrow-Debreu securities), and using the independent claim as currency for purchasing the dependent claim. There are two additional suggestions that might work, but haven't been written down in sufficient detail to be sure.

Robin described and implemented Combinatorial Information Markets which represent probabilities and traders assets explicitly for all possible combinations of outcomes. Fortnow, Kilian, Pennock, and Wellman described how you might try to support bets on arbitrary boolean combinations of conditions. Their conclusion seemed to be that solving the general problem would be computationally infeasible. They didn't describe how to address the problems they found, but I think it's possible that a market that supported only binary combinations could be designed. And finally, Peter McCluskey built (and released as open source) USIFEX in 1999. It allows the user to use the coupons of the independent event as the currency. This combination allows traders to express conditionals directly. Unfortunately, that system didn't attract a user base quickly enough, and Peter stopped development soon after the initial release.

For an article on Decision Markets written in 1999, Robin Hanson suggested creating markets using assets that pay off in "units of A if B passes" (and "... if B doesn't pass."), and allow traders to trade the assets for each other. The price of A|B in terms of B (which can be built from component assets) expresses the conditional bet. Robin didn't explain how to set up a market in which people trade assets for assets and didn't describe how to let the users see how various combination bets would express the conditional claims they might have been interested in. (This is the first of the two incomplete suggestions.)

Robin's Combinatorial Information Market design uses a complex internal representation and can support arbitrary conditional bets. He built a prototype implementation that allows the user to explore these conditionals by choosing assumptions, and then adjusting probabilities in the resulting hypothetical situations. I wrote a prototype of my own in E. Neither prototype is more than a proof-of-concept that the institution works, and neither has been operated for any general market. The strength of this approach is that users can express conditional connections between arbitrary claims; this aspect has been shown to be effective in a laboratory experiment. Robin ran tests of this market after he proposed its use for PAM, and there were apparently no problems in running it with 6 traders estimating all outcome combinations for 8 events. The glaring weakness is that it doesn't scale well. It's not clear how to build a version that would work even with a market with dozens of questions and hundreds of users. I'll describe this market in more detail in a future post in this series.

Peter McCluskey built USIFEX in 1999. It works quite differently and doesn't seem to have the performance problems of the other proposals. The primary idea for supporting conditional trading is that you buy units of A|B using units of B as currency when betting on a conditional question. The effect is that when buying A|B, you end up with coupons of ~B as part of the purchase, and that's what ensures you'll be repaid if the independent event doesn't occur. USIFEX is open source, but it hasn't been maintained since it was released in 2000. The code was resurrected for use in the Swiss MarMix exchange, (AFAICT without making any use of the conditional betting features). The biggest weakness of Peter's approach, as I recall, was that it would have taken a lot of users to ensure that the conditional markets weren't extremely thin. A longer description of USIFEX is also in the works.

Todd Proebsting built an implementation of the Hanson design that works without conditionals. Dave Pennock wrote up a description of Todd's approach, focused on the Market maker. I intend to describe the implications of Todd's approach for betting on conditionals in a future post. (This is the second incomplete suggestion.) I think it might be straightforward to extend Todd's approach to support conditional betting without running into the exponential growth of Robin's solution. The drawback is that the market operator has to separately capitalize and enable every conditional question that you want the system to support, while Robin's approach enables all of them by default. It's also possible that Zocalo Open Source Prediction Market software would be compatible with this approach, where it's clear that Zocalo would require substantial modification to support the Hanson proposal.

Other Articles in this series


Chris Abraham said...
This comment has been removed by the author.
Chris Abraham said...
This comment has been removed by the author.
Chris Abraham said...

Very interesting. I just opened the doors on a new prediction market called the Memes Futures and Prediction Markets, www.memes.org

It is only half-a-week old. I look forward to reading more about PMs since I am more of a techie and a generally curious individual, focused on pop culture, propaganda, and memetics.