Category Archives: finance

A beautiful model (of the stock market)

Here is a histogram of the daily changes of the S&P 500 from 1950 to 2009. The x-axis is the daily log difference* and the y-axis is the number of times that difference occurred.

Histogram of log differences of S&P500 from 1950 to 2009

It turns out that a Laplace distribution is a pretty good model of the stock market. The Laplace distribution is parametrized by its median u and its average absolute difference from median b. I computed these two parameters for the S&P 500 data and plugged them into a Laplace distribution in Mathematica, then used that to generate 59 years worth of random simulated S&P 500 prices. Here is the resulting histogram.

Histogram of log differences of simulated S&P500

This is not a best fit: this is simply the same u and b computed on the data and then plugged into the distribution. Here are the two histograms on top of each other.

Histogram of log differences of S&P500 from 1950 to 2009 and simulated S&P 500

At the aggregate level the stock market is well behaved: it’s randomness is remarkably predictable. It’s amazing that this social construct — created by people for people, and itself often personified — behaves so much like a physical process, more so than any other man-made entity I can think of.

The graphs also hint at the futility of attaching reasons to price movements every single day. Today, “the prospects for continued low borrowing costs buoyed investors’ hopes for the U.S. economy”. Tomorrow, there may be “profit taking”.** Why do reporters feel obligated to explain why, or more to the point why do readers demand to be told? Why must we infer reasons, see momentum where there may be none, and assign labels like bull and bear? Why can’t we accept randomness?***

Update: Anthony Towns conducted a fascinating and puzzling follow-up analysis showing that the volatility of the stock market has been going up steadily over the years, even though the mean return has not.
* The log difference is the log of the price on day d minus the log of the price on day d-1, or equivalently ln(d/(d-1)).
** I’d love to see a controlled experiment where financial reporters are given randomized reports about the Dow and watch them manufacture explanations, I imagine occasionally invoking the same cause for both ups and downs… (a) The prospect of higher interest rates spooked investors today; or (b) the Fed’s willingness to raise rates signals a recovering economy — investors rejoiced.
*** Let me clarify. The efficient market hypothesis implies both randomness and rationality: Randomness in the sense of statistical independence (no momentum), and rationality in the sense that price changes reflect new information. So I’m not saying that prices change for no reason, just that there is rarely an easily-stated single explanation for the overall market. (BTW, “profit taking” is never a valid explanation under EMH.)

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

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 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

Review of Fortune’s Formula by William Poundstone: The stranger-than-fiction tale of how to invest

What is a better investment objective?

  1. Grow as wealthy as possible as quickly as possible, or
  2. Maximize expected wealth for a given time period and level of risk

The question is at the heart of a fight between computer scientists and economists chronicled beautifully in the book Fortune’s Formula by Pulitzer Prize nominee William Poundstone. (See also David Pogue’s excellent review.*) From the book’s sprawling cast — Claude Shannon, Rudy Giuliani, Michael Milken, mobsters, and mob-backed companies (including what is now Time Warner!) — emerges an unlikely duel. Our hero, mathematician turned professional gambler and investor Edward Thorp, leads the computer scientists and information theorists preaching and, more importantly, practicing objective #1. Nobel laureate Paul Samuelson (who, sadly, recently passed away) serves as lead villain (and, to an extent, comic foil) among economists promoting objective #2 in often patronizing terms. The debate sank to surprisingly depths of immaturity, hitting bottom when Samuelson published an economist-peer-reviewed article written entirely in one-syllable words, presumably to ensure that his thrashing of objective #1 could be understood by even its nincompoop proponents.

Objective #1 — The Kelly criterion

Objective #1 is the have-your-cake-and-eat-it-too promise of the Kelly criterion, a money management formula first worked out by Bernoulli in 1738 and later rediscovered and improved by Bell Labs scientist John Kelly, proving a direct connection between Shannon-optimal communication and optimal gambling. Objective #1 matches common sense: who wouldn’t want to maximize growth of wealth? Thorp, college professor by day and insanely successful money manager by night, is almost certainly the greatest living example of the Kelly criterion at work. His track record is hard to refute.

If two twins with equal wealth invest long enough, the Kelly twin will finish richer with 100% certainty.

The Kelly criterion dictates exactly what fraction of wealth to wager on any available gamble. First consider a binary gamble that, if correct, pays $x for every $1 risked. You estimate that the probability of winning is p. As Poundstone states it, the Kelly rule says to invest a fraction of your wealth equal to edge/odds, where edge is the expected return per $1 and odds is the payoff per $1. Substituting, edge/odds = (x*p – 1*(1-p))/x. If the expected return is zero or negative, Kelly sensibly advises to stay away: don’t invest at all. If the expected return is positive, Kelly says to invest some fraction of your wealth proportional to how advantageous the bet is. To generalize beyond a single binary bet, we can use the fact that, as it happens, the Kelly criterion is entirely equivalent to (1) maximizing the logarithm of wealth, and (2) maximizing the geometric mean of gambles.

Investing according to the Kelly criterion achieves objective #1. The strategy provably maximizes the growth rate of wealth. Stated another way, it minimizes the time it takes to reach any given aspiration level, say $1 million, or your desired sized nest egg for retirement. If two twins with equal initial wealth were to invest long enough, one according to Kelly and the other not, the Kelly twin would finish richer with 100% certainty.

Objective #2

Objective #2 refers to standard economic dogma. Low-risk/high-return investments are always preferred to high-risk/low-return investments, but high-risk/high-return and low-risk/low-return are not comparable in general. Deciding between these is a personal choice, a function of the decision maker’s risk attitude. There is no optimal portfolio, only an efficient frontier of many Pareto optimal portfolios that trade off risk for return. The investor must first identify his utility function (how much he values a dollar at every level of wealth) in order to compute the best portfolio among the many valid choices. (In fact, objective #1 is a special case of #2 where utility for money is logarithmic. Deriving rather than choosing the best utility function is anathema to economists.)

Objective #2 is straightforward for making one choice for a fixed time horizon. Generalizing it to continuous investment over time requires intricate forecasting and optimization (which Samuelson published in his 1969 paper “Lifetime portfolio selection by dynamic stochastic programming”, claiming to finally put to rest the Kelly investing “fallacy” — p.210). The Kelly criterion is, astonishingly, a greedy (myopic) rule that at every moment only needs to worry about figuring the current optimal portfolio. It is already, by its definition, formulated for continuous investment over time.

Details and Caveats

There is a subtle and confusing aspect to objective #1 that took me some time and coaching from Sharad and Dan to wrap my head around. Even though Kelly investing maximizes long-term wealth with 100% certainty, it does not maximize expected wealth! The proof of objective #1 is a concentration bound that appeals to the law of large numbers. Wealth is, eventually, an essentially deterministic quantity. If a billion investors played non-Kelly strategies for long enough, then their average wealth might actually be higher than a Kelly investor’s wealth, but only a few individuals out of the billion would be ahead of Kelly. So, non-Kelly strategies can and will have higher expected wealth than Kelly, but with probability approaching zero. Note that, while Kelly does not maximize expected (average) wealth, it does maximize median wealth (p.216) and the mode of wealth. See Chapter 6 on “Gambling and Data Compression” (especially pages 159-162) in Thomas Cover’s book Elements of Information Theory for a good introduction and concise proof.

Objective #1 does have important caveats, leading to legitimate arguments against pure Kelly investing. First, it’s often too aggressive. Sure, Kelly guarantees you’ll come out ahead, but only if investing for “long enough”, a necessarily vague phrase that could mean, well, infinitely long. (In fact, a pure Kelly investor at any time has a 1 in n chance of losing all but 1/n of their wealth — p.229) The guarantee also only applies if your estimate of expected return per dollar is accurate, a dubious assumption. So, people often practice what is called fractional Kelly, or investing half or less of whatever the Kelly criterion says to invest. This admittedly starts down a slippery slope from objective #1 to objective #2, leaving the mathematical high ground of optimality to account for people’s distaste for risk. And, unlike objective #2, fractional Kelly does so in a non-principled way.

Even as Kelly investing is in some ways too aggressive, it is also too conservative, equating bankruptcy with death. A Kelly strategy will never risk even the most minuscule (measure zero) probability of losing all wealth. First, the very notion that each person’s wealth equals some precise number is inexact at best. People hold wealth in different forms and have access to credit of many types. Gamblers often apply Kelly to an arbitrary “casino budget” even though they’re an ATM machine away from replenishment. People can recover nicely from even multiple bankruptcies (see Donald Trump).

Some Conjectures

Objective #2 captures a fundamental trade off between expected return and variance of return. Objective #1 seems to capture a slightly different trade off, between expected return and probability of loss. Kelly investing walks the fine line between increasing expected return and reducing the long-run probability of falling below any threshold (say, below where you started). There are strategies with higher expected return but they end in ruin with 100% certainty. There are strategies with lower probability of loss but that grow wealth more slowly. In some sense, Kelly gets the highest expected return possible under the most minimal constraint: that the probability of catastrophic loss is not 100%. [Update 2010/09/09: The statements above are not correct, as pointed out to me by Lirong Xia. Some non-Kelly strategies can have higher expected return than Kelly and near-zero probability of ruin. But they will do worse than Kelly with probability approaching 1.]

It may be that the Kelly criterion can be couched in the language of computational complexity. Let Wt be your wealth at time t. Kelly investing grows expected wealth exponentially, something like E[Wt] = o(xt) for x>1. It simultaneously shrinks the probability of loss, something like Pr(Wt< T) = o(1/t). (Actually, I have no idea if the decay is linear: just a guess.) I suspect that relaxing the second condition would not lead to much higher expected growth, and perhaps that fractional Kelly offers additional safety without sacrificing too much growth. If formalized, this would be some sort of mixed Bayesian and worst-case argument. The first condition is a standard Bayesian one: maximize expected wealth. The second condition — ensuring that the probability of loss goes to zero — guarantees that even the worst case is not too bad.


Fortune’s Formula is vastly better researched than your typical popsci book: Poundstone extensively cites and quotes academic literature, going so far as to unearth insults and finger pointing buried in the footnotes of papers. Pounstone clearly understands the math and doesn’t shy away from it. Instead, he presents it in a detailed yet refreshingly accessible way, leveraging fantastic illustrations and analogies. For example, the figure and surrounding discussion on pages 197-201 paint an exceedingly clear picture of how objectives #1 and #2 compare and, moreover, how #1 “wins” in the end. There are other gems in the book, like

  • Kelly’s quote that “gambling and investing differ only by a minus sign” (p.75)
  • Louis Bachelier’s discovery of the efficient market hypothesis in 1900, a development that almost no one noticed until after his death (p.120)
  • Poundstone’s assertion that “economists do not generally pay much attention to non-economists” (p.211). The assertion rings true, though to be fair applies to most fields and I know many glaring exceptions.
  • The story of the 1998 collapse of Long-Term Capital Management and ensuing bailout is sadly amusing to read today (p.290). The factors are nearly identical to those leading to the econalypse of 2008: leverage + correlation + too big to fail. (Poundstone’s book was published in 2005.) Will we ever learn? (No.)

Fortune’s Formula is a fast, fun, fascinating, and instructive read. I highly recommend it.

* See my bookmarks for other reviews of the book and some related research articles.

Microfunding: the next big small thing?

First micro lending, then microblogging, now microfunding.* Announcements of three funds recently sixdegreed their way to my doorstep, each smaller and faster than the next, a trend iconified by the famously speedy and minuscule Y Combinator:

1) George “Greek geek” Tziralis’s openfund; 2) Kevin Dick’s Black Swan Fund [via Daniel Horowitz]; and 3) the Awesome Foundation [via Foo Camp list].

The beginning of a trend?

Update 2010/03/19: The Black Swan fund, now called RightSide Capital is open for business.


*Yet still no micropayments! 🙁

Thank you Bangalore

Sunday I returned from a trip to Bangalore, India, where I gave a talk on “The Automated Economy” about how computers can and should take over the mechanical aspects of economic activity, optimizing and learning from data in the way people cannot, with detailed case studies in online advertising and prediction markets. You can read the abstract, watch archive video of the talk, view my talk slides, browse the official pictures of the event, or see my personal pictures of the trip.

Some say everything’s bigger in Texas (most vociferously Texans). They haven’t been to India. My talk is part of Yahoo!’s Big Thinkers India series — four talks a year from (so far) Yahoo! Research speakers. If the Thinking isn’t Big, the crowds certainly are — the events can draw close to 1000 attendees from, apparently, all over India. Duncan Watts says its the largest crowd he’s spoken too; me too. This time they disallowed Yahoo! employees to attend the main event and the hotel ballroom still filled to capacity.

Here is a linked-up version of my journal entry for the trip, a kind of windy and winded thank you letter to Bangalore. If you’re not interested in personal details, you might skip to Thoughts on Bangalore.

Getting there

The Philadelphia airport international terminal is dead empty. I breeze through security — the only one in line. I’m inside security two hours early thinking that either the recession is still in full force or traveling internationally on a Monday night out of Philadelphia is the best ever. Maybe not. Get on plane. Wait two hours on tarmac. Apparently a two hour layover isn’t enough leeway on international flights. Miss my connecting flight in Frankfurt by a few minutes. Team up with a fellow passenger in the same boat. We are rebooked via Dubai. Fly directly over Bagdad. Dubai is an impressive airport. Endless terminals lined with upscale shopping. Packed with Asians, Europeans at midnight and beyond. From there, Emerites Air to Bangalore. Only 9 hours behind schedule. Sneezing fits begin after 28 hours of airplane air.

Day 0: Yahoo! internal practice talk

Driver right there outside baggage claim, nice guy. Takes me to hotel. Over an hour. Traffic. Time for shower, NeilMed nasal rinses (bottled water), Sudafed, but not sleep. Call home. Yahoo! Messenger with Voice doesn’t roll off the tongue like ‘Skype’, but it rocks. Super clear and dirt cheap. Lauren and the girls are so sweet. Miss them. To Yahoo! office. Meet Anita, Mani. Time for Yahoo! internal version of Big Thinkers talk. Nose is still running. Drips and wipes during my talk. Talk goes well but I run out of time for prediction market section and this seems what people are most interested in. I’m glad I had the practice run to work out the kinks and rebalanced the talk. Back to hotel. Call home again for a recharging dose of home. I missed Ashley’s graduation from pre-school: she did great: they sang six songs and she knew them all. She was dressed up in a yellow cap and gown. I’m upset I had to miss such an adorable milestone but am proud of my little girl (and dismayed she is rapidly becoming not so little!). More NeilMed. Room service. (Called “private dining” here — sounds illicit.) Sleep! For a few hours at least. Wake up in the middle of the night since it’s NY daytime. Finally get back to sleep again.

Day 1: Meetings

Hard to wake up at 9am = midnight. Shower. Feel 1000% better. Driver takes me to the Yahoo! office. It’s in a complex with Microsoft, Google, Target, Dell, and many other US brands. Once you’re inside it’s like every other Yahoo! office except the food — built essentially to corporate spec. Meet with Anita, Raghu, and Rajeev: go over PR angles and they brief me on the media interviews. These guys and gal are on top of things. Meet with Mani and her team: great group. Skip intern pizza talks because I can’t eat cheese, going for the cafeteria instead. Mistake. Order a veggie grill thinking that since it’s grilled, it’s cooked enough. I only take a few bites of this before thinking it’s too risky. I eat some bread and Indian mixtures. Not sure what the culprit is but something doesn’t sit well in my stomach. Give prediction markets portion of my talk to a few interested people in labs. Very sharp group. Meet with Dinesh and Sachin, their intern, and one other. Interesting work. Meet with Chid and Preeti on Webscope. Back to hotel. Call Lauren. Good to hear her voice. Ashley wants to say hi. She’s so adorable. She finds it hilarious that I am about to have dinner while she is eating breakfast. I can hear her laughing uncontrollably at the thought. Sarah says hi too and even ends our conversation without prompting with a “bye, love you”. I go down to the restaurant for dinner. Have a chicken Indian dish with paratha (is it lachha paratha?) bread. Spicy (sweat inducing) yet so delicious. The bread is fantastic — round white with flaky layers. Back to room. TV. CNN. CNBC. ESPN. Hard to sleep. There is an incredible thunderstorm with torrents of rain. I open my balcony door briefly to catch its power. I find out later that monsoon season is just beginning. I also find out that it rained so hard and so long that the roads flooded to the point of becoming impassible. In fact, Anita, the Bangalore PR lead, had a near-disastrous experience in the rapidly flooding streets on her way home and had to turn back and check into a hotel before going home briefly in the morning and then back to Yahoo! for our am meeting. Finally get to sleep.

Day 2: My talk!

Hard to wake up at 8:30am too. Talk’s today! Nerves begin. Media interviews are first! Even worse. Turns out they went fine. Two nice/sharp reporters, especially the second one who really knows her stuff and spoke to us (Rajeev and I) for 1.5 hours. She’s especially interested in the prediction market stuff since that is something new. She may write two articles (for Business World India). Lunch, then a bit of time to rest and freshen up. Stomach is not doing well. Pepto to the rescue. Back down to lobby. They take my picture in the courtyard. Then into the ballroom. Miked. Soundchecked. They accept a final last minute change to my slides: hooray! Room starts filling. 100 people. 200. 300. Now 500. It’s time to start! Rajeev gives a very nice intro. I walk up the stairs onto the stage. I’m miked, in lights, speaking in front of 500 people expecting a Big Thinker. Here I go! “Four score and seven years…” Ha ha. Actually: “Thanks Rajeev, and thanks everyone for your time and attention. I am happy and honored to be here. I’m going to talk about trends in automation in the economy

David Pennock speaking at Yahoo! Big Thinkers India June 2009Audience at Yahoo! Big Thinkers India June 2009

65 minutes later “Thank you very much.” Applause. I think it went well: one of my better talks. I covered everything, including the prediction market stuff. It turns out, like at Yahoo!, and like the journalists, the audience is more interested in prediction markets than advertising. Lots of questions. Some I follow, some I can’t parse the words, others I hear the words but just don’t understand. I do my best. Several people mention they follow my blog: gratifying. After the official Q&A session ends, there is a line up of folks with questions or comments and business cards. It’s the closest I’ll ever be to a rock star. A handful of people wait patiently around me while I try to get to everyone. Eventually the PR folks rescue me and take me to a “high tea” event with Yahoo! Bangalore execs and some recruiting targets. Relief and euphoria kick in. It’s over. I talk with a number of people. I make my exit. Private dining. Call home. Lauren has explained to Ashley that I am on the other side of the world, so when she has the sun, I have the moon. So I can hear Ashley asking in the background, “does Daddy have the moon?” I do. She can’t stop laughing. A repeat of game 6 of the Stanley Cup is on Ten Sports India. I watch it, getting psyched for Game 7. I check online for Ten Sports schedule. Game 7 will be on at 5:30am! I can’t miss that! Set my alarm. Try to sleep. Can’t sleep. Try to sleep. Can’t sleep. Try with TV on. Can’t sleep. Try with TV off. Can’t sleep. Finally fall asleep

Day 3a: Penguins win the Stanley Cup!

Really hard to wake up at 5:30am. Actually maybe not quite as hard since it’s 8pm in my head. Game on! Nerves are racked up. Can’t sit down: bad luck. Pacing. No score first period. Tons of commercials, all for Ten Sports programming: wrestling, cricket, tennis. Every commercial repeats three times. Is period two coming? Yes, it’s back on! Pens score first! Fist pumping and muted cheering. Can they really do this? No sitting rule in full effect. Pacing. Pens score again! Talbot second goal. Wow, is this real? Can it be? Don’t think about it yet. Don’t celebrate to soon. Plenty of time left. Period two end at 2-0. Unbelievable. All the same commercials come back, three times each. Period three begins. Stand up. Pace. Clock ticks. Pens are playing too defensive: not taking shots, just throwing the puck out of their zone. This isn’t good. Detroit is getting tons of chances. Fleury is awesome. Five minutes left. I let myself think about winning the cup. Mistake! Detroit scores! It’s 2-1! Nerves are ratcheted up beyond ratcheting. I think about it all slipping away. How awful that would feel. If Detroit ties it up, imagine the let down, the blown opportunity. Clock ticks. More chances. More saves. More defense. It’s working! Detroit pulls their goalie. Pressure. Final seconds. Faceoff in our zone. Detroit wins control. Shot. Rebound. Right to a Red Wing — Nick Lidstrom — in perfect position. He shoots. Fleury swings around. He saves it! It’s over! Pens win the Cup! Super fist pumping, jumping around, dancing, muted cheering. They did it! How amazing it feels after last year’s loss to the same team. After falling behind 2-0 and 3-2 in the series. They came back! A delicious payback with the same but opposite script as last year: a two goal lead cut in half in the waning minutes, a flurry of attempts at the end including a few-inch miss of the tying goal in the last seconds. These guys are young and have the potential to rule hockey for several years if they’re lucky. Mario Lemieux is on the ice. How sweet. Twice as player, now as owner, the one who saved hockey in Pittsburgh. What a year for Pittsburgh sports! Two nail biter games, two comebacks, two championships. City of Champions again. Too bad the Pirates have no shot to join them in a trifecta. Back to sleep.

Day 3b: Sightseeing

Phone rings at 11am — my driver is here. Off to do some whirlwind sightseeing. Everyone here who finds out I have a day off recommends I leave Bangalore — Bangalore is just not that nice, nothing really to see, they say. They all recommend Mysore, 3.5 hours away, but that is too far for my comfort level given that my flight is late tonight and it’s supposed to thunderstorm. We start with some souvenir shopping on “MG Road”. My driver takes me to a store and waits in the car outside. I walk in an instantly there are people greeting me and showing me things. One aggressive man takes over and remains my “tour guide” through the whole store. The fact that I reward his aggressiveness by following along and eventually buying stuff will only bolster him to do more of the same in the future. Annoying but clearly it works. I do negotiate him down, but I leave still feeling I didn’t bargain hard enough and with a bit of distaste in my mouth that I fueled and validated the pushy tactics. Next we drive past parliament and the courthouse. Impressive, large, old buildings. But I can just gaze and take photos from the car — can’t go inside. Next we drive past Cubbon Park — tree lined paths and flower gardens in center city. Next is ISKCON temple. But it’s closed. So one more round of shopping at a place called Cottage Industries. I’m wary given the last experience, but go anyway. This one is better. Again one person escorts me around but I feel less pressure. Plus I’m more prepared to say no and negotiate harder. I leave with what seems like a fair amount of value in goods. I recommend Cottage Industries to future visitors: more professional, more familiar (items have price tags), lower pressure, greater variety, and higher quality than at least the first shop I visited. Now we’ve killed enough time and the ISKCON temple is open. It’s a giant Hare Krishna temple. The parking lot is full. I tell the driver it’s ok — we don’t need to go. He says “you go, you go”. “Ok” I say. We drive around again to the same full parking lot. The attendant waves at us to leave, blowing a whistle. My driver is talking to him. They are talking quite heatedly. The attendant in his official looking uniform is waving us on vigorously. Although I can’t understand the words, he is clearly telling us the lot is full and we must leave immediately — we are holding up traffic. My driver is getting more insistent. They are yelling back and forth. I have no idea what he says but it works. The guard let’s us in. Meanwhile another car sees our success and tries to argue his way in too but to no avail. I ask my driver what he said: he simply replies “don’t talk”. Indeed once we’re in, there is an empty spot. We put all my bags in my suitcase in the trunk and cover my backpack. We take off our shoes and my driver leads me to the temple. He knows the back entrance and is guiding me to cut in front of lines everywhere. We walk past the main attraction: the altar with some people on the floor worshiping. Then the line weaves past a gift shop of course: I buy a crazy looking book (Easy Journey to Other Planets). We need to kill some time. We go to the gardens again to walk around. We walk into the public library. Most books are in English. Most seem old and worn. The attendant says the library is 110 years old. We start walking through the garden but I am paranoid about mosquitoes/malaria so we turn around early to return to the car. We go to UB City where I meet Rajeev. It’s a thoroughly modern office tower half owned by Kingfisher of Kingfisher Airlines. The building is full of high-end shopping like almost any upscale western mall with all the same brands. Here is the Apple Store. Here is Louis Vuitton. We have dinner at an Italian restaurant that could be anywhere in the western world, owned by an Italian expat. The only seating is outside and I remain worried about mosquitoes but don’t see any. The food is good and the conversation is good.

This place is the closest I’ve seen of the future of Bangalore. In the center of town, a gorgeous building filled with gleaming shops and tantalizing restaurants and bars, with apartments and condos within walking distance, and a palm-tree-lined street leading to the central town circle and the park. As Rajeev says, though, whereas New York has hundreds of similar scenes, Bangalore has one. For now.

Thoughts on Bangalore

Bangalore is a city of jarring contradictions, a hard-to-fathom mix of modernity and poverty. Signs with professional logos and familiar brands are set askew on dilapidated shacks and garages lining the road. While many live on dollars and day and others beg, the majority are smartly dressed (men invariably in button-down shirts), have mobile phones, and are intelligent and friendly. There are gleaming office towers indistinguishable from their western counterparts, yet a strong rain can flood the roads to the point of become impassible for hours and day-long blackouts aren’t uncommon. Many billboards are in English, sporting familiar brands and messages. Others, like sexy stars promoting a Bollywood film, are entirely familiar, English or not. Others are impenetrable. Still another advertises a phone number to learn why Obama quoted the Koran.

BMWs and Toyotas join bikes, motorcycles, pedestrians, aging trucks and buses, and colorful open-air motorized rickshaws in a sea of disorganized line-ignoring sign-ignoring traffic. People drive here the way New Yorkers walk sidewalks: weaving past one another in a noisy self-organized tangle that somehow — mostly — works. You can eat outside in a restaurant bar next to upscale shops, a fountain, and smiling yuppies, yet worry that a malaria-infected mosquito lurks nearby or that a washed vegetable will turn a western-coddled stomach deathly ill. When two people ride a motorcycle, as is common, only the driver wears a helmet — the passenger clinging on behind does not: new and old rules on display atop a single vehicle. And the traffic. Oh, the traffic. Roads are clogged nearly every hour of every day. My Saturday of sightseeing was as bad or worse than weekday rush hour. The extent of congestion itself illustrates Bangalore’s two faces: so many people with youth (India is one of the youngest countries in the world), energy, purpose, and the means and intelligence to accomplish it overtaxing a primitive infrastructure. Buildings are going up according to western specs, but under old-time rules where corruption reins and bribery is an accepted fact of life by even the western-educated aspirational class (about 20% and growing, according to Rajeev).

Thoughts on Yahoo! Labs Bangalore

The folks I met are impressive. Rajeev has done a great job hiring talented, driven folks. Mani‘s group of research engineers is fantastic. One is headed to Berkeley for grad school and asks great questions about CentMail. Another proposes an attack on Pictcha. Another (Rahul Agrawal) has read up deeply on prediction markets, including Hanson’s LMSR.

Thoughts on the Yahoo! Big Thinkers India program

The whole event was organized to precision. Anita, the PR lead, was incredible. I especially appreciated the extra “above and beyond” touches like having someone pick up Yahoo! India schwag for my family and send it to my hotel after I forgot: so nice. Raghu, who arranged the media interviews, is supremely organized and on top of his game. The fact that the event draws such a large crowd shows that there is great thirst for events like this in Bangalore. I’m not sure whose idea it is, but it’s a brilliant one: great marketing and great for recruiting.

Thank you Bangalore

In sum, thanks to the people of Bangalore for a fascinating and rewarding trip. Thanks to Rahul at the travel desk whose instant replies about the driver arrangements calmed my nerves on the stressful day of my departure. Thanks to the Yahoo! folks who arranged and organized my talk, and the Yahoo! Labs members for seeding an exceptional science organization. Thanks to my driver who got me everywhere — including into full parking lots, back entrances, and fronts of lines — with efficiency, safety, and a smile (when I tipped him, I tried to think wwsd and wwdd: what would Sharad or Dan do?). Thanks to those who attending my talk and whom I met afterward: it’s gratifying and invigorating to see your level of interest and enthusiasm (and your numbers). And thanks Bangalore chefs for keeping any stomach upset relatively mild and brief.

At the airport on the way out, the flight is overbooked and they are offering close to US$1000 plus hotel to leave tomorrow. Not a chance. It’s been fun and an adventure but my nerves are on high and I miss my family: it’s time to make the 20+ hour journey home.

Challenge: Derive the Kelly criteria for play money

The Kelly criteria is a money management strategy for gamblers and investors. The strategy says that, when faced with a positive-expectation bet, you should invest a fraction of your budget that is proportional to your expected profit. The more your expect to gain, the more you should risk, but you never risk your entire budget.

The Kelly strategy is optimal in several senses: (1) it minimizes your “doubling time”, or the time it takes to go from having X dollars to having 2X dollars; (2) it minimizes the time it takes to achieve any given level of wealth; (3) it maximizes your long-run wealth.

(It turns out that the Kelly strategy is equivalent to maximizing a logarithmic utility function.)

A key reason the Kelly strategy is optimal is that it is very careful to never take you completely bankrupt: you spend only a fraction of your money, always reserving a bit for tomorrow, however small. This is sound advice when dealing with real money. (Aside: this all assumes you have a strict budget cap, which is not entirely realistic: you can almost always borrow at least some amount, even in today’s economy.)

But what about maximizing your virtual “wealth” inside a play-money game like NewsFutures, InklingMarkets, HubDub, or MediaPredict? The problem is not quite the same, precisely because you cannot really go bankrupt. Almost every game offers an option to “recharge” your account if you go bust. Even if the option is not explicit, you can always just abandon your account and start a new one with a fresh initial bankroll they typically give to new players.

So what is the Kelly criteria for play money? What is the optimal strategy that minimizes your doubling time when you’re always allowed to recharge back to a fixed starting value any time you go bankrupt? The answer is not obvious to me, so I’m crowdsourcing the problem: can readers derive the right rule?

My only conjecture is that it might become optimal to go “all in” on every single bet. But I’m not sure. [Update: I’ve convinced myself this is not optimal. Imagine two sequential bets, the first with minuscule expected profit and the second with huge expected profit: surely you should not go “all in” on the first.]

Note that finding the optimal solution may not just help you win more bragging rights in online games. There is a fascinating sports betting site called CentSports that gives everyone ten real cents to start with. If you can turn that ten cents into twenty dollars, they’ll cut you a check. Moreover, if you ever go to zero, they’ll restore you right back to ten cents. In other words, the system works just like play-money games except the potential for profit is real. So another way to phrase the challenge question is: what strategy in CentSports minimizes the time it takes you to go from ten cents to twenty dollars?

Wall Street's version of a combinatorial market

I was poking around TD AMERITRADE and came across this description of conditional orders (login required, or look here), or sequences of orders that are synchronized in various ways:

What is a conditional order and how do I place one?

Conditional orders let you combine two or three individual orders that will, if filled, either cancel or trigger additional orders. Conditional orders are available for both stocks and single-leg option orders (in option-approved accounts).

The following types of conditional orders are available:

  • OCA (one cancels another) – submit two orders simultaneously; if one order is filled, the other is canceled.
  • OTA (one triggers another) – submit an order and if that order is filled, submit another order.
  • OTT (one triggers two) – submit an order and if that order is filled, submit two additional orders.
  • OT/OCA (one triggers an OCA order) – submit an order; if that order is filled, submit two orders simultaneously; if one of these orders is filled, cancel the other.
  • OT/OTA (one triggers an OTA order) – submit an order; if that order is filled, submit another order. If that order is filled, submit a third order.

At first glance these resemble combinatorial bids that allow traders to buy several things at once, but they’re not. They’re more like bidding agent programs that describe exactly what to do when under various conditions: more complex, but not fundamentally different, than limit orders and stop-loss orders. They can be executed without any cooperation from the exchange.

This brings to light a key distinction: some forms of expressiveness can be achieved by layering increasingly complicated bidding agents on top of an existing exchange. Other types of expressiveness, for example true combinatorial bids, require new optimization routines put directly into the exchange.

The distinction arises in advertising as well. In a sponsored search auction, advertisers can bid lower during the day when people tend to browse and higher in the evening when people tend to buy, and they can even write a program to do it for them automatically. However an advertiser cannot execute a “guaranteed delivery” contract in sponsored search without changing the underlying auction mechanism.

Why should we care about the latter type of expressiveness that requires “smarter” exchange mechanisms? One word: efficiency. Economic efficiency, that is. With greater expressiveness, resources can be shuffled to align more precisely with who wants them the most. Advertising opportunities (a particular user’s attention on a particular page) can go to advertisers who value them most. Financial transactions that otherwise might go unmet can be consummated. Insurance buyers can get better coverage. And gamblers can have more fun.

Even the stock market doesn't know how to report prices

The debate over how to report prediction market prices may seem to arise only because so many of the markets have low liquidity. If prediction markets were more liquid, the logic goes, then it wouldn’t matter if observers reported the last trade price, the average of the last several prices, or the bid-ask spread: they’d all be roughly the same. Indeed, in the extreme case of an “infinite liquidity” automated market maker, they are all the same.

Lance encountered the problem when a few rogue trades caused the colors on our electoral markets map to swing in what would seem to be irrational ways, briefly painting California red for McCain, for example.

However yesterday proved that even one of the most traded stocks on one of the largest volume financial exchanges in the world can suffer from bizarre trading oddities that make reporting meaningful prices an exercise in ad hockery.

It seems that Google’s stock gyrated wildly near the close of trading in entirely inexplicable ways that seem impossible to rationalize, and all this despite enormous volume traded. From SeekingAlpha:

[Here are] the official [NASDAQ] datapoints: share volume of 12 million shares (that’s about $5 billion), more than double the normal amount; an intraday high of $489, and — most improbable of all — an intraday low of just 1 cent per share.

What I found most incredible is that NASDAQ actually rewrote history in response:

Sep 30, 2008 17:01:02 ET Pursuant to Rule 11890(b) NASDAQ, on its own motion, has determined to cancel all trades in security Google Inc Cl – A “GOOG” at or above $425.29 and at or below $400.52 that were executed in NASDAQ between 15:57:00 and 16:02:00 ET. In addition, NASDAQ will be adjusting the NASDAQ Official Closing Cross (NOCP) and all trades executed in the cross to $400.52. This decision cannot be appealed. MarketWatch has coordinated this decision to break trades with other UTP Exchanges. NASDAQ will be canceling trades on the participant’s behalf.

I had no idea that stock exchanges canceled trades “just because”. Barring system error, this seems just plain wrong — certainly worthy of serious outrage from traders. If someone agrees to trade at a wildly irrational price that’s their own problem and they should have to live with it.

Apparently it’s not only possible, but common. On the same day NASDAQ canceled trades in ROH deemed out of bounds:

Sep 30, 2008 17:14:37 ET Pursuant to Rule 11890(b) NASDAQ, on its own motion, has determined to cancel all trades in security Rohm and Haas Company (ROH) at or above $73.20 and at or below $68.93 that were executed in NASDAQ between 15:57:00 and 16:02:00 ET. This decision cannot be appealed.

Suddenly our hack fix to the electoral markets map* and the various controversial revisions at intrade and betfair [1, 2] don’t seem quite so crazarbitrary in comparison.

*We now report the last trade price only if it falls between the current bid-ask spread, otherwise we report the bid or ask price, whichever is closer to the last price. After all, if the last price falls outside the bid-ask boundaries, it no longer reflects current market sentiment.

WeatherBill shows the way toward usable combinatorial prediction markets

WeatherBill let’s you construct an enormous variety of insurance contracts related to weather. For example, the screenshot embedded below shows how I might have insured my vacation at the New Jersey shore:

Read this document on Scribd: WeatherBill Example Contract

For $42.62 I could have arranged to be paid $100 per day of rain during my vacation.

(I didn’t actually purchase this mainly because the US government insists that I am a menace to myself and should not be allowed to enter into such a dangerous gamble — more on this later. And as Dan Reeves pointed out to me, it’s probably not rational to do for small sums.)

WeatherBill is an example of the evolution of financial exchanges as they embrace technology.

WeatherBill can be thought of as expressive insurance, a financial category no doubt poised for growth and a wonderful example of how computer science algorithms are finally supplanting the centuries-old exchange logic designed for humans (CombineNet is another great example).

WeatherBill can also be thought of as a combinatorial prediction market with an automated market maker, a viewpoint I’ll expand on now.

On WeatherBill, you piece together contracts by specifying a series of attributes: date range, place, type of weather, threshold temperature or participation level, minimum and maximum number of bad-weather days, etc. The user interface is extremely well done: a straightforward series of adaptive menu choices and text entry fields guide the customer through the selection process.

This flexibility quickly leads to a combinatorial explosion: given the choices on the site I’m sure the number of possible contracts you can construct runs into the millions.

Once you’ve defined when you want to be paid — according to whatever definition of bad weather makes sense for you or your business — you choose how much you want to be paid.

Finally, given all this information, WeatherBill quotes a price for your custom insurance contract, in effect the maximum amount you will lose if bad weather doesn’t materialize. Quotes are instantaneous — essentially WeatherBill is an automated market maker always willing to trade at some price on any of millions of contracts.

Side note: On WeatherBill, you control the magnitude of your bet by choosing how much you want to be paid. In a typical prediction market, you control magnitude by choosing how many shares to trade. In our own prediction market Yoopick, you control magnitude by choosing the maximum amount you are willing to lose. All three approaches are equivalent, and what’s best depends on context. I would argue that the WeatherBill and Yoopick approaches are simpler to understand, requiring less indirection. The WeatherBill approach seems most natural in an insurance context and the Yoopick approach in a gambling context.

How does the WeatherBill market maker determine prices? I don’t know the details, but their FAQ says that prices change “due to a number of factors, including WeatherBill forecast data, weather simulation, and recent Contract sales”. Certainly historical data plays an important role — in fact, with every price quote WeatherBill tells you what you would have been paid in years past. They allow contracts as few as four days into the future, so I imagine they incorporate current weather forecasts. And the FAQ implies that some form of market feedback occurs, raising prices on contract terms that are in high demand.

Interface is important. WeatherBill shows that a very complicated combinatorial market can be presented in a natural and intuitive way. Though greater expressiveness can mean greater complexity and confusion, Tuomas Sandholm is fond of pointing out that, when done right, expressiveness actually simplifies things by allowing users to speak in terms they are familiar with. WeatherBill — and to an extent Yoopick IMHO — are examples of this somewhat counterintuitive principle at work.

There is another quote from WeatherBill’s FAQ that alludes to an even higher degree of combinatorics coming soon:

Currently you can only price contracts based on one weather measurement. We’re working on making it possible to use more than one measurement, and hope to make it available soon.

If so, I can imagine the number of possible insurance contracts quickly growing into the billions or more with prices hinging on interdependencies among weather events.

Finally, back to the US government treating me like a child. It turns out that only a very limited set of people can buy contracts on WeatherBill, mainly businesses and multi-millionaires who aren’t speculators. In fact, the rules of who can play are a convoluted jumble that I believe are based on regulations from the US Commodity Futures Trading Commission.

Luckily, WeatherBill provides a nice “choose your own adventure” style navigation flow to determine whether you are allowed to participate. Most people will quickly find they are not eligible. (I don’t officially endorse the CYOA standard of re-starting over and over again until you pass.)

Even if red tape locks the average consumer out of direct access, clever companies are stepping in to mediate. In a nice intro piece on WeatherBill, Newsweek mentions that Priceline used WeatherBill to back a “Sunshine Guaranteed” promotion offering refunds to customers whose trips were rained out.

Can you think of other end-arounds to bring WeatherBill functionality to the masses? What other forms of expressive insurance would you like to see?