Eva Tardos Presentation
Eva Tardos from the Computer Science Department at Cornell University will present on "The Price of Anarchy in Adword Auctions" on March 16, 2011 at 4:00 pm in O'Neill 247.
Eva Tardos is a Jacob Gould Schurman Professor of Computer Science at Cornell University, and was department chair 2006-2010. She is currently on leave at Microsoft Research New England. She received her PhD from Eotvos University in Budapest. 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. Her research interest is algorithms and algorithmic game theory, the sub area theory of designing systems and algorithms for selfish users.
Abstract: The Generalized Second Price Auction has been the main mechanism used by search companies to auction positions for advertisements on search pages. In this paper we study the social welfare of the Nash equilibria of this game in various models. In the full information setting, socially optimal Nash equilibria are known to exist (i.e., the Price of Stability is 1). This paper is the first to prove bounds on the price of anarchy, and to give any bounds in the Bayesian setting. Our main result is to show that the price of anarchy is small assuming that all bidders play undominated strategies. In the full information setting we prove a bound of 1.618 for the price of anarchy for pure Nash equilibria, and a bound of 4 for mixed Nash equilibria. We also prove a bound of 8 for the price of anarchy in the Bayesian setting, when valuations are drawn independently, and the valuation is known only to the bidder and only the distributions used are common knowledge. Our proof exhibits a combinatorial structure of Nash equilibria and uses this structure to bound the price of anarchy. While establishing the structure is simple in the case of pure and mixed Nash equilibria, the extension to the Bayesian setting requires the use of novel combinatorial techniques that can be of independent interest.