computer science » Oddhead Blog

Three Crowd-ed events this fall

computer science, economics, events, incentives, prediction markets, research, yahoo No Responses »

Aug 172010

Research and Analysis of Tail Phenomenon Symposium

August 20, 2010, Sunnyvale, CA

The last decade has witnessed the emergence of enormous scale artifacts resulting from the independent action of hundreds of millions of people; for example, web repositories, social networks, mobile communication patterns, and consumption in “limitless” stores… the first Research and Analysis of Tail phenomena Symposium (RATS)… will explore the different computational, statistical, and modeling problems related to tail phenomena… We are particularly encouraging summer interns in any of the Bay Area research centers to join us in the event.
We will start with a video welcome by Chris Anderson (Wired), followed by a series of invited talks by Michael Mitzenmacher (Harvard), Aaron Clauset (Univ. of Colorado), Neel Sundaresan (eBay), Sharad Goel (Yahoo! Research, NY) and Michael Schwarz (Yahoo! Research, CA).

We invite proposals for short (20 minute) talks from students and researchers working in the area.

CrowdCof2010: 1st Annual Conference on the Future of Distributed Work

October 4, 2010, San Francisco, CA

Were you crowdsourcing before it was cool? We want to hear about your projects.

We are inviting submissions on all topics regarding crowdsourcing, including:

Past, present, and future of crowdsourcing

Quality assurance and metrics

Social and economic implications of crowdsourcing

Task design/Worker incentives

Innovative projects, experiments, and applications

Submission Guidelines

Deadline: Sept. 1

CrowdConf will bring together researchers, technologists, outsourcing entrepreneurs, legal scholars, and artists for the first time to discuss how crowdsourcing is transforming human computation and the future of work.

Confirmed Speakers:
Sharon Chirella: Vice President, Amazon Mechanical Turk
Tim Ferriss : Author, The 4-Hour Work Week
David Alan Grier: Author, When Computers Were Human
Barney Pell: Partner, Search Strategist, and Evangelist, Microsoft Maynard Webb: CEO, LiveOps
Jonathan Zittrain: Professor of Law and Computer Science, Harvard

Computational Social Science and the Wisdom of Crowds Workshop at NIPS 2010

December 10th or 11th, 2010, Whistler, Canada

We welcome contributions on theoretical models, empirical work, and everything in between, including but not limited to:

Automatic aggregation of opinions or knowledge

Prediction markets / information markets

Incentives in social computation (e.g., games with a purpose)

Studies of events and trends (e.g., in politics)

Analysis of and experiments on distributed collaboration and consensus-building, including crowdsourcing (e.g., Mechanical Turk) and peer-production systems (e.g., Wikipedia and Yahoo! Answers)

Group dynamics and decision-making

Modeling network interaction content (e.g., text analysis of blog posts, tweets, emails, chats, etc.)

Social networks

[Covers] computational social science… [and] social computing… with an emphasis on the role of
machine learning…

Deadline for submissions: Friday October 8, 2010

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.

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.

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.

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.

Why automated market makers?

commentary, computer science, prediction markets, research 20 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 pratical 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.

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.

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