fun » Oddhead Blog

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

commentary, computer science, gambling, people, prediction markets, trends 8 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.

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.

The most prescient footnote ever

fun, people, probability, technology, trends 24 Responses »

Jul 152010

Back in 2004, who could have imagined Apple’s astonishing rise to overtake Microsoft as the most valuable tech company in the world?

At least one person.

Paul Graham wins the award for the most prescient parenthetical statement inside a footnote ever.

In footnote 14 of Chapter 5 (p. 228) of Graham’s classic Hackers and Painters, published in 2004, Graham asks “If the the Mac was so great why did it lose?”. His explanation ends with this caveat, in parentheses:

And it hasn’t lost yet. If Apple were to grow the iPod into a cell phone with a web browser, Microsoft would be in big trouble.

Wow. Count me impressed.

To find this quote, search inside the book for “ipod cell”.

To get into a 2004 midset, look here and here.

It’s official: More people are playing Predictalot than Mafia Wars

artificial intelligence, computer science, economics, finance, fun, gambling, games, hacking, prediction markets, probability, research, yahoo 2 Responses »

Jun 122010

It’s true.

More people are playing Predictalot today than Mafia Wars or Zynga Poker… On Yahoo!, that is.

In fact, Predictalot is the #1 game app on Yahoo! Apps by daily count. By monthly count, we are 5th and rising.

A prediction is being made about every three minutes.

Come join the fun.

Predictalot for World Cup: Millions of predictions, stock market action

computer science, economics, finance, fun, gambling, games, hacking, prediction markets, probability, research, yahoo 3 Responses »

Jun 112010

I just left the 2010 ACM Conference on Electronic Commerce, where six (!) out of 45 papers were about prediction markets.

Yahoo! Lab’s own Predictalot market is now live and waiting for you to place almost any prediction your heart desires about the World Cup in South Africa.

Here are some terribly useful things you can learn this time around. All numbers are subject to change, and that’s kind of the point:

There’s a 37% chance Brazil and Spain will both make it to the final game; there’s only a 15% chance that neither of them will make it
There’s is a 1 in 25 chance Portugal will win the cup; 1 in 50 for Argentina
42.92% chance that a country that has never won before will win
19.07% chance that Australia will advance further than England
65.71% chance that Denmark, Italy, Mexico and United States all will not advance to Semifinals
Follow Predictalot on twitter for more

If you think these odds are wrong, place your virtual wager and earn some intangible bragging rights. You can sell your prediction any time for points, even in the middle of a match, just like the stock market.

There are millions of predictions available, yet I really believe ours is the simplest prediction market interface to date. (Do you disagree, Leslie?) We have an excellent conversion rate, or percent of people who visit the site who go on to place at least one prediction — for March Madness, that rate was about 1 in 5. One of our main goals was to hide the underlying complexity and make the app fast, easy, and fun to use. I personally am thrilled with the result, but please go judge for yourself and tell us what you think.

In the first version of Predictalot, people went well beyond picking the obvious like who will win. For example, they created almost 4,000 “three-dimensional” predictions that compared one team against two others, like “Butler will advance further than Kentucky and Purdue”.

If you’re not sure what to predict, you can now check out the streaming updates of what other people are predicting in your social circle and around the world:

Predictalot recent activity screenshot 2010-06-11 18:45

Also new this time, you can join a group and challenge your friends. You can track how you stack up in each of your groups and across the globe. We now provide live match updates right within the app for your convenience.

If you have the Yahoo! Toolbar (if not, try the World Cup toolbar), you can play Predictalot directly from the toolbar without leaving the webpage you’re on, even if it’s Google.

playing predictalot from the yahoo! toolbar

Bringing Predictalot to life has been a truly interdisciplinary effort. On our team we have computer scientists and economists to work out the market math, and engineers to turn those equations into something real that is fast and easy to use. Predictalot is built on the Yahoo! Application Platform, an invaluable service (open to any developer) that makes it easy to make engaging and social apps for a huge audience with built-in distribution. And we owe a great deal to promotion from well-established Yahoo! properties like Fantasy Sports and Games.

We’re excited about this second iteration of Predictalot and hope you join us as the matches continue in South Africa. We invite everyone to join, though please do keep in mind that the game is in beta, or experimental, mode. (If you prefer a more polished experience, check out the official Yahoo! Fantasy Sports World Soccer game.) We hope it’s both fun to play and helps us learn something scientifically interesting.

World Blogging Year

challenges, economics, fun, oddhead blog, woblomo 2 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.

Meet my maker, or Bernie Pennock and the blowtorch fountain

fun, hacking, personal, woblomo No Responses »

Mar 312010

My dad is an original maker. When I didn’t want to pay $200 to replace a broken car key housing, he sent me this vice made out of quarters he fashioned and all the parts I needed to attach it to the key.

Aa biomedical engineer, he led a study showing that a non-invasive mask can save people from respiratory failure as well as intubation. The technique is now common practice and, fittingly, the device helped saved his own life several years ago. He also invented a piezoelectric band to measure heart rate and breathing during sleep more comfortably than electrodes.

He did his Ph.D. dissertation on, in a sense, protien folding, in the days when cut and paste meant scissors and glue. I have an original copy of his dissertation and it’s a beautiful object to behold.

And what about that blowtorch fountain?

Read about it in this profile of my dad by Maureen Simpson highlighting both his hacker and painter sides.

In his retirement, Bernie Pennock found a way to turn fire into water.
The former medical research scientist said it was just one of the many problems that needed solving in his home, where art has become the answer.
“It’s really the same idea as what I did as a career,” Pennock said of his hobby. “You see a problem and think of how to solve it. I think of what I want to do and how to do it, and then I do it and see if it works.”
Using old brass blowtorches he has collected over the years from antique shops and friends, Pennock constructed a fountain next to the pathway leading up to his front door…
Instead of spitting flames, Pennock’s structure spouts water. He mounted the old-fashioned tools to a sheet of copper and then rigged a water pump and pipes behind it… Pennock said his friends describe the work of art as “very Rube Goldberg.”…
Inside his home — on lampshades, along walls and attached to windows — guests can see numerous examples of the former scientist’s artistic experiments. His most recent obsession, apart from the fountain, has been working with stained glass.
“It all started with this window that looks out on the pool,” Pennock said. “I wanted something that let in light, but wouldn’t allow you to see into the bathroom. When I got an estimate to find out how much it would cost to have someone do a stained glass window, I decided to make my own.”
The multi colored scene is based on a photograph Pennock took of two people walking on the beach. Since then, he has made at least a dozen more windows that include a copy of a Monet painting, the Talmadge Bridge in Savannah and his interpretation of
12 stained glass windows designed by Marc Chagall at the synagogue of the Hadassah-Hebrew University Medical Center in Jerusalem, Israel.
Pennock said he usually buys the windows from a Habitat for Humanity store and gets his stained glass from a supplier in Charleston. The next project he plans to take on is a bamboo sculpture, because he’s running out of windows.
“I dabble in a lot of things,” Pennock said. “I like to invent. I just start from scratch, get ideas and see what happens.”
Among his rules for living, which Pennock painted on leftover floor tiles that hang next to the blowtorch fountain, is fittingly: “Pay attention.”

Oh, my brother and sister are makers too. And my mom a trailblazer. I’ll leave those for another day.

__________
This more personal post inspired because Robin says Tyler says it’s OK.

Gates Hillman Prediction Market: The Movie

computer science, fun, prediction markets, woblomo 2 Responses »

Mar 272010

From September 2008 to August 2009, Carnegie Mellon graduate student Abe Othman ran a prediction market to forecast when CMU’s two new computer science buildings, Gates and Hillman, would open. Abe designed the market to predict not just the magic day, but the likelihood of every possible opening day (in other words, the full probability distribution), at the time making his the largest prediction market built in terms of the number of outcomes.

Now Abe created a fascinating video showing the evolution of prices over time in his market. You can see qualitatively that the thing actually worked, zeroing in closer and closer to the actual opening day as the market progressed.

Figure 3 on page 7 of Abe’s paper with Tuomas Sandholm in the 2010 ACM Conference on Electronic Commerce conveys similar information.

Despite plenty of precedent, and despite increasing evidence that non-market methods do surprisingly well too,* I still find it astonishing to see a bunch of people play a subtle betting game for nothing but bragging rights or a small prize and end up with something reasonably intelligent.

By implementing a working market used by over a hundred CMU students, Abe learned a great deal about practical yet important details, from the difficulty of crisply defining ground truth (when exactly is a building officially “open”?) to the black art of choosing the liquidity parameter of Hanson’s market maker.** Abe independently created an intuitive interval betting interface similar, and in some ways superior, to our own Yoopick interface and Leslie Fine’s Crowdcast interface. Abe went so far as to interview his top traders in great detail to learn about their strategies, which ran the gamut from building automated statistical arbitrage agents to calling construction crew members to learn inside information. Abe observed that interval betting using Hanson’s market maker leads to very “spiky” prices. Starting from this informal observation, Abe was able to actually prove an impossibility result of sorts that any price function with otherwise reasonable properties must be spiky in a formal sense. See Abe and Tuomas’s paper for the details.

__________
* Our paper “Prediction without markets”, by Sharad Goel, Daniel Reeves, Duncan Watts, and me, will be published in the 2010 ACM Conference on Electronic Commerce.
** Abe has now developed a flexible market maker that automatically adjusts liquidity to match trader activity. The paper, by Abe, Tuomas, Daniel Reeves, and me, will also be published in the 2010 ACM Conference on Electronic Commerce.

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.