Éva Tardos, Department of Computer Science, Cornell University
Games and Networks and the Quality of Outcomes

audio and slides of talks

Network games play a fundamental role in understanding behavior in many domains, ranging from communication networks through markets to social networks. Such networks are used, and also evolve due to selfish behavior of the users and owners. In light of these competing forces, it is surprising how efficient these networks are. It is an exciting challenge to understand the operation and success of these networks in game theoretic terms: what principles of interaction lead selfish participants to form such efficient networks?

We will study the degradation of quality of solution caused by the selfish behavior of users in a number of different games including congestion games that model routing or cost-sharing, and games that model Ad-Auctions. In each setting our goal is to quantify the degradation of quality of solution caused by the selfish behavior of user. We compare the selfish outcome to a centrally designed optimum both in terms of the quality of Nash equilibria and also the quality of outcomes of learning behavior by the users.

Eva Tardos is a Jacob Gould Schurman Professor of Computer Science Cornell University. She received her Dipl.Math. in 1981, and her Ph.D. 1984, from Eötvös University, Budapest, Hungary. She is currently the Chair of the Department of Computer Science at Cornell. She has been elected to the National Academy of Engineering and the American Academy of Arts and Sciences, and is the recipient of Packard, Sloan Foundation, and Guggenheim fellowship, an ACM Fellow, INFORMS fellow; and has received the Fulkerson Prize, and the Dantzig prize. She is the editor editor-in-Chief of SIAM Journal of Computing, and editor of several other journals including Journal of the ACM, and Combinatorica.

Tardos's research interest is algorithms and algorithmic game theory. Her work focuses on the design and analysis of efficient methods for combinatorial-optimization problems on graphs or networks. She is most known for her work on network-flow algorithms, approximation algorithms for network flows, cut, and clustering problems. Her recent work focuses on algorithmic game theory, an emerging new area of designing systems and algorithms for selfish users.