HP research scientist Vinay Deolalikar has constructed the most credible proof yet of the most important open question in computer science. If his proof is validated (and there are extremely confident skeptics as you’ll see) he proved that P≠NP, or loosely speaking that some of the most widespread computational problems — everything from finding a good layout of circuits on a chip to solving Sudoku puzzles to computing LMSR prices in a combinatorial market — cannot be solved efficiently. Most computer scientists believe that P≠NP, but after decades of some of the smartest people in the world trying, and despite the promise of worldwide accolades and a cool $1 million from the Clay Mathematics Institute, no one has been able to prove it, until possibly now.
Scott Aaronson is a skeptic, to say the least. He made an amazing public bet to demonstrate his confidence. He pledged that if Deolalikar wins the $1 million prize, Aaronson will top it off with $200,000 of own money. Even more amazing: Aaronson made the bet without even reading the proof. [Update: I should have said "without reading the proof in detail": see comments] (Perhaps more amazing still: a PC World journalist characterized Aaronson’s stance as “noncommittal” without a drip of sarcasm.) [Hat tip to Dan Reeves.]
As Aaronson explains:
The point is this: I really, really doubt that Deolalikar’s proof will stand. And while I haven’t studied his long, interesting paper and pinpointed the irreparable flaw… I have a way of stating my prediction that no reasonable person could hold against me: I’ve literally bet my house on it.
Aaronson is effectively offering infinite odds [Update: actually more like 2000/1 odds: see comments] that the question “P=NP?” will not be resolved in the near future. Kevin McCurley and Ron Fagin made a different (conditional) bet: Fagin offered 5/1 odds (at much lower stakes) that if the question is resolved in 2010, the answer will be P≠NP. Bill Gasarch says that he, like Aaronson, would bet that the proof is wrong… if only he were a betting man. Richard Lipton recounts a discussion about the odds of P=NP with Ken Steiglitz.
But beyond a few one-off bets and declarations, where is the central market where I can bet on P=NP? I don’t even necessarily want in on the action, I just want the odds. (Really!)
My first thought was the Foresight Exchange. It does list one related contract — Good 3SAT Algorithm by 2020 — which should presumably go to zero if Deolalikar’s proof is correct. It hasn’t budged much, consistent with skepticism (or with apathy). My second thought was the PopSci Predictions Exchange (PPX), though sadly it has retired. InklingMarkets has a poll about whether P=NP will be resolved before the other Clay Institute prize questions, but not about how it will be resolved or the odds of it happening. (The poll is one of several markets sponsored by the Woodrow Wilson Center’s Science and Technology Innovation Program — hat tip to Vince Conitzer.) I don’t see anything at longbets, and anyway longbets doesn’t provide odds despite it’s name.
In 1990 Robin Hanson provocatively asked: Could gambling save science?. That question and his thoughtful answers inspired a number of people, including me, to study prediction markets. Indeed, the Foresight Exchange was built largely in his image. P=NP seems one of the most natural claims for any scitech prediction market.
All these years later, when I really need my fix, I can’t seem to get it!
2010/08/14 Update: Smarkets comes the closest: they have real-money betting on whether P=NP will be resolved before the other Clay Institute prize questions. They report a 53% chance as of 2010/08/14 (for the record, I would bet against that). What’s missing is when the award might happen and how the question might be resolved, P=NP or P≠NP. I also don’t see a graph to check whether Deolalikar’s proof had any effect.
If it wasn’t clear in my original post, I found Aaronson’s bet incredibly useful and I am thrilled he did it. I believe he should be commended: his bet was exactly what more scientists should do. Scientists should express their opinion, and betting is a clear, credible, and quantitative way to express it. It would be as shame if some of the negative reactions caused him or others not to make similar bets in the future.
I just wish there were a central place to make bets on scientific claims and follow the odds in the vision of Robin Hanson, rather than every scientist having to declare their bet on their own individual blogs.
It's Arab Spring, but is it Prediction Market Winter?
Is the growing prediction market industry graveyard an omen?
It’s hard to ignore the accumulating bodies, including, may they rest in peace, PPX, Hubdub, Protrade, Tradesports, Newsfutures, Hedgestreet, Yoonew, TheTicketReserve, FirstDibz, BettorFan, ipreo, Tech Buzz Game, The WSX, Storage Markets, FTPredict, real HSX, BizPredict [1], CasualObserver.net, Cenimar, Alexadex [2], Askmarkets, Truth Markets, BetBubble, Betocracy, CrowdIQ, Media Mammon, Owise, RIMDEX, Trendio [3], TwoCrowds, BBC celebdaq/sportdaq, Betfair Predicts, chrisfmasse.com [4], and more.
Is this churn rate normal for startups in general, even healthy? Is it a sign of PM’s place in the trough of the hype cycle? Is the current climate an opportunity for those left standing or someone new? Or does it simply suggest that prediction market proponents like me have lost?
A number of media-PM partnerships which on their face seem perfectly natural are history: USA Today+Newsfutures, Popular Science+HSX, Business 2.0+ConsensusPoint, Financial Times+Intrade, Techcrunch+Askmarkets [5], ABC7+Inkling [6], and CFO Magazine+Crowdcast.
At least two former PM companies found success only after switching gears: Protrade became Citizen Sports before being acquired by Yahoo! and Nigel euthanized Hubdub to focus on FanDuel. Cocision, launched just last fall, has already abandoned its PM roots in favor of breezy Q&A and voting.
Usable Marketeer Alex Kirtland nails exactly why all the “predict Wall Street” games may be fun but aren’t likely to be predictive. Research papers, including my own, report that the accuracy advantage of prediction markets, while real, may often be small compared to statistical models or polls.
Intrade, one of the most cited and well studied PMs, is trying hard with a radical remake that looks great and a new fee structure that’s likely to improve low-probability predictions. I don’t have any inside knowledge but the company and the exchange don’t seem especially strong; I even spotted some bugs in their exchange rules. The venerable Iowa Electronic Market and Foresight Exchange that, together with Robin, started it all, look, well, venerable. Betfair is still a powerhouse and soared in its IPO just last fall, but is perhaps showing signs of age as personnel turn over and the product remains decidedly 1.0.
A few startups like Crowdcast, MediaPredict, smarkets, betable, socialico/PremierX, and InklingMarkets are nimble and promising, but none have hit home runs yet. The SimExchange is well designed and chugging along. Bet2Give [7] and CentSports are both fascinating concepts and still alive, two of the most intriguing real-money markets. Others like ExtZy, RealityMarkets and PublicGyan are hanging on. New entrants like Prediculous, Predictalot, Predictopus, 4cast, beansight, I Called It, IBET, Prediction Book, HuffPo’s Predict the News, Slate’s Lean/Lock, Ultrinsic, Knew The News, Cantor Gaming’s Oracle [8], and the MNI Forecast Competition (Lumenogic) are still coming up, though at an admittedly slower pace than four years ago.
Update 2011/5/10: Crowdpark, a German company with an office in San Francisco, launched in English last December with a web game and an impressive, well-designed Facebook game that’s already attracted 500,000 monthly active users, the 11th fastest growing Facebook app in April. They have an interesting “patent pending” automated market maker that I can’t find any details about (yet).
One PM mailing list is of questionable transparency and another is often silent. The Prediction Market Industry Association is inactive.
The final post on Newfutures Blog in 2009 declares that “resistance is futile”. But is it the world’s resistance of PMs, or PMs resistance of irrelevance, that is futile?
Despite the negative tone of this post, I believe it’s the former. The prediction market spring will come. Here’s why. Prediction markets offer:
No other prediction technology offers the same. There’s a great opportunity here for the companies that have squirreled away enough nuts to survive the winter.
P.S. Also read Paul Hewitt’s Prediction Market Prospects 2010.
Footnotes:
[1] In 2006, the teaser prediction for BizPredict was “Do you know when MySpace’s traffic will surpass Yahoo’s?”.
[2] Techcrunch declared Alexadex “the web 2.0 stock market”, back when Techcrunch encouraged Diggs
[3] I like Trendio’s post-mortem:
[4] A truly sad loss, and not just because of the 2005 awards. Someone should archive the archive to be sure this gem, as information-rich as it was verbose and disorganized, survives. Hang in there Midas Oracle!
[5] Ironically, upon launch of Askmarkets in 2008 Techcrunch asked “who’s going to the deadpool?”
[6] Technically not dead, but seems neglected.
[7] We independently considered an idea similar to bet2give at Yahoo! in 2007 but never pursued it.
[8] Cantor Gaming’s odd-setting mechanism seems effectively like an automated market maker with intelligent prior.