Category Archives: economics

advertising, challenges, economics, new media, woblomo, yahoo

The social advertising puzzle

7 Comments

There’s no doubt that social ties have tremendous value: people find love and work largely through the people they know and the people the people they know know.

And there’s no doubt that digital representations of social ties add value. Facebook does improve people’s lives.1

The puzzle, and one of the key challenges facing companies like Facebook, Google, and Yahoo!., is how social media can make money. So far the evidence is most users won’t pay directly, which leaves ideas like virtual goods, community marketplaces, app stores, and, of course, advertising. Unfortunately, although we know great ways to advertise to people searching, and decent ways to advertise to people viewing content, it’s less clear how to advertise to people communicating.

P&G’s Ted McConnell puts it bluntly:

What in heaven’s name made you think you could monetize the real estate in which somebody is breaking up with their girlfriend?

Riffing off of this quote, Wired asks the $15 billion question: Is social advertising an oxymoron?:

So, what if social media and advertising just don’t mix?

SocialMedia.com, a social advertising startup, begs to differ (hat tip to Cong Yu), reacting to the same provocative McConnell quote. Their answer:

Advertisers only pay when users volunteer to say something about the brand to their friends.

Indeed, this sort of paid version of Bem+Wom (“BEtter Mousetrap + Word Of Mouth”) — more on this in the next post — is one of the first things people think of when pondering how to monetize a social network. But can it work well and if so, how?

Three disjoint friends like Rooster Sauce. Who knew?

1For example, I never would have guessed that three completely disjoint friends of mine are all fans of Sriracha Rooster Sauce. Who knew?
advertising, economics, finance, prediction markets, woblomo

Wall Street's version of a combinatorial market

3 Comments

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.

advertising, artificial intelligence, economics, research, search, technology, yahoo

Yahoo! Key Scientific Challenges student seed program

2 Comments

Yahoo! Research just published its list of key scientific challenges facing the Internet industry.

It’s a great resource for students to learn about the area and find meaty research problems. There’s also a chance for graduate students to earn $5000 in seed funding, work with Yahoo! Research scientists and data, and attend a summit of like-minded students and scientists.

The challenges cover search, machine learning, data management, information extraction, economics, social science, statistics, multimedia, and computational advertising.

Here’s the list of challenges from the algorithmic economics group, my group. We hope it provides a clear picture of the goals of our group and the areas where progress is most needed.

We look forward to supporting students who love a challenge and would like to join us in building the next-generation Internet.


Yahoo! Key Scientific Challenges Program 2009

economics, incentives, oddhead blog, spam

Intelligent blog spam

23 Comments

As I alluded to previously, I seem to be getting “intelligent spam” on my blog: comments that pass the re-captcha test and seem on-topic, yet upon further inspection clearly constitute link spam: either the author URI or a link in the comment body is spam.

Here is one of the most clear cases, received on January 9 as a comment to my post on the CFTC’s call for proposals to regulate prediction markets:

Date: Fri, 9 Jan 2009 01:28:01 -0800
From: Matt.Herdy
New comment on your post #71 “A historic MayDay: The US
government’s call for help on regulating prediction markets”
Author : Matt.Herdy
Comment:
Thanks for that post. I’ll put a note in the post.

1. It’s nothing new. The CFTC will just formalize the current
status quo.
2. We are prisoner of the CFTC regulations and the US Congress’
distaste of sports “gambling”. As for the profitability of prediction
exchanges in that strict environment, I don’t see how you can deny that
HedgeStreet went bankrupt even though it was well funded. Isn’t that a
hard fact?
3. You’re right, but all “pragmatists” should follow a business
plan and make profits. See point #2. Pragmatists won’t make miracles.

<a href=”http://www.stretch-marks-help.com/”>Removing stretch marks</a>

At first blush, the comments seems to come from a knowledgeable person: they refer to HedgeStreet, an extremely relevant yet mostly unknown company that’s not mentioned anywhere else in the post or other comments.

It turns out the comments seem intelligent because they are. In fact, they’re copied word for word from Chris Masse’s comments on his own blog.

Chris Masse’s page has a link to my page, so it could have been discovered with a “link:” query to a search engine.

Though now I understand what this spammer did, I remain puzzled exactly how they did it and especially why.

  1. Are these comments being inserted by people, perhaps hired on Mechanical Turk or other underground equivalent? Or are they coming from robots who have either broken re-captcha or the security of my blog? (John suspects a security breach.)
  2. Is it really worth it economically? All links in blog comments are NOFOLLOW links anyway, and disregarded by search engines for ranking purposes, so what is the point? Are they looking for actual humans to click these links?

In any case, it seems an intriguing development in the spam arms race. Are other bloggers getting “intelligent spam”? Does anyone know how it’s done and why?

Update 2010/07: Oh, the irony. I got a number of intelligent seeming comments on this post about SEO, nofollow, economics of spam, etc. that were… promoting spammy links. I left them for humor value though disabled the links.

explainer, gambling, prediction markets, research

What is (and what good is) a combinatorial prediction market?

6 Comments

What exactly is a combinatorial prediction market?

2010 Update: Several of us at Yahoo! Labs, along with academic researchers, have theorized and written about combinatorial prediction markets for several years, as you’ll see below. But now we’ve gone beyond talking about them and actually built one. So the best way to answer the question is to see the market we built and play with it. It’s called Predictalot. The first version was based on the NCAA Men’s College Basketball tournament known as March Madness.

Combinatorial Madness

March Madness is the anything-can-happen-and-often-does tournament among the top 64 NCAA Men’s College Basketball teams. The “madness” of the games is rivaled only by the madness of fans competing to pick the winners. In Las Vegas, you can bet on many things, from individual games to the overall champion to more exotic “propositions” like which conference of teams will do best. Still, each gambling venue defines in advance exactly what you are allowed to bet on, offering an explicit list of usually no more than a few thousand choices.

A combinatorial market maker fulfills an almost magical promise: propose any obscure proposition, click “accept”, and your bet is placed: no doubt and no waiting.

In contrast, a combinatorial market could allow you to make up nearly any proposition you want on the fly, for example, “Duke will advance further than UNC” or “At least one of the top four seeds will lose in the first round”, or “ACC conference teams will win every game they play against lower-seeded SEC conference teams”. How many such propositions are there? Let’s count. There are 63 games (ignore the new play-in game), each of which could go to either to the favorite or the underdog, so there are 263 or over 9,220,000,000,000,000,000 (9.22 quintillion) outcomes, or ways the tournament in its entirety could unfold. Propositions are collections or sets of outcomes: for example “Duke will advance further than UNC” is a statement that’s true in something less than half of the 9.2 quintillion outcomes. Technically, then, there are 2263 possible propositions, a number that dwarfs the number of atoms in the universe. Clearly we could never write down a list that long, even inside a computer. However that doesn’t necessarily mean we can’t operate such a market if we are a little clever about how we implement it, as we’ll see below.

So here is my informal definition: a combinatorial market is one where users can construct their own bets by mixing and matching options in myriad ways, sort of like ordering a Wendy’s hamburger. (Or highly customized insurance.)

The Details

Now I’ll try for a more precise definition.

Just to set the vocabulary straight, outcomes are all possible things that might happen: for example all five candidates in an election, all 30 teams in an NBA Championship market, all 3,628,800 (or 10!) finish orderings in a ten-horse race, or all 9.2 quintillion March Madness tournament results. Among the outcomes, in the end one and only one of them will actually occur; traders try to predict which.

Bids express what outcome(s) traders think will happen. Bids also contain the risk-reward ratio the trader is willing to accept: the amount she wins if correct and the amount she is willing to lose if incorrect.

There are two reasons why we might call a market “combinatorial”: either the bids are combinatorial or the outcomes are combinatorial. The latter poses a much harder computational problem. I’ll start with the former.

  1. Combinatorial bids. A combinatorial bid or bundle bid is a concise expression representing a collection or set of outcomes, for example “a Western Conference team will win the NBA Championship”, encompassing 15 possible outcomes, or “horse A will finish ahead of horse B” in a ten-horse race, encoding 1,814,400, or half, of the possible outcomes. Yoopick, our experimental sports prediction market on Facebook, features a type of combinatorial bidding called interval bidding. Traders select the range they think the final score difference will fall into, for example “Pittsburgh will win by between 2 and 11 points”. An interval bet is actually a collection of bets on every outcome between the left and right endpoints of the range.

    For comparison, a non-combinatorial bid is a bet on a single outcome, for example “candidate O will win the election”. The vast majority of fielded prediction markets handle only non-combinatorial bids.

    What are examples of combinatorial bids besides Yoopick? Abe Othman built an interval betting interface similar to Yoopick (he came up with it on his own, proving that great minds think alike) to predict when the new CMU computer science building will finish construction. Additional examples include Bossaerts et al.’s concept of combined value trading and the parimutuel call market mechanism [Baron & Lange, Lange & Economides, Peters et al.]. 2010 Update: Predictalot is our latest example of a market featuring both combinatorial bids and outcomes.

  2. Combinatorial outcomes. The March Madness scenario is an example of combinatorial outcomes. The number of outcomes (e.g., 9.2 quintillion) may be so huge that we could never hope to track every outcome explicitly inside a computer. Instead, outcomes themselves are defined implicitly according to some counting process that involves enumerating every possible combination of base objects. For example, the outcome space could be all n! possible finish orderings of an n-horse race. Or all 2n combinations of n binary events. In both cases, the number of outcomes grows exponentially in the number of base objects n, quickly becoming unimaginably large as n grows.

    A market with combinatorial outcomes is almost nonsensical without allowing combinatorial bids as well, since individual outcomes are like microbes on a needle on a cruise ship of hay in a universe-sized sea. No one wants to bet on these minuscule possibilities one at a time. Instead, traders bet on high-level properties of outcomes, like “Duke will advance further than UNC”, that encode sets of outcomes. Here are some example forms of combinatorics and corresponding bidding languages that seem natural:

    • Boolean betting. Outcomes are combinations of binary events. Bids are phrased in Boolean logic. So if base objects are “Democrat will win in Alabama”, “Democrat will win in Alaska”, etc. for all fifty US states, and outcomes are all 250 possible ways the election might swing across all 50 states, then bids may be of the form “Democrat will win in Ohio and Florida, but not Virginia”, or “Democrat will win Nevada if they win California”, etc. For further reading, see Hanson’s paper on combinatorial market makers and our papers on the computational complexity of Boolean betting auctioneers and market makers.
    • Tournament betting. This is the March Madness example and a special case of Boolean betting. See our paper on tournament betting market makers.
    • Permutation betting. Outcomes are possible finish orderings in a horse race. Bids are properties of orderings, for example “Horse B will finish ahead of horse D”, or “Horse B will finish between 3rd and 7th place”. See our papers on permutation betting auctioneers and market makers.
    • Taxonomy betting. Base objects are (discretized) numbers arranged in a taxonomy, for example web site page views organized by topic, subtopic, etc. Outcomes are all possible combinations of the numbers. Bets can be placed on the range of any number in the taxonomy, for example page views of a sports web site, page views of the NBA subsection of the web site, etc. Coming soon: a paper on taxonomy betting led by Mingyu Guo at Duke. [Update: here is the paper.]

    We summarize some of these in a short article on Combinatorial betting and a more detailed book chapter on Computational aspects of prediction markets.

    2009 Update: Gregory Goth writes an excellent and accessible summary in the March 2009 Communcations of the ACM, p.13.

Auctioneer versus market maker

So far, I’ve only talked about the form of bids from traders. Next I’ll discuss the actual mechanics of the marketplace, or how bids are processed. How does the market operator decide which bids to accept or reject? At what prices?

I’ll focus on two major possibilities: either the market operator acts as an auctioneer or he acts as an automated market maker.

An auctioneer only matches up willing traders with each other — the auctioneer never takes on any risk of his own. This is how most financial exchanges like the stock market operate, and how intrade and betfair operate. (A call market is a special case where the auctioneer collects many bids over a period of time, then processes them all together in a single batch.)

An automated market maker will quote a price for any bet whatsoever. Even lone traders can place their bet with the market maker as long as they accept the price, greatly enhancing liquidity. The liquidity comes at a cost though: an automated market maker can and often does lose money, though clever pricing algorithms can guarantee that losses won’t mount beyond a fixed amount set in advance. Hanson’s logarithmic market scoring rule market maker is far and away the most popular for prediction markets, and for good reason: it’s simple, has nice modularity properties, and behaves well in practice. We catalog a number of bounded-loss market makers in this paper. The dynamic parimutuel market used in the (now closed) Yahoo! Tech Buzz Game can be thought of as another type of automated market maker.

A market with combinatorial outcomes almost requires a market maker to function smoothly. When traders have such a mind-boggling array of choices, the chances that two or more of their bets will exactly counter each other seems remote. If trades are rarely filled, then traders won’t bother bidding at all, causing a no-chicken-no-egg spiral into failure.

One the other hand, a market maker allows anyone to get a price quote at any time on any bet, no matter how convoluted or specific, even if no other traders had thought about that particular possibility. Thus interacting with a combinatorial market maker can be highly satisfying: propose any obscure proposition, click “accept price”, and your bet is placed: no doubt and no waiting.

I’ll discuss one more technicality. An auctioneer must decide whether bids can be partially filled, giving traders both less risk and less reward than they requested, in the same ratio. This makes sense. If I’m willing to risk $100 to win $200, I’d almost surely risk $50 to win $100 instead. Allowing partial fills greatly simplifies life for the auctioneer too. If bids are divisible, or can be filled in part, the auctioneer can use efficient linear programming algorithms; if bids are indivisible, the auctioneer must use integer programming algorithms that may be intractable. For more on the divisible/indivisible distinction, see Bossaerts et al. and Fortnow et al. Allowing divisible bids seems the logical choice in most scenarios, since the market functions better and most traders won’t mind.

The benefits of combinatorial markets

Why do we need or want combinatorial markets? Simply put, they allow for the collection of more information, the life-blood of every prediction market. Combinatorial outcomes allow traders to assess the correlations among base objects, not just their independent likelihoods, for example the correlation between Democrats winning in Ohio and Pennsylvania. Understanding correlations is key in many applications, including risk assessment: one might argue that the recent financial meltdown is partly attributable to an underestimation of correlation among firms and securities and the chances of cascading failures.

Although financial and betting exchanges, bookmakers, and racetracks are modernizing, turning their operations over to computers and moving online, their core logic for processing bids hasn’t changed much since auctioneers were people. For simplicity, they treat all bets like apples and oranges, processing them independently, even when they are more like hamburgers and cheeseburgers. For example, bets on a horse “to win” and “to finish in the top two” are managed separately at the racetrack, as are options to buy a stock at “strike price 30” and “strike price 20” on the CBOE. In both cases it’s a logical truism that the first is worth less than the second, yet the market pleads ignorance, leaving it to traders to enforce consistent pricing.

In a combinatorial market, a bet on “Duke will win the tournament” automatically increases the odds on “Duke will win in the first round”, as it logically should. Mindless mechanical tasks like this are handled automatically, by algorithms that are far better at it anyway, freeing up traders for the primary task a prediction market asks them to do: provide information. Traders are free to express their information in whatever form they find most natural, and it all flows into the same pool of liquidity.

I discuss the benefits of combinatorial bids further in this post, including one benefit I don’t mention here: smarter accounting, or making sure no more is reserved from a trader’s balance than necessary to cover their worst-case loss.

The disadvantages of combinatorial markets

I would argue that there is virtually no disadvantage to allowing combinatorial bids. They are more flexible and natural for traders, and they eliminate redundancy and thus concentrate liquidity (again I refer the reader to this previous post). Allowing indivisible combinatorial bids can cause computational problems, but as I argue above, divisible bids make more sense anyway.

On the other hand, there can be disadvantages to markets with combinatorial outcomes. First, trader attention and liquidity may be severely fractured, since there are nearly limitless things to bet on.

Second, and perhaps more troublesome, running an auctioneer with combinatorial outcomes is computationally intractable (specifically, NP-hard, or as hard as solving SAT) and running a market maker is even harder (specifically, #P-hard, as hard as counting SAT), meaning that the amount of time needed to run is proportional to the number of outcomes, exponential in the number of objects.

It gets worse. Even if we place strict limits on what types of bets traders can make, the market may still be infeasible to run. For example, even if all bets are pairwise, like “Horse B will finish ahead of horse D”, the auctioneer and market maker problems for permutation betting remain NP-hard and #P-hard, respectively. Likewise, Boolean betting remains hard even if the most complicated bet allowed is joining two events, like “E will happen and F will not” [see Chen et al. and Fortnow et al.].

How to build one

Now for some good news: in some cases, fast algorithms are possible. If all bets are subset bets of the form “Horse A will finish in position 1,2, or 10” or “Horse B,C, or E will finish in position 3”, then permutation betting with an auctioneer is feasible (using a combination of linear programming and maximum matching), even though the corresponding market maker problem is #P-hard. If all bets are of the form “Team B will advance to round k”, tournament betting with a market maker is feasible (using Bayesian network inference). Taxonomy betting with a market maker is feasible (using dynamic programming).

Finally, even better news: fast market maker approximation algorithms are not only possible and practical, they work without limiting what people can bet on, fulfilling the almost magical promise I made at the outset of constructing any bet you can imagine on the fly. Approximation works because people like to bet on things that have a decent chance of happening, say between a 1% and 99% chance. Standard sampling algorithms, including importance sampling and MCMC, are good at approximating prices for such reasonable events. For the extreme (e.g., 1-in-a-billion) events, sampling may fail, so the market maker will have to round off in its own favor to be safe.

Wrapping up, in my mind, the best way to implement a combinatorial-outcome prediction market is as follows:

  • Use a market maker. Without one, traders are unlikely to find each other in the sea of choices. Specifically, use Hanson’s LMSR market maker.
  • Use an approximation algorithm for pricing. Importance sampling seems to work well. MCMC is another possibility. See Appendix A of this paper.
  • The interface is absolutely key, and the aspect I’m least qualified to opine on. I think Predictalot, WeatherBill, Yoopick, and WhenWillWeMove point in the right direction.

2010 Update: Predictalot is our first pass at carrying through on this vision of how to build a combinatorial prediction market. In building it, we learned a great deal already, for example that sampling is much much trickier than I had initially imagined, and that it’s easy to accidentally create arbitrage loopholes if you’re not extremely careful with the math.

I glossed over a number of details. For example, care must be taken for the market maker to always round approximations in its own favor to avoid opening itself up to arbitrage attacks. Another difficulty is how to implement smart accounting to allow traders maximum leverage when they place many interrelated bets. The assumption that traders could lose all their bets is far too conservative — they might have bets that provably cannot simultaneously lose — but may serve as a reasonable starting point in practice.

commentary, economics, fun

Babel: English Lit Syndrome meets Economics 101

4 Comments

My wife and I just finished watching Babel, a movie about people lost in foreign cultures struggling to communicate.

It turns out that when you pop in the DVD and hit play, by default there are no subtitles, despite the fact that the majority of dialog takes place in Moroccan, Japanese, sign language, and Spanish.

I suffered from English Lit Syndrome, thinking how cool it was how the filmmakers made you feel like you were lost along with the characters, recalling the spot-on memoryless feel of Memento.

My wife insisted that there must be something wrong. Perhaps we missed a setting or choice among the menu options for subtitles? As the Japanese storyline reached its close, with lengthy and intricate back and forth dialog between characters whose relationships I hadn’t the least clue about, I realized that maybe, just maybe, she was right.

When the movie ended, I dug back into the menu. Low and behold, there in a “settings” submenu was a choice for subtitles: English, Spanish, or none. Default on “none”.

My artistic elitism crumbled into simple annoyance.

Poking around online, it turns out I’m not the only one duped by the DVD bug or struck by ELS.

Just think of all the time wasted by people watching the movie in incomprehension, investigating the problem, getting irked, and most especially complaining about it online.

A classic Econ 101 lesson in efficiency lost.

But wait! The DVD spurred the disorganized masses to work together to produce a tower of criticism. How clever!

commentary, prediction markets, publication, research, search, yahoo

The "predict flu using search" study you didn't hear about

12 Comments

In October, Philip Polgreen, Yiling Chen, myself, and Forrest Nelson (representing University of Iowa, Harvard, and Yahoo!) published an article in the journal Clinical Infectious Diseases titled “Using Internet Searches for Influenza Surveillance”.

The paper describes how web search engines may be used to monitor and predict flu outbreaks. We studied four years of data from Yahoo! Search together with data on flu outbreaks and flu-related deaths in the United States. All three measures rise and fall as flu season progresses and dissipates, as you might expect. The surprising and promising finding is that web searches rise first, one to three weeks before confirmed flu cases, and five weeks before flu-related deaths. Thus web searches may serve as a valuable advance indicator for health officials to spot the onset of diseases like the flu, complementary to other indicators and forecasts.

On November 11, the New York Times broke a story about Google Flu Trends, along with an unusual announcement of a pending publication in the journal Nature.

I haven’t read the paper, but the article hints at nearly identical results:

Google … dug into its database, extracted five years of data on those queries and mapped it onto the C.D.C.’s reports of influenzalike illness. Google found a strong correlation between its data and the reports from the agency…

Tests of the new Web tool … suggest that it may be able to detect regional outbreaks of the flu a week to 10 days before they are reported by the Centers for Disease Control and Prevention.

To the reporter’s credit, he interviewed Phillip and the article does mention our work in passing, though I can’t say I’m thrilled with the way it was framed:

The premise behind Google Flu Trends … has been validated by an unrelated study indicating that the data collected by Yahoo … can also help with early detection of the flu.

giving (grudging) credit to Yahoo! data rather than Yahoo! people.

The story slashdigged around the blogomediasphere quickly and thoroughly, at one point reaching #1 on the nytimes.com most-emailed list. Articles and comments praise how novel, innovative, and outside-of-the-box the idea is. The editor in chief of Nature praised the “exceptional public health implications of [the Google] paper.”

I’m thrilled to see the attention given to the topic, and the Google team deserves a huge amount of credit, especially for launching a live web site as a companion to their publication, a fantastic service of great social value. That’s an idea we had but did not pursue.

In the business world, being first often means little. However in the world of science, being first means a great deal and can be the determining factor in whether a study gets published. The truth is, although the efforts were independent, ours was published first — and Clinical Infectious Diseases scooped Nature — a decent consolation prize amid the go-google din.

Update 2008/11/24: We spoke with the Google authors and the Nature editors and our paper is cited in the Google paper, which is now published, and given fair treatment in the associated Nature News item. One nice aspect of the Google study is that they identified relevant search terms automatically by regressing all of the 50 million most frequent search queries against the CDC flu data. Congratulations and many thanks to the Google/CDC authors and the Nature editors, and thanks everyone for your comments and encouragement.

advertising, economics, events, research, yahoo

NYCE Day: Thanks and thoughts

10 Comments

NYCE Day 2008 went very well, with over 100 attendees, great talks, and valuable discussion. Many thanks to the four plenary speakers — Costis, Asim, Susan, and Tuomas — and ten rump session speakers who came in from various NYC suburbs like Boston, Pittsburgh, and Palo Alto.

At dinner the night before,1 the organizers agreed that we were nervous because we weren’t at all nervous. Karin and Renee from the New York Academy of Sciences had taken care of almost everything, leaving little for us to fret about. It turned out we were right to not worry and wrong to worry about not worrying: indeed Karin, Renee, and NYAS were absolutely fantastic, orchestrating every detail of the event flawlessly, from technology to catered breaks. The venue itself is gorgeous — a well laid-out space in a modern building in the World Trade Center complex with stunning views2 and a number of nice touches, from an alcove with a computer station to check email to a subtle gradient in the wallpaper that slowly pixilates as your gaze moves from the center toward the side of the room. I came away incredibly impressed with NYAS and delighted to become a member.

Muthu provides an excellent summary of the event, divided into before and after lunch. Read that first and then come back here for my additional thoughts/notes:

  1. Costis gave us mostly bad news. He summarized some of his award winning work with Christos Papadimitriou and Paul Goldberg proving that computing equilibrium behavior in almost any moderately complex game may be beyond the reach of our computers,3 let alone our brains. As a saying goes, “if your laptop can’t find it, then neither can the market” [attribution: Kamal Jain?]. Still, all may not be lost. These results, as is the nature of computational complexity results, say only that some games are extremely hard to solve, not all games or even most games. Since nature is not adversarial (Murphy’s Law aside), it may be the case that among games that arise in the real world that we care about, a number of them can be solved for equilibrium. The problem is defining what “realistic” means in this context: an almost impossibly fuzzy task. Costis did end with some positive results, showing that anonymous games can be solved efficiently. Anonymous games crop up in realistic situations, for example in analyzing traffic, where only the quantity of cars near you matters and not the identity of the drivers inside.

  2. Asim described a sophisticated Bayesian model well suited for social network data that handles non-existant links — meaning the lack of connection between two people, by far the most common situation — much better than previous approaches. The approach is good for digging deeply into a small data set but at least for now has difficulty with moderately large amounts of data. (To get results in a reasonable amount of time, Asim had to down sample his already fairly modest sized corpus.) The talk didn’t help me overcome my bias that Bayesian methods ala UAI often don’t work well at Internet scales without modification.

  3. Susan gave a fantastic and energetic talk. She advocates economic models of online advertising that include more sophisticated users, as opposed to typical models that assume users scan from the top of the page down in a precise sequence. She went further to claim that users may actually choose their search engine based on the quality of the ads. Personally, I’m a bit skeptical about that, though I do agree that there is an indirect effect: search engines with better paying ads can afford to buy more traffic and improve their algorithmic search more. Susan highlighted the enormous shift in mindset required between economic theory and practice when just computing the mean of a data stream can take weeks (though this is changing with tools like Hadoop that can bring such computations down to hours or minutes as Sebastien confirms).

  4. Someone asked Tuomas why his expressive commerce company CombineNet uses first-price auctions instead of VCG pricing. He listed four of what he said were dozens of reasons on top of Rothkopf’s thirteen and Ausubel and Milgrom’s list. In fact he went further to say that as far as he knew no real auction anywhere in the world has ever used true VCG pricing for anything more complicated than selling a single good at a time.

  5. For those not familiar, a rump session is open to anyone to speak briefly on any relevant topic. As it turns out, in part because brevity forces clarity, and in part because editorial filtering overweights mediocrity, the rump session is often the most interesting part of a conference. The “NYCE rump” session was no exception, with topics spanning ad auctions, reputation, Internet routing, and user generated content. Ivy Li proposed a clever scheme whereby eBay sellers are motivated to reward buyers for honest feedback. Sebastien presented work with Sihem and I on an expressive bidding language for online advertising with fast allocation and pricing algorithms, with the goal of moving the industry toward an open standard. Sampath Kannan on leave at NSF had encouraging news on the funding front, laying out his vision for CS theory funding with an explicit call for proposals at the boundary of CS and economics.

  6. I think we did a good job of attracting a diversity of speakers and participants, with talks ranging from computational complexity to Bayesian models of social networks, with academia and industry represented, and with CS, economics, and business backgrounds represented.
1We had dinner at Gobo, a fantastic restaurant Muthu recommended that truly opened my eyes in terms of the tastes and textures possible with a vegetarian menu. Delicious.
2Speaking of views, I had a stunning and fascinating one from my hotel the night before, looking straight down onto ground zero of the World Trade Center complex from a relatively high floor of the Millenium Hilton (apparently intentionally misspelled). I booked the room for $185 on Hotwire, and then found out why. Though the WTC site still looks nearly empty, builders appear to be making up for lost time with round the clock construction. Put it this way: the hotel kindly provided complementary earplugs. All in all though the room and view were well worth the cost in dollars and sounds.
3Specifically, computing Nash equilibrium is PPAD-complete for most games. In terms of complexity classes, PPAD is a superset of P and a subset of NP. Almost surely there is no polynomial time algorithm, though the problem is not quite as hard as the classic NP-complete problems like traveling salesman.
finance, prediction markets

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.