Oddhead Blog

I am happy to announce the following prediction market workshop and solicit submissions and participants.

or email the organizing committee: pm2008@umich.edu

I am happy to announce the following ad auctions workshop and solicit submissions and participants.

or email the organizing committee:
adauctions2008@yahoogroups.com

Here are two Call For P*s for upcoming academic/research conferences:

1. Call for Participation: For the first time, the World Wide Web Conference has a track on Internet Monetization, including topics in electronic commerce and online advertising. The conference will be held in Beijing April 21-25, 2008. If the Olympics in China are all about image, then the Internet in China is all about, well, Monetization. (A lot of it, growing fast.)
2. Call for Papers: The 2008 ACM Conference on Electronic Commerce will be held in Chicago July 8-12, 2008 in proximity to AAAI-08 and GAMES 2008. Research papers on all aspects of electronic commerce — including personal favorites prediction markets and online advertising — are due February 7, 2008.

You can signal your interest on social events calendar upcoming.org: WWW2008 | EC’08

Hope to see some of you in either the Forbidden or Windy City, as the case may be.

Rahul Sami and I wrote a chapter called “Computational aspects of prediction markets” in the book Algorithmic Game Theory, Cambridge University Press, forthcoming 2007.

You can download an almost-final version of our chapter here.

Update 2007/09/19: You can now also download the entire book Algorithmic Game Theory: username agt1user , password camb2agt . If you like it, you can buy it.

In the course of writing the chapter, we compiled an extended annotated bibliography that ended up being too long to publish in its entirety in the book. So we trimmed the bibliographic notes in the book to cover only the most directly relevant citations. You can download the full extended bibliography here.

Here is the abstract of our chapter:

Prediction markets (also known as information markets) are markets established to aggregate knowledge and opinions about the likelihood of future events. This chapter is intended to give an overview of the current research on computational aspects of these markets. We begin with a brief survey of prediction market research, and then give a more detailed description of models and results in three areas: the computational complexity of operating markets for combinatorial events; the design of automated market makers; and the analysis of the computational power and speed of a market as an aggregation tool. We conclude with a discussion of open problems and directions for future research.

If you’re interested in this topic, you might also take a look at our recent paper on Betting on permutations, published after the book chapter was completed.

Finally, for a higher-level treatment, here is a pre-print version of a short letter on “Combinatorial betting” that we submitted to SIGecom Exchanges.

Earlier this month, I spent a few days in lovely Banff, Alberta, Canada, at WWW2007, the 16th International World Wide Web Conference. Here are my thoughts from the event. [See also: Yahoo! Research’s writeup.]

It’s becoming clear that other sciences beyond computer science, including economics and sociology, are necessary for understanding the web and realizing its full potential. This theme ran through both Tim Berners-Lee’s and Prabhakar Raghavan’s plenary talks. For every new advance in the web, once it reaches critical mass, the economic incentives to manipulate the system inevitably emerge. Email led to spam. Altavista led to keyword spam. Google led to link spam. Blogs led to comment and trackback spam. Folksonomies led to tag spam. Recommender systems and aggregators (e.g., Digg) led to shilling. It’s clear that a better understanding of incentives, game theory, and system equilibrium is needed, beyond just cool engineering feats. The University of Michigan calls this incentive-centered design and has a world-class research team exploring the topic; see Jeff MacKie-Mason’s blog ICD Stuff for an interesting and accessible discussion. Yahoo! Research is also betting on the importance of human incentives, building a group of economists and sociologists to complement our contingent of computer scientists.

Among conference events, nowhere was the convergence of economics and computer science more clear than at the Third Workshop on Sponsored Search Auctions. The workshop is a rare venue where terms like Nash equilibrium and NP-complete can coexist in harmony. The workshop explored the intricacies of web search advertising, a multi-billion dollar industry experiencing rapid growth. Contributions included new designs for auctioning off advertising space, new analyses of the systems currently used by search engines, new tools to help advertisers, and empirical studies of the industry. Participants included representatives from both academia and industry, including economists, computer scientists, search engine employees (including representatives from the “big three”: Google, Microsoft, and Yahoo!), and search engine marketers. Yahoo! had a large presence at the workshop: Yahoo! scientists (including me) served on the organizing committee, Yahoo! employees and interns presented six of the fourteen peer-reviewed papers, and many Yahoos attended, contributing to their voice to the discussion of this emerging field.

Bradley Horowitz’s talk also emphasized the new web order, where artists are needed as much as technologists: artists who can envision, create, and orchestrate online communities can be the difference between mass adoption and a flop.

An interesting addition to the WWW program was the Web History track and the Web History Center. Some of the talks were fascinating. Hermann Maurer recounted stories of interactive TV products that proliferated in Europe in the 1970’s and that mirrored almost everything that is done on the Web today in a primitive form. [Some keywords to search for if you’re interested: PRESTEL, Teletel/Minitel (France), MUPID (Austria).] For example, one massive multiplayer game, which involved social exploration of 64 million virtual planets, each with a hidden secret, was so wildly popular that it crashed the network. The apparent winner of the contest returned his prize, admitting that he didn’t actually solve for the secrets, but rather hacked into the system and reverse engineered the code. This pre-Internet system even featured some things I’m still waiting for on today’s web, like micropayments.

We’re soliciting research paper submissions and participants for the Second Workshop on Prediction Markets, to be held June 12, 2007 in San Diego, California, in conjunction with the ACM Conference on Electronic Commerce and the Federated Computing Research Conference. The workshop will have an academic/research bent, though we welcome both researchers and practitioners from academia and industry to attend to discuss the latest developments in prediction markets.

See the workshop homepage for more details and information.

You can signal your intent to attend at upcoming.org, though official registration must go through the EC’07 conference.

Here is a fluffy post for a fluffy (but important) topic: the economics of attention.

Yahoo! is in the business of monetizing attention: that’s essentially what advertising is all about. We (Yahoo!) attract users’ attention by providing content, usually free, then diverting some of that attention to our paying advertisers. Increasingly users’ attention is one of the most valuable commodities in the world. This trend will only accelerate as energy becomes cheaper and more abundant, and thus everything we derive from energy (that is, everything) becomes cheaper and more abundant, on our way to a post-scarcity society, where attention is nearly the only constrained resource.

Today, users generally accept content and entertainment in return for their attention, though likely in the future users will be more savvy in directly monetizing their own attention. I’ve heard a number of companies and organizations large and small discuss direct user compensation. Beyond advertising, the economics of attention is important for the future of communication in general.

I haven’t found much academic writing on the topic, though I haven’t looked thoroughly. John Hagel’s piece “The Economics of Attention” is a good start, and he looks to have compiled some nice resources on the topic, though I haven’t yet investigated closely.

An organization that has garnered some attention of their own (of the Web 2.0 buzz variety) is Attention Trust. I find the description on their own website vague and impenetrable. The best explainer on Attention Trust I could find is PC4Media’s, though questions remain. The basic concept is simple enough: users should be empowered to control and monetize their own attention, including the output of their attention (e.g., their click trails, personal data, etc.). Just how Attention Trust plans to hand this power to the people seems to be the hand-wavy part of their story.

Another interesting company in this space is Root Markets, whose business is to connect both sides of the attention market in an attempt to commoditize attention. Their first product is much more specific than that: an exchange for mortgage leads.

If the absence of formal models of the economics of attention is real — and not simply a matter of my own ignorance — than it may be that some economist can make a career by truly tackling the topic in a precise and thorough way.

One of the purest and most fascinating examples of the “wisdom of crowds” in action comes courtesy of a unique online contest called ProbabilitySports run by mathematician Brian Galebach.

In the contest, each participant states how likely she thinks it is that a team will win a particular sporting event. For example, one contestant may give the Steelers a 62% chance of defeating the Seahawks on a given day; another may say that the Steelers have only a 44% chance of winning. Thousands of contestants give probability judgments for hundreds of events: for example, in 2004, 2,231 ProbabilityFootball participants each recorded probabilities for 267 US NFL Football games (15-16 games a week for 17 weeks).

An important aspect of the contest is that participants earn points according to the quadratic scoring rule, a scoring method designed to reward accurate probability judgments (participants maximize their expected score by reporting their best probability judgments). This makes ProbabilitySports one of the largest collections of incentivized¹ probability judgments, an extremely interesting and valuable dataset from a research perspective.

The first striking aspect of this dataset is that most individual participants are very poor predictors. In 2004, the best score was 3747. Yet the average score was an abysmal -944 points, and the median score was -275. In fact, 1,298 out of 2,231 participants scored below zero. To put this in perspective, a hypothetical participant who does no work and always records the default prediction of “50% chance” for every team receives a score of 0. Almost 60% of the participants actually did worse than this by trying to be clever.

Participants are also poorly calibrated. To the right is a histogram dividing participants’ predictions into five regions: 0-20%, 20-40%, 40-60%, 60-80%, and 80-100%. The y-axis shows the actual winning percentages of NFL teams within each region. Calibrated predictions would fall roughly along the x=y diagonal line, shown in red. As you can see, participants tended to voice much more extreme predictions than they should have: teams that they said had a less than 20% chance of winning actually won almost 30% of the time, and teams that they said had a greater than 80% chance of winning actually won only about 60% of the time.

Yet something astonishing happens when we average together all of these participants’ poor and miscalibrated predictions. The “average predictor”, who simply reports the average of everyone else’s predictions as its own prediction, scores 3371 points, good enough to finish in 7th place out of 2,231 participants! (A similar effect can be seen in the 2003 ProbabilityFootball dataset as reported by Chen et al. and Servan-Schreiber et al.)

Even when we average together the very worst participants — those participants who actually scored below zero in the contest — the resulting predictions are amazingly good. This “average of bad predictors” scores an incredible 2717 points (ranking in 62nd place overall), far outstripping any of the individuals contributing to the average (the best of whom finished in 934th place), prompting someone in this audience to call the effect the “wisdom of fools”. The only explanation is that, although all these individuals are clearly prone to error, somehow their errors are roughly independent and so cancel each other out when averaged together.

Daniel Reeves and I follow up with a companion post on Robin Hanson’s OvercomingBias forum with some advice on how predictors can improve their probability judgments by averaging their own estimates with one or more others’ estimates.

In a related paper, Dani et al. search for an aggregation algorithm that reliably outperforms the simple average, with modest success.

Robin Hanson invented a wonderful market maker well suited for use in prediction market applications with a long name: the logarithmic market scoring rule market maker, which I’ll abbreviate as LMSR. (In fact, Hanson invented an entire class of market scoring rule market makers, but the logarithmic variant seems the most useful.) Hanson’s two papers on the subject are excellent, but Hanson does not spend a lot of time explaining how LMSR functions as a market maker in the typical sense. Instead, Hanson mostly emphasizes a second, alternate way of thinking about his market maker, as a “sequential shared scoring rule”, which I will not try to explain here. Hanson prefers to describe trader behavior in terms of “changing the price” instead of “buying and selling shares”. In my opinion, most people who encounter LMSR for the first time don’t quite see how beautifully and naturally LSMR can be used as a market maker in a standard prediction market setting. In fact, I am embarrassed to admit that upon my own first reading of Hanson’s papers, I did not fully “get it”. It took my seeing LMSR implemented in practice, by Todd Proebsting at Microsoft Research for Microsoft’s internal prediction markets, to realize how elegantly LMSR can be used as a market maker in an otherwise typical prediction market. LMSR is now being used in several places, including an implementation at InklingMarkets with a wonderfully intuitive interface, the Washington Stock Exchange, BizPredict, and (reportedly) at YooNew. Net Exchange was one of the first to use LMSR, though they seem to favor Hanson’s “change the price” interface over the more widespread “buy and sell shares” interface. As Chris Masse is quick to point out, LMSR has achieved much more widespread use than my own competing invention, the dynamic parimutuel market maker, which so far is being used in only one place: our own Yahoo! Tech Buzz Game.

In this post I will try to explain how to implement LMSR in a way that I believe most people familiar with prediction markets will understand. This interpretation of LMSR is not new: it’s the way Proebsting thinks about LMSR and it’s implicit “between the lines” in Hanson’s papers. But I haven’t seen this interpretation of LMSR written up anywhere, so I’m hoping that others can benefit from this explanation. The following understanding of LMSR was developed over the past few months together with my colleague Yiling Chen.

Suppose there are two outcomes that traders can buy or sell shares of (bet on or against) such that one and only one of the two outcomes is guaranteed to eventually occur. For example, the two outcomes could be “a Democrat wins the 2008 US Presidential election” and “a Democrat does not win the 2008 US Presidential election”. Each share is worth exactly $1 if and only if the trader is correct. In other words, one share of “Democrat wins” pays $1 if, in 2008, a Democrat actually wins the election, and is worthless otherwise. The following description can be easily generalized to any number of (disjoint and exhaustive) outcomes, including the case of combinatorial markets, but for ease of exposition I’ll stick to the two-outcome case.

The market maker keeps track of how many shares have been purchased by traders in total so far for each outcome: that is, the number of shares outstanding for each outcome. Let q1 and q2 be the number (”quantity”) of shares outstanding for each of the two outcomes. The market maker also maintains a cost function C(q1,q2) which records how much money traders have collectively spent so far, and depends only on the number of shares outstanding, q1 and q2. For LMSR, the cost function is:

where “ln” is the natural logarithm function, “e” is the constant e=2.718…, and “b” is a parameter that the market maker must choose. The parameter “b” controls the maximum possible amount of money the market maker can lose (which happens to be b*ln2 in the two-outcome case). The larger “b” is, the more money the market maker can lose. But a larger “b” also means the market has more liquidity or depth, meaning that traders can buy more shares at or near the current price without causing massive price swings.

Traders arrive one at a time and tell the market maker how many shares they want to buy or sell of each outcome. Traders say, for example, “I want to buy 13 shares of outcome 1 — how much will that cost?”, or “I want to sell 250 shares of outcome 2 — how much will you pay me?”. The market maker uses the cost function to answer these questions. The cost to buy 13 shares of outcome 1 is simply C(q1+13,q2) - C(q1,q2). The “cost” to sell 250 shares of outcome 2 is C(q1,q2-250) - C(q1,q2), which will be a negative number (negative cost), meaning that the seller receives money in return for the shares. In general, if a trader wants to buy or sell shares of either or both outcomes so as to change the number of shares outstanding from (q1,q2) to (q1*,q2*), then he or she must pay C(q1*,q2*) - C(q1,q2) dollars. If this amount is negative it means the trader receives money instead of paying money.

Here’s a simple example. Suppose b=100 and no one has purchased any shares yet, so q1=q2=0. A trader arrives who wants to buy 10 shares of outcome 1. The trader must pay:

Now suppose that at some time later, the number of shares outstanding for outcome 1 is q1=50 and the number of shares outstanding of outcome 2 is q2=10. Now the same trader above returns to the market and wants to sell her 10 shares. The trader’s “payment” is:

This is a negative number so it means the trader receives $5.87. So in the end the trader made a round-trip profit of $0.75.

That’s it! Well, almost. If the market maker wants to quote a “current price”, he can. The current price for outcome 1 is:

and similarly for price2. But note that the current price only applies for buying a miniscule (infinitesimal, in fact) number of shares. As soon as a trader starts buying, the price immediately starts going up. In order to figure out the total cost for buying some number of shares, we should use the cost function C, not the price function. (If you remember your calculus: The total cost for buying k of shares of outcome 1 is the integral of the price function from q1 to q1+k. The price function (”price1″) is the derivative of the cost function C with respect to q1, and the cost function is the integral of the price function.)

Finally, although I won’t go into the details here, one can generalize the above so that the market maker can handle limit orders, for example an order to “buy up to 100 shares of outcome 1, each at price less than or equal to $0.80″. But if unfilled limit orders like this are allowed to persist, the market maker logic can get a little complicated.

As I mentioned, Hanson actually invented an entire class of market makers: he shows how to turn any proper scoring rule into a market maker. Yiling Chen and I have derived the cost and price functions corresponding to the quadratic scoring rule. It turns out, however, that the quadratic scoring rule market maker is not very interesting or useful in practice. I’ll save the details for another day. We’re also working on additional classes of market makers that do seem useful, results we hope to report on soon.