Category Archives: research

advertising, computer science, economics, events, research, science

Upcoming CS-econ events: New York Computer Science and Economics Day and ACM Conference on Electronic Commerce

1. New York Computer Science and Economics Day (NYCE Day)

Monday, November 9, 2009 | 9:00 AM – 5:00 PM
The New York Academy of Sciences, New York, NY, USA

NYCE 2009 is the Second Annual New York Computer Science and Economics Day. The goal of the meeting is to bring together researchers in the larger New York metropolitan area with interests in Computer Science, Economics, Marketing and Business and a common focus in understanding and developing the economics of internet activity. Examples of topics of interest include theoretical, modeling, algorithmic and empirical work on advertising and marketing based on search, user-generated content, or social networks, and other means of monetizing the internet.

The workshop is soliciting rump session speakers until October 12. Rump session speakers will have 5 minutes to describe a problem and result, an experiment/system and results, or an open problem or a big challenge.

Invited Speakers

  • Larry Blume, Cornell University
  • Shahar Dobzinski, Cornell University
  • Michael Kearns, University of Pennsylvania
  • Jennifer Rexford, Princeton University

CFP: New York Computer Science and Economics Day (NYCE Day), Nov 9 2009

2. 11th ACM Conference on Electronic Commerce (EC’10)

June 7-11, 2010
Harvard University, Cambridge, MA, USA

Since 1999 the ACM Special Interest Group on Electronic Commerce (SIGecom) has sponsored the leading scientific conference on advances in theory, systems, and applications for electronic commerce. The Eleventh ACM Conference on Electronic Commerce (EC’10) will feature invited speakers, paper presentations, workshops, and tutorials covering all areas of electronic commerce. The natural focus of the conference is on computer science issues, but the conference is interdisciplinary in nature. The conference is soliciting full papers and workshop and tutorial proposals on all aspects of electronic commerce.

fun, gambling, goodbet, insurance, prediction markets, probability, science, search

Psst: WeatherBill doesn’t know New Jersey is the new Florida: Place your bets now

11 Comments

Quantifying New York’s 2009 June gloom using WeatherBill and Wolfram|Alpha

In the northeastern United States, scars are slowly healing from a miserably rainy June — torturous, according to the New York Times. Status updates bemoaned “where’s the sun?”, “worst storm ever!”, “worst June ever!”. Torrential downpours came and went with Florida-like speed, turning gloom into doom: “here comes global warming”.

But how extreme was the month, really? Was our widespread misery justified quantitatively, or were we caught in our own self-indulgent Chris Harrisonism, “the most dramatic rose ceremony EVER!”.

This graphic shows that, as of June 20th, New York City was on track for near-record rainfall in inches. But that graphic, while pretty, is pretty static, and most people I heard complained about the number of days, not the volume of rain.

I wondered if I could use online tools to determine whether the number of rainy days in June was truly historic. My first thought was to try Wolfram|Alpha, a great excuse to play with the new math engine.

Wolfram|Alpha queries for “rain New Jersey June 200Y” are detailed and fascinating, showing temps, rain, cloud cover, humidity, and more, complete with graphs (hint: click “More”). But they don’t seem to directly answer how many days it rained at least some amount. The answer is displayed graphically but not numerically (the percentage and days of rain listed appears to be hours of rain divided by 24). Also, I didn’t see how to query multiple years at a time. So, in order to test whether 2009 was a record year, I would have to submit a separate query for each year (or bypass the web interface and use Mathematica directly). Still, Wolfram|Alpha does confirm that it rained 3.8 times as many hours in 2009 as 2008, already one of the wetter months on record.

WeatherBill, an endlessly configurable weather insurance service, more directly provided what I was looking for on one page. I asked for a price quote for a contract paying me $100 for every day it rains at least 0.1 inches in Newark, NJ during June 2010. It instantly spat back a price: $694.17.



WeatherBill rainy day contract for June 2010 in Newark, NJ

It also reported how much the contract would have paid — the number of rainy days times $100 — every year from 1979 to 2008, on average $620 for 6.2 days. It said I could “expect” (meaning one standard deviation, or 68% confidence interval) between 3.9 and 8.5 days of rain in a typical year. (The difference between the average and the price is further confirmation that WeatherBill charges a 10% premium.)

Below is a plot of June rainy days in Newark, NJ from 1979 to 2009. (WeatherBill doesn’t yet report June 2009 data so I entered 12 as a conservative estimate based on info from Weather Underground.)


Number of rainy days in Newark, NJ from 1979-2009

Indeed, our gloominess was justified: it rained in Newark more days in June 2009 than any other June dating back to 1979.

Intriguingly, our doominess may have been justified too. You don’t have to be a chartist to see an upward trend in rainy days over the past decade.

WeatherBill seems to assume as a baseline that past years are independent unbiased estimates of future years — usually not a bad assumption when it comes to weather. Still, if you believe the trend of increasing rain is real, either due to global warming or something else, WeatherBill offers a temptingly good bet. At $694.17, the contract (paying $100 per rainy day) would have earned a profit in 7 of the last 7 years. The chance of that streak being a coincidence is less than 1%.

If anyone places this bet, let me know. I would love to, but as of now I’m roughly $10 million in net worth short of qualifying as a WeatherBill trader.

commentary, research, science, woblomo

The long tail of science: Good, bad, or ugly?

5 Comments

(First in a series of “random thoughts on science”)

A mind boggling number of academic research conferences and workshops take place every year. Each fills a thick proceedings with publications, some containing hundreds of papers. High-profile conferences can attract five times that many submissions, often of low average quality. Smaller venues can seem absurdly specialized (unless it happens to be your specialty). Every year, new venues emerge. Once established, rarely do they “retire” (there is still an ACM Special Interest Group on the Ada programming language, in addition to a SIG on programming languages). It’s impossible for all or even most of the papers published in a given year to be impactful. Most of them, including plenty of my own, will never be cited or even read by more than the authors and reviewers.

No one can deny that incredible breakthroughs emerge from the scientific process — from Einstein to Shannon to Turing to von Neumann — but scientific output seems to have a (very) long tail.

Is this a good thing, a bad thing, or just a thing?

Is the tail…

Good?
Is the tail actually crucial to the scientific process? Are some breakthroughs the result of ideas that percolate through long chains — person to person, paper to paper — from the bottom up? Is science less dwarfs standing on the shoulders of giants than giants standing on the shoulders of dwarfs? I published a fairly straightforward paper that applies results in social choice theory to collaborative filtering. Then a smarter scientist wrote a better paper on a more widely applicable subject, apparently partially inspired by our approach. Could such virtuous chains actually lead, eventually, to the truly revolutionary discoveries? Is the tail wagging the dog?
Bad?
Are the papers in the tail a waste of time, energy, and taxpayer dollars? Do they have virtually no impact, at least compared to their cost? Should we try hard to find objective measures that identify good science and good scientists and target our funding to them, starving out the rest?
Ugly?
Is the tail simply a messy but necessary byproduct (I can’t resist: a “messessity”) of the scientific process? Under this scenario, breakthroughs are fundamentally rare and unpredictable hits among an enormous sea of misses. To get more and better breakthroughs, we need more people trying and mostly failing — more monkeys at typewriters trying to bang out Shakespeare. Every social system, indeed almost every natural system, has a long tail. Maybe it’s simply unavoidable, even if it isn’t pretty. Was the dog simply born with its (long and scraggly) tail attached?
prediction markets, research, woblomo

Should there be a Prediction Market Institute?

4 Comments

There’s a Prediction Market Industry Association (sort of).

Is it time for a Prediction Market Institute dedicated to scientific advancement and engineering innovation in prediction markets?

On the face of it, the concept is ludicrous: there is no “Support Vector Machine Institute”, for example. But a bunch of tech companies have PM research efforts of some sort, including Google, HP, Microsoft, and Yahoo!. Folks at these companies have come together to lobby, to speak, and to exchange academic research results. Would YaHPooglesoft fund such an institute? If not, who? Chris Masse, who adds “PM journalism” to the list of institute goals, is on the case.

publication, technology, woblomo, writing

What do you want to be when you grow up?

The first semi-serious answer I remember giving to the title question was “either a writer or a magician” (circa third grade, more about age 8-9).

Given this quote:

Any sufficiently advanced technology is indistinguishable from magic. –Arthur C. Clarke

and the fact that likely the most tangible record of my career are my publications, one might say that I did indeed become both a writer and a magician.

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

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