ideas » Oddhead Blog

Where is the betting market for P=NP when you need it?

commentary, computer science, gambling, people, prediction markets, trends 12 Responses »

Aug 112010

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.

Famous for 15 tweets

blogging, commentary, new media, oddhead blog, search, trends No Responses »

Jul 292010

TV era: $quote = “In the future, everyone will be world-famous for 15 minutes”;
Search era: $quote =~ s/minutes/links/;
Social era: $quote =~ s/links/tweets/;

This month I’ve had five times more traffic than in any other month since I began blogging in Oct 2006, even during woblomo.

Why? I paid Paul Graham a compliment that struck a minor viral nerve, spreading through twitter, facebook, and blogs and sending over six thousand people my way on July 16 alone according to quantcast. Of course most have since dispersed.

Power on the web flows backward through referrals to the sites that people begin their day with, the sources of traffic. Referrals from social media, unpredictable and bursty though they may be, are inexorably on the rise. As they grow, power will shift away from search engines, today’s referral kings. Who knows, this may embolden publishers to take previously unthinkable steps like voluntary delisting, further eroding the value of search. This has all been said before, perhaps best by Mark Cuban starting in 2008. It would be a blow to openness and hurt users, but would spark a fascinating battle.

Another meta note: I installed a new WordPress theme: Suffusion. It’s fantastic: endlessly configurable, bug free, fast, and well designed. I happened upon it by accident when WP 3.0 broke my old theme and I couldn’t be happier. Apparently written by a teenager, I donated to his beer, er, coffee fund.

Casinos for geeks

commentary, finance, gambling, ideas, prediction markets, technology, trends 2 Responses »

Jul 272010

mad scientist geek with test tube & lab coat

Gambling has been mocked as “a tax on the mathematically challenged”. Gamblers are stereotyped as losers in life. Casinos reinforce this by literally kicking out people who display too much intelligence. They ban card counting and people who simply win too much. They don’t allow computers or Internet connections in the sports book to block out information. They emphasize familiarity over innovation, cementing their appeal to habitual gamblers over geeks.

In the eyes of a casino, a sharp is indistinguishable from a cheat. More than boring, this seems fundamentally unfair and unsustainable, inviting disguise. It also turns off a wealthy, influential, and game-loving segment of the population.

What I want: A casino by geeks for geeks that celebrates innovation, encourages cleverness, welcomes gadgets and wifi, and fosters hacking, outwit, and outplay.

At least one casino has seen the light. The M Casino in Las Vegas is parterning with Cantor Fitzgerald to support in-game sports betting with few rules and caps, inviting sharps to, more or less, “bring it on”.

…gamblers can bet on the game even during play, accepting ever-changing point-spreads and odds. They can invest money on a Knicks foul shot going through the hoop or a Dodger getting to first base — contending with ever-evolving odds.

More critically, bettors can create hedges while jumping in and out of positions. But instead of buying into the fast-breaking moves of Microsoft, they’re betting on the Mariners’ impending fortunes.

This form of wagering is new to Las Vegas but old-hat in other markets.

…unlike in most other casinos, laptop computers are welcome.

…”The M wants [sharp bettors] to be there,” believes [professional sports-bettor Steve] Fezzik. “They want your information, and that’s a progressive attitude.”

Kudos to M for taking a chance on a more interesting future and to Cantor for making it happen.

What Cantor is debuting may not be a whole lot more than betfair indoors, but it’s a long overdue start. Here’s to hoping we see even more innovation, including smarter and more expressive markets.

How high can high-level programming go?

artificial intelligence, commentary, computer science, prediction markets, research, technology 3 Responses »

Jul 192010

Our first prototype of Predictalot was written mainly in Mathematica with a rudimentary web front end that Dan Reeves put together (with editable source code embedded right on the page via etherpad!). It proved the concept but was ugly and horribly slow.

Dan and I built a second prototype in PHP. It was even uglier but about twice as fast and somewhat useable on a small scale (at least by user willing/able to formulate their own propositions in PHP). Yet it still wasn’t good enough to serve thousands of users accustomed to simplicity and speed.

The final live version of Predictalot was not only pleasing to the eye — thanks to Sudar, Navneet, and Tom — but pleasingly fast, due almost entirely to the heroic efforts of Mridul M who wrote a mini PHP parser inside of java and baked in a number of datbase and caching optimizations.

It seems that high-level programming languages haven’t climbed high enough. To field a fairly constrained web app that looks good and works well, we benefit greatly from having at least three specialists, for the app front end, the app back end, and the platform back end (apache, security, etc.).

Here’s a challenge to the programming language community: anything I can whip up in Mathematica I should be able to run at web scale. Math majors should be able to create Predictalot. Dan and I can mock up the basic idea of Predictalot but it still takes tremendous talent, time, and effort to turn it into a professional looking and well behaved system.

The core market math of Predictalot — a combinatorial version of Hanson’s LMSR market maker — involves summing thousands of e^x terms. Here we are in the second decade of the new millenium and in order for a sum of exponentials to execute quickly and without numeric overflow, we had to work out a transformation to conduct all our summations in log space. In other words, programming still requires me to think about how my machine represents my number. That shouldn’t qualify as “high level” thinking in 2010.

I realize I may be naively asking too much. Solving the challenge fully is AI-complete. Still, while we’re making impressive strides in artificial intelligence, programming feels much the same today as it did twenty years ago. It still requires learning specialized tricks, arcane domain knowledge, and optimizations honed only over years of experience, and the most computationally intensive applications still require that extra compilation step (i.e., it’s still often necessary to use C or Java over PHP, Perl, Python, or Ruby).

Some developments hardly seem like progress. Straightforward HTML markup like border=2 has given way to unweildy CSS like style=”border:2px solid black”. In some ways the need for specialized domain knowledge has gone up, not down.

Visual programming is an oft-tried, though so far largely unsuccessful way to lower the barrier to programming. Pipes was a great effort, but YQL proved more useful and popular. Google just announced new visual developer tools for Android in an attempt to bring mobile app creation to the masses. Content management systems are getting better and broader every day, allowing more and more complex websites to be built with less time touching source code.

I look forward to the day that computational thinking can suffice to create the majority of computational objects. I suspect that day is still fifteen to twenty years away.

Why automated market makers?

commentary, computer science, prediction markets, research 23 Responses »

Jul 082010

Why do prediction markets need automated market makers?

Here’s an illustration why. Abe Othman recently alerted me to intrade’s market on where basketball free agent LeBron James will sign, at the time a featured market. Take a look at this screenshot taken 2010/07/07:

The market says there’s between a 42 and 70% chance James will sign with Cleveland, between a 5 and 40% chance he’ll sign with Chicago, etc.

In other words, it doesn’t say much. The spreads between the best bid and ask prices are wide and so its predictions are not terribly useful. We can occasionally tighten these ranges by being smarter about handling multiple outcomes, but in the end low liquidity takes the prediction out of markets.

Even if someone does have information, they may not be able trade on it so may simply go away. (Actually, the problem goes beyond apathy. Placing a limit order is a risk — whoever accepts it will have a time advantage — and reveals information. If there is little chance the order will be accepted, the costs may outweigh any potential gain.)

Enter automated market makers. An automated market maker always stands ready to buy and sell every outcome at some price, adjusting along the way to bound its risk. The market maker injects liquidity, reducing the bid-ask spread and pinpointing the market’s prediction to a single number, say 61%, or at least a tight range, say 60-63%. From an information acquisition point of view, precision is important. For traders, the ability to trade any contract at any time is satisfying and self-reinforcing.

For combinatorial prediction markets like Predictalot with trillions or more outcomes, I simply can’t imagine them working at all without a market maker.

Abe Othman, Dan Reeves, Tuomas Sandholm, and I published a paper in EC 2010 on a new automated market maker algorithm. It’s a variation on Robin Hanson‘s popular market maker called the logarithmic market scoring rule (LMSR) market maker.

Almost anyone who implements LMSR, especially for play money, wonders how to set the liquidity parameter b. I’ve been asked this at least a dozen times. The answer is I don’t know. It’s more art than science. If b is too large, prices will hardly move. If b is too small, prices will bounce around wildly. Moreover, no matter what b is set to, prices will be exactly as responsive to the first dollar as the million and first dollar, counter to intuition.

Our market maker automatically adjusts its level of liquidity depending on trading volume. Prices start off very responsive and, as volume increases, liquidity grows, obviating the need to somehow guess the “right” level before trading even starts.

A side effect is that predictions take the form of ranges, like 60-63%, rather than exact point estimates. We prove that this is a necessary trade off. Any market maker that is path independent and sensitive to liquidity must give up on providing point estimates. In a way, our market maker works more like real bookies who maintain a vig or spread for every outcome.

The market maker algorithm is theoretically elegant and seems more practical than LMSR in many ways. However I’ve learned many times than nothing can replace implementing and testing a theory with real traders. Final word awaits such a trial. Stay tuned.

World Blogging Year

challenges, economics, fun, oddhead blog, woblomo 3 Responses »

Apr 012010

First: I did it! A perfect 16 out of 31. I completed the (ok, my) World Blogging Month challenge to blog every odd day in the month of March.

Last year WoBloMo leapt out of the gates with five participants but I fell five hours short of the goal. As far as I know only Anthony and I returned for year two. He succeeded too according to official Australian Rules.

Again, I found the exercise worthwhile, clearing a number of items out of my queue, albeit mostly the easy and inane ones (c.f. the barking), and boosting readership.

In fact, I enjoyed it so much that I’ve signed up for World Blogging Year (WoBloYe). I will blog every odd day of every month at least through the end of 2010, starting today.

In fact I have formally pledged to stickk to my goal. Moreover, I am putting my money where my mouth is, PM-style. For every odd day of the month that passes blog-post-free I will donate $100 to my anticharity, the re-election fund for Don McLeroy. If I miss two deadlines in a row, my antidonation will double. Three missed deadlines in a row and it will quadruple, etc.

I’ve enlisted kibotzer’s help and you can follow my progress there. Wish me luck!

Update 2010/04/02: April Fools!

P.S. In all seriousness, read that New York Times article about Don McLeroy. It’s one of the scariest articles I’ve read in a long time. It’s about how ultra conservatives on the Texas board of education are rewriting history and science according to biblical and republican dogma, and how standards in that enormous state can dictate what gets printed in textbooks nationwide. They’ve done things like add Newt Gingrich and delete Edward Kennedy as significant Americans. They’ve banned classic children’s books by Bill Martin Jr. because they confused him with a different Bill Martin, author of “Ethical Marxism”.

It is the most crazy-making thing to sit there and watch a dentist and an insurance salesman rewrite curriculum standards in science and history. Last year, Don McLeroy believed he was smarter than the National Academy of Sciences, and he now believes he’s smarter than professors of American history.

Recaptcha poetry: The barking

challenges, fun, ideas, spam, woblomo 3 Responses »

Mar 252010

My first attempt. I’m sure you can do better.

The barking. Reenact task. Arnold understanding a caveated consideration. Snowmen ammunition, shoutouts stumbling. A gridded courtroom, community pumping. Cussions berate

Housing arbitrage, or the $1.4 million muse

finance, fun, ideas, woblomo 10 Responses »

Mar 232010

Has anyone heard of the following trick, which might be called housing arbitrage?

Buy one house at the beach and a second house near a ski resort. You live in the beach house in the winter and the ski resort in the summer. You rent out the beach house in the summer and the ski resort in the winter.* Can your earnings (rental revenue minus mortgage costs) be enough to live on?

Why it could work: the cost of each house will be roughly proportional to the average annual rental income in that location. If you didn’t live in the properties at all, you should roughly break even (income = mortgage payments). But you are living in each location during the time when rent is essentially free (not contributing to the average) so you have no housing costs. If you find good enough deals (or put money down, or have some small income like freelance writing, etc.) your income may exceed your mortgage enough to live on.

What’s the minimum you could get started with on this strategy? Probably a minimum income to live comfortably as a starting point would be $70K before taxes: see justification below. Assume you can make about 5% of a home’s value in rental income: this seems feasible. Then you need $1.4 million invested in real estate (say two $700K houses) with no mortgage (completely paid). Suppose you can also borrow at 5%. Then if you put 50% down on two $1.4 million properties ($2.8 million total), your effective mortgage rate is 2.5% and your “spread” is 2.5%, so you again earn $70K, but now you have two twice as nice houses (but more risk, need to qualify for loan, etc.). Now here is some magic. Suppose you find an incredible deal (say, in a down real estate market) and you can earn 10% in rental income. You can borrow at 5% and only want to put 20% down, still a respectable portion that the bank may be willing to go for. You buy two $600K homes ($1.2 million total) needing only $240K in cash. Now your rental revenue is $120K and your mortgage payments are $48K, so your net income is, viola, $72K!

Didn’t I forget about taxes and insurance? No, I’m just assuming these can be covered by your $70K income. I did forget about health insurance, though: that could threaten the strategy, at least in the United States. You can can hope that the new health care law helps, or keep an enjoyable day job, or purchase insurance out of the $70K.

You might say $70K pretax is not enough to live the lifestyle you want. But remember, you effectively have no housing costs, and this is just meant as a starting point. This is your “muse” as Tim Ferriss calls it: a steady reliable income that is your buffer. You still should pursue freelance ideas or business ideas that you are passionate about, and one of those just might hit it big. This just gives you freedom to pursue other ideas on your own. Hopefully even at $70K you can save some money to purchase additional properties and increase your income. Note that once your mortgage is paid off, your income will go up.

One nice thing about this strategy, and real estate investments in general, is that they are naturally inflation adjusted: rental rates should go up if inflation goes up.

This really only seems practical for people without kids in school. Although I suppose if your kids went to school in the beach location it might work. You’d only spend 2.5 months in the ski resort.

Certainly there are downsides: constantly moving, living in off-season tourist towns, living in properties that are rented half the year, dealing with renters, risk of loss or default, and managing the business headaches.

If housing arbitrage could really work, why aren’t more people doing it? Maybe it requires too much capital and maybe my math is wildly optimistic. Probably it’s no more than a fun mental exercise. I’m sure it’s been thought of. I can’t find it on a cursory web search but it seems hard to articulate to a search engine. If enough people started doing it, by definition house prices would go up to eliminate the arbitrage.

__________
* Maybe take a week or two in the summer at the beach and the winter at the ski house.

Computer science = STEAM

commentary, computer science, science, technology, woblomo 6 Responses »

Mar 112010

At a recent meeting of the Association for Computing Machinery, the main computer science association, the CEO of ACM John White reported on efforts to increase the visibility and understanding of computer science as a discipline. He asked “Where is the C in STEM?” (STEM stands for Science, Technology, Engineering, and Math, and there are many policy efforts to promote teaching and learning in these areas.) He argued that computer science is not just the “T” in “STEM”, as many might assume. Computer science deserves attention of its own from policy makers, teachers, and students.

I agree, but if computer science is not the “T”, then what is it? It’s funny. Computer science seems to span all the letters of STEM. It’s part science, part technology, part engineering, and part math. (Ironically, even though it’s called computer science, the “S” may be the least defensible.*)

The interdisciplinary nature of computer science can be seen throughout the university system: no one knows quite where CS departments belong. At some universities they are part of engineering schools, at others they belong to schools of arts and sciences, and at still others they have moved from one school to another. That’s not to mention the information schools and business schools with heavy computer science focus. At some universities, computer science is its own school with its own Dean. (This may be the best solution.)

Actually, I’d go one step further and say that computer science also involves a good deal of “A”, or art, as Paul Graham popularized in his wonderful book Hackers and Painters, and as seen most clearly in places like the MIT Media Lab and the NYU Interactive Telecommunications Program.

So where is the C in STEM? Everywhere. Plus A. Computer science = STEAM.**

__________
* It seems that those fields who feel compelled to append the word “science” to their names (social science, political science, library science) are not particularly scientific.
** Thanks to Lance Fortnow for contributing ideas for this post, including the acronym STEAM.

Why doesn't Pittsburgh have a Silicon Hill?

commentary, computer science, technology, woblomo 10 Responses »

Mar 092010

I grew up in Pittsburgh. I love Pittsburgh. I still run into people who believe Pittsburgh is a steel town. Pittsburgh is not that — the steel industry cleared out (and the air cleared up) before I moved there at age 10 in 1981 — though driving through its streets it sometimes feels like one: gritty row houses, dive bars, old-growth neighborhoods, and independent shops, worn and welcoming.

Then what is Pittsburgh?

A sports town, no doubt, but that doesn’t count.

A hospital town, perhaps. The University of Pittsburgh Medical Center is a sprawling conglomerate of hospitals, doctors, researchers, and medical school, growing organically and through acquisition. Several other private hospitals and networks dot the city.

But with one the the top five computer science departments in the world at Carnegie Mellon University churning out grads at all levels, you might think Pittsburgh would have the seeds of a high-tech ecosystem. Yet there are few major technology companies, startups, or venture capital firms to nurture them locally. (Two exceptions I can think of: Google and CombineNet. Update: Also Intel Labs Pittsburgh.) Instead, CMU students tend to flee for the coasts after graduation.

Could Pittsburgh develop a startup row, a mini Silicon Valley? Pittsburghers have been hoping for and heralding such a transformation for decades. Given the city’s famously steep (SF-worthy) gradients, there’s even a perfect name for it: Silicon Hill.

In selecting Pittsburgh for the G-20 summit, the Obama administration cited Pittsburgh as a post-industrial success story with “renewed industries that are creating the jobs of the future”. But that seems very glass half full as (paraphrasing) one of my Pittsburgh friends noted on Facebook.

Paul Graham wrote a terrific essay (as Paul Graham is wont to do) about how a city might go about buying their own Silicon Valley.* He concludes that it may be possible. “For the price of a football stadium, any town that was decent to live in could make itself one of the biggest startup hubs in the world.” His main conjecture is that the money would fund a large number of good local startups in their infancy but without forcing them to stay — the best startups simply won’t take money that constrains their future options. The funding would have to be rich enough and the environment nice enough that they simply would not want to leave.

Is Graham right and, if so, could Pittsburgh pull it off?

__________
* See also Graham’s older and longer essay How to be Silicon Valley.