Category Archives: computer science

Why automated market makers?

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:

Wide bid-ask spread for Lebron James contract on intrade -- needs a market maker 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.

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

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 most popular game app on yahoo 2010-06-12

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

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.

Read more here, here, and here.

Or watch a screencast of how to play:

Gates Hillman Prediction Market: The Movie

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.

Evolution of prices in the Gates Hillman prediction market

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.

CS ∩ Econ news

Here are some news items about the field with no name (at least not yet, see below) that lies at the intersection of computer science and economics.

  1. The Sixth Workshop on Ad Auctions is soliciting papers. The workshop will be held June 8, 2010, in Cambridge, MA, in conjunction with the ACM Conference on Electronic Commerce (EC’10). There is a terrific organizing committee this year spanning industry and academia, CS and business schools.
  2. The EC’10 list of accepted papers is out and looks great.
  3. The first-ever Behavioral and Quantitative Game Theory Conference on Future Directions will be held May 14-16 in Newport Beach, CA. The program looks fantastic.
  4. Last fall, the University of Pennsylvania announced the first-ever undergraduate degree program in Market and Social Systems Engineering. Kudos to UPenn: the move shows impressive vision and leadership.
  5. The NSF is funding research in the CS-Econ area. They support efforts to “explore the emerging interface between computer science and economics, including algorithmic game theory, automated mechanism design, computational tractability of basic economic problems, and the role of information, trust, and reputation in markets” (page 7).
  6. The NBER Market Design working group is soliciting papers for a workshop October 8-9, 2010 in Cambridge, MA.
  7. We are now reviewing some amazing submissions to Yahoo!’s 2010 Key Scientific Challenges program. Read the challenges for the area we call Algorithmic Economics.
  8. Members of Yahoo! Labs can submit proposals to fund collaborative research with academic colleagues through the Yahoo! Faculty Research and Engagement program. If you’re interested, contact a Yahoo! Labs employee.

What should be the name? CS ∩ Econ is accurate but cryptic. At Yahoo!, we call it Algorithmic Economics. At Google, they call it Market Algorithms. The ACM Special Interest Group in this area calls it Electronic Commerce, causing complaints every year. I’ve heard people suggest Economics and Computation. The name Algorithmic Game Theory has emerged as something of a standard within the CS theory community. [Update: Noam suggests Algorithmic Game Theory and Economics and even renamed his blog accordingly.] The phrase Computational Economics makes sense but is already in use by a different field. A fun suggestion is Economatics (or Autonomics), meant to invoke a mashup of economics and automation.

Prediction markets had a similar naming/identity crisis. They’ve been called information markets, idea markets, securities markets, event markets, binary options, market in uncertainty, and more. But now almost everyone has settled on prediction markets. I’ve come to like the name and I think it’s helped establish the field in it’s own right. I hope we can settle on a good name for CS ∩ Econ in part so we can create the Journal of PerfectNameForCSEcon, an outlet sorely missing from the field.

Update 2011/10/11: The journal now exists! Called the ACM Transactions on Economics and Computation, it circumvented the naming issue.

Let the madness begin

Sixty-five men’s college basketball teams have been selected. Tomorrow there will be sixty-four. Half of the remaining teams will be eliminated twice every weekend for the next three weekends until only one team remains.

On April 5th, we will know who is champion. In the meantime, it’s anybody’s guess: any of 9.2 quintillion things could in principle happen.

At Predictalot it’s your guess. Make almost any prediction you can think of, like Duke will win go further than both Kansas and Kentucky, or the Atlantic Coast will lose more games than the Big East. There’s even the alphabet challenge: you pick six letters that include among them the first letters of all four final-four teams.

Following Selection Sunday yesterday, the full range of prediction types are now enabled in Predictalot encompassing hundreds of millions of predictions about your favorite teams, conferences, and regions. Check it out. Place a prediction or just lurk to see whether the crowd thinks St. Mary’s is this year’s Cinderella.

Come join our mad science experiment where crowd wisdom meets basketball madness. We’ve had many ups and down already — for example sampling is way trickier than I naively assumed initially — and I’m sure there is more to come, but that’s part of what makes building things based on unsolved scientific questions fun. Read more about the technical details in my previous posts and on the Yahoo! Research website.

And for the best general-audience description of the game, see the Yahoo! corporate blog.

Update: Read about us on the New York Times and VentureBeat.

You can even get your fix on Safari on iPhone!

Dave playing Predictalot on iPhone

Below is a graph of our exponential user growth over the last couple days. Come join the stampede!

graph of YAP installs for Predictalot

Revisiting predictions: Google and Avatar

In September 2007 I predicted that “Google [will buy] a TV ad for Google.com aimed at mass consumers”… before September 2008. I only missed it by a year and a half.

In December, before Avatar was released and while some still thought it more likely to sink than swim, Slate journalist Josh Levin asked us to predict its opening weekend box office earnings using our models. We projected between $65 and $84 million. The actual number? $77 million.

Confession: In this post I am guilty of exactly the sins I’ve complained about in the past: cherry picking positive outcomes in hindsight, and measuring probabilistic predictions categorically and in isolation. Oops.

Computer science = STEAM

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?

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.