David Pennock is one of the smartest guys I know. As a scientist at Yahoo! Research, he’s on the bleeding edge of computer scientists working at the interface with economics. His latest project, called Predictalot, is an amazing new prediction market which allows people to trade on the millions of possible outcomes of the Sweet Sixteen. It’s a brilliant example of just why economists are going to have to get cozy with computer scientists. And David has generously agreed to provide a guest post describing what he’s up to. (And if you want more, he writes the always-interesting Oddhead Blog).
A Prediction Market Trading Pit for the Digital Age
By David Pennock
Prediction markets are a boon for information junkies. You can learn a lot by watching people vote with their wallets, even without opening your own. For example, here’s what the betting markets are predicting today:
- There’s a 96-98 percent chance the Federal Reserve will keep rates unchanged at their April meeting (IEM)
- There’s a 42-47 percent chance that 2012 will be the warmest year on record (intrade)
- U.S. home prices aren’t expected to rebound until 2012, though they’re projected to be up 1-5 percent from Dec 2009 levels by 2015 (CME Group)
- There’s a less than 50 percent chance Obama will win Ohio in 2012 (intrade)
An information junkie myself, I want more. For example, I’d like to know:
- The chances that Obama will win both Ohio and Pennsylvania together
- The chances that whoever wins California will win the election
- The chances that the Republican candidate will win Nevada, Utah, and Arizona but not New Mexico
To get this kind of wild flexibility in what can be predicted, we need what are called combinatorial prediction markets, or markets where predictions are composed by combining different options in myriad ways.
Most prediction markets are one-dimensional, which means that every outcome is traded separately. For instance, to predict “Obama will win between 269 and 312 electoral votes” in a one-dimensional market, you’d have to go in and buy each of the 44 intervening outcomes one at a time: 269, 270, 271, 272, … ugh! Combinatorial prediction markets allow traders to buy the full interval in one fell swoop. This bundling feature can be added with almost no downside as long as the number of outcomes is modest: say a few thousand or less.
But combinatorial prediction markets can have an unimaginably large number of outcomes. A U.S. election market might have over one quadrillion outcomes, one for every possible way the fifty states might swing. Think of the red and blue maps that are typically displayed by election pundits. Now think of all the possible configurations of that map that might arise after the 2012 election. Since each of the fifty states can be colored two ways (ignoring third parties), in theory there are 2 to the power 50, or 1.13 quadrillion, possible outcomes! A combinatorial prediction market needs to track each of these possibilities!
People don’t naturally deal well with 1.13 quadrillion of anything. Traders want to predict high-level things like “Obama will win Ohio and Pennsylvania.” A combinatorial market does the heavy lifting behind the scenes, taking a prediction and automatically breaking it up into its component parts: in this case, all possible maps — over 250 trillion — in which Ohio and Pennsylvania are both blue. Of course, this process is an impossibly tedious task no (human) trader would ever undertake. Luckily, computers don’t mind at all; in fact, it’s just the kind of thing they excel at.
These combinatoric problems are actually pretty common. In fact, you’ve probably been thinking about a particularly complicated example recently, as you’ve filled out your March Madness brackets. There are 9.2 quintillion possible brackets, one for every possible way the 64-team, 63-game tournament might unfold. To put that number in perspective, there are estimated to be about 10 quintillion insects on the planet. At Yahoo! Labs, we’ve built a combinatorial prediction market as a beta experiment. It’s called Predictalot, and right now you can make any of millions (OK, quadrillions) of predictions, including “Duke will advance further than Connecticut and Brigham Young” (current odds: 42.3 percent).
But there’s a real computational problem in running these markets: keeping track of 9.2 quintillion possible outcomes is too hard, even for today’s computers to manage explicitly. Technically, the problem we’re trying to solve is #P-hard, or as hard or harder than the canonical intractable problems in computer science like the traveling salesman problem. So we use an approximation technique to estimate the odds for any prediction a user selects on the fly. Improving this approximation is an ongoing area of research that we’re still actively exploring. (At this point, I have to acknowledge the incredibly talented and dedicated research engineers who took the crazy idea of two scientists — myself and Daniel Reeves — and turned it into something real that’s fast, fun, pretty, and easy to use. Read more here.)
Why do we need or want combinatorial markets? Simply put, they allow us to collect more information. Combinatorial markets reveal the correlations among events (like Obama winning both Ohio and Pennsylvania), and not just their independent likelihoods. Understanding these correlations is key to many applications, including risk assessment. In fact, many people conjecture the financial crisis was exacerbated due to fundamental underestimation of the possibility of correlated failures.
Now these ideas aren’t just relevant to prediction markets. They also translate to financial and betting exchanges, sports bookies, and racetracks. But while these markets are modernizing — turning their operations over to computers and moving online — their core logic for processing orders hasn’t changed much in the last century since the days when auctioneers were people. These markets typically treat all outcomes like apples and oranges, processing them independently, even when they are related. For example, bets on a horse “to win” and “to finish in the top two” are managed separately at the racetrack, as are options to buy a stock at strike price 30 and strike price 20 on the Chicago Board Options Exchange. In both cases, it’s a logical truism that the first is worth less than the second, yet the market pleads ignorance, leaving it to traders to enforce consistent pricing. In a combinatorial market, a bet on Obama to win Ohio and Florida automatically affects the market price for that combination, and also for the possibility that he wins the Presidency, as it logically should.
A combinatorial market is a smarter market, letting humans and computers each do what they do best. People enter predictions in simple terms they understand. The computer handles the massive yet methodical number-crunching needed to combine all the pieces together into a coherent overall prediction of a complex event. Especially in the context of a prediction market, where the goal is to gather information, it makes sense to focus traders on providing their information, rather than wasting effort on finding and exploiting mispricings between related outcomes.
The learning curve in many of these prediction markets is still too steep. First-time traders can get lost in a maze of numbers, jargon, and definitions. By shifting some of that complexity into the central trading pit, the task of traders can, somewhat counter-intuitively, become easier and more natural, leveling the playing field and allowing a wider range of people to participate. Ultimately, that’s good for the overall ecosystem. And great for information junkies.