"Near-Optimal Greedy Mechanisms"
Eva Tardos
Jacob Gould Schurman Professor of Computer Science
Cornell University
Monday, May 7th, 2012, 11:00 am
EBU3B, Room 1202
Abstract
The design and analysis of Internet and web applications requires careful consideration of possible strategic behavior of the users of the system. The economic theory of mechanism design gives foundations for these sorts of design questions; however, the mechanisms it proposes tend to be complex and therefore impractical. To address this shortcoming, the simplicity of a mechanism should be held at least as important as the quality of outcomes it produces. Given the prevalence of very simple mechanisms in practice, it is fundamental to understand properties of these mechanisms and the environments in which they perform well. Over the last decade computer scientists and game theorists have developed good understanding of the impact of strategic user behavior on system performance in many environments including selfish traffic routing, service location, and bandwidth sharing. In this talk we will consider mechanisms based on simple greedy algorithms from this perspective.
Short biography
Eva Tardos is a Jacob Gould Schurman Professor of Computer Science at Cornell University, is Senior Associate Dean of Computing and Information Science, and was department chair 2006-2010. 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 subarea theory of designing systems and algorithms for selfish users.