Michael Giberson
The NCAA basketball season is well underway, and soon enough March Madness will be here. Do you have your brackets worked out yet?
Last year while working out a few thoughts on arbitrage opportunities in basketball tournament prediction markets at Inkling, it occurred to me that the Inkling pricing mechanism was just a little bit off for such applications. The question is whether something better can be done. An answer comes from the folks at Yahoo Research: yes.
This is a long post likely only of interest to prediction market geeks, a few computational theorists and some mechanism design people. You have been notified.
Inkling prediction markets come in a couple of flavors, so far as I know all using an automated market maker based on a logarithmic market scoring rule (LMSR). In the multi-outcome case – for example, a market to pick the winner of a 65-team single elimination tournament – the market ensures that all prices sum to exactly 100. If a purchase of team A shares causes its share price to increase by 5, then the prices of all 64 other team shares will decrease by a total of 5.
The logic of the LMSR doesn’t tell you exactly how to redistribute the counter-balancing price decreases. In Inkling’s case they appear to redistribute the counter-balancing price movements in proportion to each team’s previous share price (so, for example, a team with an initial price of 10 would decrease twice as much as a team with a previous price of 5). While for generic multi-outcome prediction markets this approach seems reasonable, it doesn’t seem right for a tournament structure. [I raised this point in a comment posted here at Midas Oracle last September, and responses in that comment thread by David Pennock and Chris Hibbert were helpful.]
For simplicity, let’s forget the 65-team NCAA basketball tournament and consider a four-player single-elimination coin-tossing tournament. In the first round, A and B match up and C and D match up. If the first coin toss comes up heads, player A will advance to the final, otherwise B will advance. In the second coin toss, C advances on a heads, otherwise D advances. In the third coin toss, A or B will win on heads, otherwise C or D wins.
Assuming three independent fair coin tosses, the probability of each of the four players winning the tournament is 25 per cent. Suppose, however, you learn that the first coin is biased so B is sure to lose, but the other two coin tosses will be fair.
If an Inkling-style multi-outcome market opens, beginning with each price at 25, selling B down to near zero will drive the three other prices each to near 33 1/3. But that is crazy because it suggests that A only has a 1/3 chance of winning a fair coin toss. You can achieve the correct pricing by buying as many A shares as you sold B shares.*
The problem arises for pricing tournament markets because the tournament structure imposes certain relationships between teams that the generic pricing rule ignores. Incorporating the structure into the price rule in principle seems like the way to go. Robin Hanson, in his original articles on the LMSR, suggests a Bayes net could be used in such cases. Now three scientists at Yahoo Research have shown this approach works.**
In a short paper, “Pricing Combinatorial Markets For Tournaments,” Yiling Chen, Sharad Goel and David Pennock have demonstrated that the pricing problem involved in running a LMSR-based combinatorial market is computationally tractable so long as the shares are defined in a particular manner. In the abstract the authors report, “This is the first example of a tractable market-maker driven combinatorial market.” If you want the details, read the paper.
[Warning, the paper reads about as well as you might expect a paper in computational theory to read. Personally, I stumbled through some of the formula and skipped a lot of the others. (Hey, that’s how I got through grad school, too!) I’m trusting that these folks did the math right, but feel free to check it and let me know if you find problems.]
An introduction to the broader research effort at Yahoo describes the “Bracketology” project in a much more assessable manner.
Fantasy stock market games are all the rage with Internet users…. Though many types of exchanges abound, they all operate in a similar fashion.
For the most part, each bet is managed independently, even when the bets are logically related. For example, picking Duke to win the final game of the NCAA college basketball tournament in your online office pool will not change the odds of Duke winning any of its earlier round games, even though that pick implies that Duke will have had to win all of those games to get to the finals.
This approach struck the Yahoo! Research team of Yiling Chen, Sharad Goel, George Levchenko, David Pennock and Daniel Reeves as fundamentally flawed. In a research project called “Bracketology,” they set about to create a “combinatorial market” that spreads information appropriately across logically related bets.
… In a standard market design, there are only about 400 possible betting options for the 63-game [sic] NCAA basketball tournament. But in a combinatorial market, where many more combinations are possible, the number of potential combinations is billions of billions. “That’s why you’ll never see anyone get every game right,” says Goel.
The challenge with a combinatorial market is that it encompasses a much larger outcome space than a typical market. The key technical issue was figuring out how to incorporate the opinions and picks of every participant, and then appropriately distributing that information over the entire tournament bracket….
At its core, the Bracketology project is about using a combinatorial approach to aggregate opinions in a more efficient manner. “I view it as collaborative problem solving,” Goel explains. “This kind of market collects lots of opinions from lots of people who have lots of information sources, in order to accurately determine the perceived likelihood of an event.”
While the article is oriented to the “Which team will win the championship?” single-winner market, in principle I think you could aggregate shares to support multiple-winner markets like “Which four of the 65 teams will reach the Final Four?”
But now that they know they can manage a 65-team single elimination tournament, and I think their method would support simple extensions, I wonder about more complicated tournament structures. For example, how about a prediction market asking which Major League Baseball teams will reach the playoffs? Eight teams total advance, three division leaders and a wild-card team from the National League and the same from the American League. The wild-card team is the team with the best overall record in the league excepting the three division winners.
In principle the MLB case seems doable, though it would be a lot more complicated that a mere 65-team tournament that has only billions of billions of possible outcomes.
NOTES: *Even in more complicated cases there will be some combination of share purchases or sales to attain any desired set of prices. Therefore, the mispricing is only a nuisance as long as the trader can keep trading uninterrupted until the prices are right. However, if another trader enters the market before the first trader is done, the second trader can capture some of the small arbitrage opportunities that result from the generic rule’s mispricing.
**By the way, the Yahoo Research folks weren’t trying to solve the Inkling pricing issue per se (at least as far as I know), they were just working in the context of the same general pricing rule that Inkling uses. I brought up Inkling only because that was the context in which I began thinking about the topic and it makes a natural introduction.