Category Archives: games

Raise your WiseQ to the 57th power

One of the few aspects of my job I enjoy more than designing a new market is actually building it. Turning some wild concept that sprung from the minds of a bunch of scientists into a working artifact is a huge rush, and I can only smile as people from around the world commence tinkering with the thing, often in ways I never expected. The “build it” phase of a research project, besides being a ton of fun, inevitably sheds important light back on the original design in a virtuous cycle.

In that vein, I am thrilled to announce the beta launch of PredictWiseQ, a fully operational example of our latest combinatorial prediction market design: “A tractable combinatorial market maker using constraint generation”, published in the 2012 ACM Conference on Electronic Commerce.

You read the paper.1  Now play the game.2 Help us close the loop.

PredictWiseQ Make-a-Prediction screenshot October 2012

PredictWiseQ is our greedy attempt to scarf up as much information as is humanly possible and use it, wisely, to forecast nearly every possible detail about the upcoming US presidential election. For example, we can project how likely it is that Romney will win Colorado but lose the election (6.2%), or that the same party will win both Ohio and Pennsylvania (77.6%), or that Obama will paint a path of blue from Canada to Mexico (99.5%). But don’t just window shop, go ahead and customize and buy a prediction or ten for yourself. Your actions help inform the odds of your own predictions and, crucially, thousands of other related predictions at the same time.

For example, a bet on Obama to win both Ohio and Florida can automatically raise his odds of winning Ohio alone. That’s because our market maker knows and enforces the fact that Obama winning OH and FL can never be more likely than him winning OH. After every trade, we find and fix thousands of these logical inconsistencies. In other words, our market maker identifies and cleans up arbitrage wherever it finds it. But there’s a limit to how fastidious our market maker can be. It’s effectively impossible to rid the system of all arbitrage: doing so is NP-hard, or computationally intractable. So we clean up a good bit of arbitrage, but there should be plenty left.

So here’s a reader’s challenge: try to identify arbitrage on PredictWiseQ that we did not. Go ahead and profit from it and, when you’re ready, please let me and others know about it in the comments. I’ll award kudos to the reader who finds the simplest arbitrage.

Why not leave all of the arbitrage for our traders to profit from themselves? That’s what nearly every other market does, from Ireland-based Intrade, to Las Vegas bookmakers, to the Chicago Board Options Exchange. The reason is, we’re operating a prediction market. Our goal is to elicit information. Even a completely uninformed trader can profit from arbitrage via a mechanical plug-and-chug process. We should reserve the spoils for people who provide good information, not those armed (solely) with fast or clever algorithms. Moreover, we want every little crumb of information that we get, in whatever form we get it, to immediately impact as many of the thousands or millions of predictions that it relates to as possible. We don’t want to wait around for traders to perform this propagation on their own and, besides, it’s a waste of their brain cells: it’s a job much better suited for a computer anyway.

Intrade offers an impressive array of predictions about the election, including who will win in all fifty states. In a sense, PredictWiseQ is Intrade to the 57th power. In a combinatorial market, a prediction can be any (Boolean) function of the state outcomes, an ungodly degree of flexibility. Let’s do some counting. In the election, there are actually 57 “states”: 48 winner-takes-all states, Washington DC, and two proportional states — Nebraska and Maine — that can split their electoral votes in 5 and 3 unique ways, respectively. Ignoring independent candidates, all 57 base “states” can end up colored Democratic blue or Republican Red. So that’s 2 to the power 57, or 144 quadrillion possible maps that newscasters might show us after the votes are tallied on November 6th. A prediction, like “Romney wins Ohio”, is the set of all outcomes where the prediction is true, in this case all 72 quadrillion maps where Ohio is red. The number of possible predictions is the number of sets of outcomes, or 2 to the power 144 quadrillion. That’s more than a googol, though less than a googolplex (maybe next year). To get a sense of how big that is, if today’s fastest supercomputer starting counting at the instant of the big bang, it still wouldn’t be anywhere close reaching a googol yet.

Create your own league to compare your political WiseQ among friends. If you tell us how much each player is in for, we’ll tell you how to divvy things up at the end. Or join the “Friends Of Dave” (FOD) league. If you finish ahead of me in my league, I’ll buy you a beer (or beverage of your choice) the next time I see you, or I’ll paypal you $5 if we don’t cross paths.

PredictWiseQ is part of PredictWise, a fascinating startup of its own. Founded by my colleague David Rothschild, PredictWise is the place to go for thousands of accurate, real-time predictions on politics, sports, finance, and entertainment, aggregated and curated from around the web. The PredictWiseQ Game is a joint effort among David, Miro, Sebastien, Clinton, and myself.

The academic paper that PredictWiseQ is based on is one of my favorites — owed in large part to my coauthors Miro and Sebastien, two incredible sciengineers. As is often the case, the theory looks bulletproof on paper. But I’ve learned the hard way many times that you don’t really know if a design is good until you try it. Or more accurately, until you build it and let a crowd of other people try it.

So, dear crowd, please try it! Bang on it. Break it. (Though please tell me how you did, so we might fix it.) Tell me what you like and what is horribly wrong. Mostly, have fun playing a market that I believe represents the future of markets in the post-CDA era, a.k.a the digital age.

__________
1 Or not.
2 Or not.

Crowdpark: Taking Facebook and now Florida by storm

Crowdpark logoCrowdpark is an impressive, well-designed prediction market game that’s already attracted 500,000 monthly active users on Facebook, the 11th fastest growing Facebook app in April.

It’s a dynamic betting game with an automated market maker, not unlike Inkling Markets in functionality (or even Predictalot minus the combinatorial aspect). What stands out is the flashy UI, both literally and figuratively. The look is polished, slick, refreshing, and richly drawn. It’s also cutesy, animation-happy, and slow to load. Like I said, Flash-y in every way. The game is well integrated into Facebook and nicely incorporates trophies and other social rewards. Clearly a lot of thought and care went into the design: on balance I think it came out great.

Crowdpark is a German company with an office in San Francisco. In addition to their Facebook game, they have German and English web versions of their game, and white-label arrangements with gaming companies. They launched in English just last December.

Crowdpark’s stunning growth contrasts with decidedly more mixed results on this side of the Atlantic. I wonder how much of Crowdpark’s success can be attributed to their German roots, their product, their marketing, or other factors?

Crowdpark has an automated market maker they call “dynamic betting” that I can’t find any technical details about [1]. Here’s their well-produced video explanation:

They say it’s “patent pending”, though my colleague Mohammad Mahdian did some nice reverse engineering to show that, at least in their Facebook game, they’re almost certainly using good-old LMSR. Here is a graph of Crowdpark’s market maker price curve for a bet priced at 1%:

Crowdpark's automated market maker price curve

Here is the raw data and the fit to LMSR with b=20,000.

risk   to win (CP)   to win (LMSR)
1 91 91.079482
2 181 181.750593
5 451 451.350116
10 892 892.847929
20 1747 1747.952974
50 4115 4115.841760
100 7535 7535.378665
200 13019 13019.699483
500 23944 23944.330406
600 26594 26594.687310
700 28945 28945.633048
800 31059 31059.076097
900 32979 32979.512576
1000 34740 34740.000000


Still, there’s a quote buried in the video at 0:55 that caught my attention: “you’re current profit is determined by the fluctuation of the odds”.

There’s only one market maker that I know of where the profit fluctuates with the odds, and that’s my own dynamic parimutuel market, which by coincidence recently went from patent pending to inventor cube delivered. :-)

David Pennock's dynamic parimutuel market (DPM) patent cube - 4/2011

With every other market maker, indeed almost every prediction market, the profit is fixed at the time of the bet. Add to that the fact that Crowdpark bought a majority stake in Florida horse racing circuit Saratoga Racing Inc. and plans to operate all bets exclusively through their system, leads me to wonder if they may have some kind of parimutuel variant, the only style of betting that is legal in the US.

Of course, it may be that I simply misinterpreted the video.


[1] The technical exec at Crowdpark seems to be Aleksandar Ivanov. I found a trade press paper on (internal) prediction markets he wrote in 2009 for the Journal of Business Forecasting.

March Madness thingnaming: Core 64, True 32?

This year’s men’s college basketball tournament featured four play-in games called the First Four that the NCAA officially designated as the “first round”. They renamed what used to be called the first round — the truly mad round where 64 teams play 32 games in 2 days — the “second round”. But tradition is hard to break. Many people ignored the official names and kept right on calling the 64-team stage the “first round”. Naming confusion ensued.

For Predictalot, we sidestepped the problem by calling the first two major rounds the “round of 64″ and the “round of 32″. Interestingly enough, Yahoo! Sports independently adopted the same convention.

But shouldn’t we come up with some cute, memorable names to go along with Sweet 16, Elite 8, and Final 4? Wearing my hat as amateur (in every sense) thingnamer, here are my official nominations:

  • Core 64
  • True 32

(I initially considered but dropped a more accurate, yet ultimately clunky-sounded alternate: “Thru 32″.)

(Dis)Like them? Other ideas?

Predictopus in the Times of India

Today, Yahoo! placed two full-page ads on the back cover of the Times of India, the largest English-language daily in the world, to promote Yahoo! Cricket, a site that reaches 13.4 percent of everyone online in India and serves as the official website of the ICC Cricket World Cup.

Take a look at the middle right of the second page: it says “Play exciting games and win big” and features… Predictopus! That’s the Indian spinoff of Predictalot, the combinatorial prediction game I helped invent.

Page 1 of two full-page Yahoo! Cricket ads in the Times of India, p. 31, 2011/03/30Predictopus on Page 2 of two full-page Yahoo! Cricket ads in the Times of India, p. 32, 2011/03/30

Predictopus has nearly 70,000 users and counting, and this ad certainly won’t hurt.

Yahoo!!!

BTW, I grabbed these images from an amazing site called Press Display, which I discovered via the New York Public Library.

Times of India Mumbai edition
30 Mar 2011

Times of India Mumbai edition
30 Mar 2011

Also, congrats India, and thanks! I nearly doubled my virtual bet with the victory:

Dave's Predictopus prediction: India will advance further than Pakistan, 3/2011

We’re baaack: Predictalot is here for March Madness 2011

March Madness is upon us and Predictalot, the crazy game that I and others at Yahoo! Labs invented, is live again and taking your (virtual) bets. Filling out brackets is so 2009. On Predictalot, you can compose your own wild prediction, like there will be exactly seven upsets in the opening round, or neither Duke, Kentucky, Kansas, nor Pittsburgh will make the Final Four. You’ll want your laptop out and ready as you watch the games — you can buy and sell your predictions anytime, like stocks, as the on-court action moves for or against you.

Predictalot v0.3 is easier to play. We whittled down the ‘Make Prediction’ process from four steps to just two. Even if you don’t want to wager, with one click come check out the projected odds of nearly any crazy eventuality you can dream up.

Please connect to facebook and/or twitter to share your prediction prowess with your friends and followers. You’ll earn bonus points and my eternal gratitude.

The odds start off at our own prior estimate based on seeds and (new this year) the current scores of ongoing games, but ultimately settle to values set by “the crowd” — that means you — as predictions are bought and sold.

Yahoo! Labs Predictalot version 0.3 overview tab screenshot

For the math geeks, Predictalot is a combinatorial prediction market with over 9 quintillion outcomes. Prices are computed using an importance sampling approximation of a #P-hard problem.

What kind of information can we collect that a standard prediction market cannot? A standard market will say that Texas A&M is unlikely to win the tournament. Our market can say more. Yes, A&M is unlikely to reach the Final Four and even more unlikely to win apriori, but given that they somehow make it to the semifinals in Houston, less than a two hour drive from A&M’s campus, their relative odds may increase due to a home court advantage.

Here’s another advantage of the combinatorial setup. A standard bookmaker would never dare to offer the same millions of bets as Predictalot — they would face nearly unlimited possible losses because, by tradition, each bet is managed independently. By combining every bet into a single unified marketplace, we are able to limit the worst-case (virtual) loss of our market maker to a known fixed constant.

Predictalot goes East: Introducing Predictopus for the ICC Cricket World Cup

Yahoo! India Predictopus logo

I’m thrilled to report that Predictalot had an Indian makeover, launching as Predictopus* for the ICC Cricket World Cup. The Yahoo! India team did an incredible job, leveraging the idea and some of the code base of Predictalot, yet making it their own. Predictopus is not a YAP — it lives right on the Yahoo! Cricket website, the official homepage for the ICC Cricket World Cup. They’re also giving away Rs 10 lakhs — or about $22,000 if my calculations are correct — in prizes. Everything is bigger in India, including the crowds and the wisdom thereof. It will be great to see the game played out on a scale that dwarfs our college basketball silliness in the US.

The Y! India team reused some of the backend code but redid the frontend almost entirely. To adapt the game to cricket, among other chores, we had to modify our simulation code to estimate the starting probabilities that any team would win against any other team, even in the middle of a game. (How likely is it for India to come back at home from down 100 runs with 10 overs left and 5 wickets lost? About 25%, we think.) These starting probabilities are then refined further by the game-playing crowds.

It’s great to see an experiment from Labs grow into a full-fledged product run by a real product team in Yahoo!, a prime example of technology transfer at its best. In the meantime, we (Labs) are still gunning for a relaunch of Predictalot itself for March Madness 2011, the second year in a row. Stay tuned.

2011/02/24 Update: An eye-catching India-wide ad campaign for predictopus is live, including homepage, finance, movies, OMG, answers, mail, everywhere! Oh, and one of the prizes is a Hyundai.

predictopus ad on Yahoo! India homepage 2011/02/24


* Yes, that’s a reference to legendary Paul the Octopus, RIP.

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:

Countdown to web sentience

In 2003, we wrote a paper titled 1 billion pages = 1 million dollars? Mining the web to play Who Wants to be a Millionaire?. We trained a computer to answer questions from the then-hit game show by querying Google. We combined words from the questions with words from each answer in mildly clever ways, picking the question-answer pair with the most search results. For the most part (see below), it worked.

It was a classic example of “big data, shallow reasoning” and a sign of the times. Call it Google’s Law. With enough data nothing fancy can be done, but more importantly nothing fancy need be done: even simple algorithms can look brilliant. When in comes to, say, identifying synonyms, simple pattern matching across an enormous corpus of sentences beats the most sophisticated language models developed meticulously over decades of research.

Our Millionaire player was great at answering obscure and specific questions: the high-dollar questions toward the end of the show that people find difficult. It failed mostly on the warm-up questions that people find easy — the truly trivial trivia. The reason is simple. Factual answers like the year that Mozart was born appear all over web. Statements capturing common sense for the most part do not. Big data can only go so far.*

That was 2003.

In the paper, our clearest example of a question that we could not answer was How many legs does a fish have?. No one on the web would actually bother to write down the answer to that. Or would they?

I was recently explaining all this to a colleague. To make my point, we Googled that question. Lo and behold, there it was: asked and answered — verbatim — on Yahoo! Answers. How many legs does a fish have? Zero. Apparently Yahoo! Answers also knows the number of legs of a crayfish, rabbit, dog, starfish, mosquito, caterpillar, crab, mealworm, and “about 133,000″ more.

Today, there are way more than 1 billion web pages: maybe closer to 1 trillion.

What’s the new lesson? Given enough time, everything will be on the web, including the fact that hungry poets blink (✓). Ok, not everything, but far more than anyone ever imagined.

It would be fun to try our Millionaire experiment again now that the web is bigger and search engines are smarter. Is there some kind of Moore’s Law for artificial intelligence as the web grows? Can sentience be far behind? :-)

__________
* Lance agreed, predicting that IBM’s quest to build a Jeopardy-playing computer would succeed but not tell us much.

Predictalot! (And we mean alot)

I’m thrilled to announce the launch of Predictalot, a combinatorial prediction market for the NCAA Men’s Basketball playoffs. Predict almost anything you can think of, like Duke will advance further than UNC, or Every final four team name will start with U. Check the odds and invest points on your favorites. Sell your predictions anytime, even as you follow the basketball games live.

The basic game play is simple: select a prediction type, customize it, and invest points on it. Yet you’ll never run out of odds to explore: there are hundreds of millions of predictions you can make. The odds on each update continuously based on other players’ predictions and the on-court action.

Predictalot is a Yahoo! App, so you can play it at apps.yahoo.com or you can add it to your Yahoo! home page. I have to admit, it’s an incredible feeling to play a game I helped design right on the Yahoo! home page.

Predicalot app on the Yahoo! home page

That’s all you need to get started. If you’re curious and would like a peek under the hood, read on: there’s some interesting technology hidden in the engine.

Background and Details

Predictalot is a true combinatorial prediction market of the sort academics like us and Robin Hanson have been dreaming about since early in the decade. We built the first version during an internal Yahoo! Hack Day. Finally, we leveraged the Yahoo! Application Platform to quickly build a public version of the game. (Note that anyone can develop a YAP app that’s visible to millions — there’s good sample code, it supports YUI and OpenSocial, and it’s easy to get started.) After many fits and starts, late nights, and eventually all nights, we’re proud and excited to go live with Predictalot version 1.0. I can’t rave enough about the talent and dedication of the research engineers who gave the game a professional look and feel and production speed, turning a pie-in-the-sky idea into reality. We have many features and upgrades in mind for future versions, but the core functionality is in place and we hope you enjoy the game.

In the tournament, after the play-in game, the 64 top college basketball teams play 63 games in a single elimination tournament. So there are 2 to the power 63 or 9.2 quintillion total possible outcomes, or ways the entire tournament can unfold. Predictalot implicitly keeps track of the odds for them all. To put this in perspective, it’s estimated that there are about 10 quintillion individual insects on Earth. Of course, for all practical purposes, we can’t store 9.2 quintillion numbers, even with today’s computers. Instead, we compute the odds for any outcome on the fly by scanning through the predictions placed so far.

A prediction is a statement, like Duke will win in the first round, that will be either true or false in the final outcome. In this case, the prediction is true in exactly half, or 2 to the power 62 outcomes. (Note this does not mean the odds are 50% — remember the outcomes themselves are not all equally likely.) In theory, Predictalot can support predictions on any set of outcomes. That’s 2 to the power 2 to the power 63, or more than a googol predictions. For now, we restrict you to “only” hundreds of millions of predictions categorized into thirteen types. Computing the odds of a prediction precisely is too slow. Technically, the problem is #P-hard: as hard as counting SAT and harder than the travelling salesman problem. So we must resort to approximating the odds by randomly sampling the outcome space. Sampling is a tricky business — equal parts art and science — and we’re still actively exploring ways to increase the speed, stability, and accuracy of our sampling.

Because we track all possible outcomes, the predictions are automatically interconnected in ways you would expect. A large play on Duke to win the tournament instantly and automatically increases the odds of Duke winning in the first round; after all, Duke can’t win the whole thing without getting past the first round.

With 9.2 quintillion outcomes, Predictalot is to our knowledge the largest prediction market built, testing the limits of what the wisdom of crowds can produce. Predictalot is a game, and we hope it’s fun to play. We’d also like to pave the way for serious use of combinatorial prediction market technology.

Why did Yahoo! build this? Predictalot is a smarter market, letting humans and computers each do what they do best. People enter predictions in simple terms they understand like how one team fares against another. The computer handles the massive yet methodical number crunching needed to combine all the pieces together into a coherent overall prediction of a complex event. Markets like Predictalot, WeatherBill, CombineNet, and Internet advertising systems, to name a few, represent the evolution of markets in the digital age, empowering users with extreme customization. More and more, matching buyers with sellers — the core function of markets — requires sophisticated algorithms, including machine learning and optimization. Predictalot attempts to illustrate this trend in an entertaining way.

David Pennock
Mani Abrol, Janet George, Tom Gulik, Mridul Muralidharan, Sudar Muthu, Navneet Nair, Abe Othman, Daniel Reeves, Pras Sarkar