Market Algorithms and Optimization Meeting

Vahab S. Mirrokni and Muthu Muthukrishnan

Google auctions ads, and enables a market with millions of advertisers and users.  This market presents a unique opportunity to test and refine economic principles as applied to a very large number of interacting, self-interested parties with a myriad of objectives. Researchers in economics, computer science, operations research, marketing and business are increasingly involved in defining, understanding and influencing this market.

On January 7th, a group of computer science researchers from Google and various universities formed a workshop to discuss key research directions in this area, specifically "Market Algorithms and Optimization." Corinna Cortes (Head, Google Research, NY)  and Alfred Spector (VP of Research, Google) gave short talks about research groups in Google, academic collaborations, and research awards. The morning session comprised talks by Google researchers including Noam Nisan, Jon Feldman, Vahab Mirrokni, Yishay Mansour, and Muthu Muthukrishnan. These talks explored the following topics and key issues:

• Role of budgets. Identify suitable properties of mechanisms for repeated auctions in the presence of budgets. Truthfulness is impossible, and may not be the suitable property.  
• Advertisers' bidding strategies. While bidding equally on all keywords has certain desirable properties,  identify other bidding strategies if advertisers want to maximize different utility functions and  use rich bidding features.
• Dynamics of ad games. Understand dynamics of sophisticated advertiser bidder strategies under various ad allocation rules. For proportional allocation rules, the dynamics of simple bidder strategies are described here.
• Online Reservations. Design suitable mechanisms for selling ad inventory in the future rather than on the spot. Models and methods for what happens when reservations can not be honored are explored in WWW08, WINE08, and SODA09 papers.

The research presented in these talks can be found at the Google publications site. Some general research directions and open problems in ad auctions are here.

The post-lunch (sushi included of course) session comprised talks by researchers from academia.  Bobby Kleinberg (Cornell) went first and took the audience far into projective geometry in an attempt to understand equilibria resulting from a sequence of selfish behavior of players using specific learning algorithms. Silvio Micali (MIT) described how difficult it was to model or propose mechanisms in presence of collusions, and then went on to show how to correctly design such mechanisms for combinatorial auctions. Kamesh Munagala (Duke Univ.) and Anna Karlin ( U. Wash) discussed algorithmic problems related to ad auctions, including how to run auctions in presence of advertisers with mixed utilities and tight remnant budgets. Other participants -- Richard Cole (NYU), Amos Fiat (Tel Aviv), Uri Feige (Weizmann), Michel Goemans (MIT), Anupam Gupta (CMU),   Nicole Immorlica (Northwestern), Michael Rabin (Harvard), and Eva Tardos (Cornell) -- kept it lively with questions and discussions.

Part of what makes Google ad systems exciting is the challenges they pose and overcome, and yet others in the horizon. It is remarkable how some of the fundamental problems Google ad systems grapple with are also some of the hardest research problems in the community of Market Algorithms.  Joint Google and Academia meetings like this help researchers begin to attack these problems, and may be a model for  research collaborations in the future.