Colloquium Details
Price of Anarchy in Adword Auctions
Speaker: Eva Tardos, Cornell University
Location: Warren Weaver Hall 1302
Date: October 22, 2010, 11:30 a.m.
Host: Joel Spencer
Synopsis:
Generalized Second Price Auction, also known as Ad Word auctions, and its variants has been the main mechanism used by search companies to auction positions for sponsored search links. Online auctions, such as GSP give rise to a number of interesting challenges not traditionally considered by auction theory, e.g., search advertising gives rise of an enormous number of auctions running simultaneously, limiting the applicability of traditional auction theory.
In this talk we consider the quality of outcomes in Generalized Second Price Auction. We will consider the equilibria both in the full information model, and in the Bayesian setting modeling uncertainty using a probability distribution. It is known that in the full information model the Generalized Second Price Auction has socially optimal Nash equilibria (i.e., that the Price of Stability is 1), but not all equilibria are optimal. Even worse, in the Bayesian setting socially optimal Nash equilibria may not exists. In this talk we will show that under some mild assumptions, all Nash equilibria have good quality (i.e., the price of anarchy is small) both in the full information and in the Bayesian settings. The results are joint work with Renato Paes Leme and Brendan Lucier.
Speaker Bio:
Eva Tardos is a Jacob Gould Schurman Professor of Computer Science at Cornell University, and was department chair 2006-2010. She received her PhD from Eotvos University, Budapest. Her research interest is algorithms and algorithmic game theory, the subarea theory of designing systems and algorithms for selfish users. She is most known for her work on network-flow algorithms, approximation algorithms, and quantifying the efficiency of selfish routing. She has been elected to the National Academy of Engineering and the American Academy of Arts and Sciences, and is the recipient of some fellowships and awards, including the Packard Fellowship, the Fulkerson Prize and the Dantzig prize. She was editor in chief of SIAM Journal of Computing 2003-09, and is editor of several other journals, including the Journal of the ACM, and Combinatorica.
Notes:
In-person attendance only available to those with active NYU ID cards.