Games in Networks: the price of anarchy and learning – Eva Tardos, Cornell University

Tuesday, December 8, 2009 - 8:53am


3:30 PM – 4:00 PM Reception
4:00 PM – 5:00 PM Talk
Engineering Sciences Building, Room 1001

HOST: Subhash Suri

Computer Science, Cornell University

Title: Games in Networks: the price of anarchy and learning


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 focus on congestion games, and study the degradation of quality of solution caused by the selfish behavior of users. We model users as learning algorithms, and show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game. We use tools from the theory of dynamical systems and algebraic geometry to show when players use a class of natural learning algorithms the distribution of play converges to the set of weakly stable equilibria, and that the set of weakly stable equilibria are the pure Nash equilibria with probability 1 when congestion costs are selected at random independently on each edge (from any monotonically parameterized distribution).


Éva Tardos is a Jacob Gould Schurman Professor of Computer Science, and the Chair of the Department of Computer Science at Cornell University. Her research interest is algorithms and algorithmic game theory, an emerging new area of designing systems and algorithms for selfish users. Her research focuses on algorithms and games on networks. She has been elected to the National Academy of Engineering and the American Academy of Arts and Sciences, and is the recipient of numerous fellowships and awards. She is the editor-in-Chief of SIAM Journal of Computing, and editor of several other journals, including Journal of the ACM, and Combinatorica.