ACM EC Conference and Workshop on Ad Auctions

By Jon Feldman and Vahab Mirrokni, Google Research, NY

This month, the 10th ACM Conference on Electronic Commerce (EC 2009) and the 5th Workshop on Ad Auctions took place at Stanford University. This is one of the major forums for economists and computer scientists to share their ideas about mechanism design and algorithmic game theory. Other than co-authoring several papers in the conference and workshops, Google contributed significantly in presenting tutorials.

Among the four tutorials given at the ACM EC conference, we participated in presenting two of them:

• In a joint tutorial with Google researcher Muthu Muthukrishnan, we explored research problems in sponsored search inspired by taking the advertiser's perspective. Emphasizing a cross-disciplinary approach, we presented sample research directions in keyword selection, traffic prediction and bidding strategy, encouraging the research community to build upon known auction models in order to tackle these even more challenging domains. We explored in more detail specific examples of research in bidding strategies.
• Moreover, in a joint tutorial with H. Roeglin, we presented results in convergence of game dynamics, both to equilibria and nearly-optimal solutions. This was a more algorithm-oriented variant of the tutorial at ICML (which is described in a previous blog post.)

The Ad Auctions Workshop brought together many industry and academic research leaders to discuss ongoing challenges in online advertisement. The topics presented at the workshop included the role of externalities in ad auctions, new truthful ad auction mechanisms with budget constraints, efficiency loss of generalized second-price ad auctions, and complex combinatorial ad auctions. Google researchers co-organized, participated in the discussions, and contributed the following presentations:

• Google's chief economist, Hal Varian, gave an enlightening invited talk about using Google Trends data for "predicting the present." In this work, Google Trends data is used to help improve forecasts of various economic time series. Examples illustrating this technique were drawn from the auto industry, real estate, and unemployment. He emphasized that Google Trends data is publicly available and encouraged people to use this data for their research.
• We presented two papers in the workshop, one about optimal pricing mechanisms over social networks and one about using offline optimization in stochastic online ad allocation problems. In the latter talk, we presented an algorithm in which we use an optimal offline solution in an "expected instance", and use this solution as a signal in online decision making. Using the idea of the power of two choices from the CS literature, we give a novel theoretical analysis of our method, improving the best previously known result. We also gave some practical insight about using these methods in online ad allocation. The theoretical results will appear in the upcoming FOCS 2009 conference.

Motivated by our various ad systems, there is a large research effort at Google around areas at the intersection of Economics, Computer Science and Machine Learning. The Ad Auctions Workshop and ACM Conference on Electronic Commerce are among the best forums for stimulating ideas and collaboration in these interdisciplinary areas.