Theoretical Computer Science

Distinguished Lecturer Series

Network Games and the Price of Anarchy or Stability

Eva Tardos

Cornell University

Friday, February 24, 2006
1:00 pm – FIT 1-222

Abstract:

Traditional network design assumes that the network designer has the information and power to decide on the whole network. However, many networks operate and evolve through interactions of large numbers of participants. Such networks play a fundamental role in many domains, ranging from communication networks to social networks. In this talk we will consider settings where multiple agents each pursue their own selfish interests, each represented by his own objective function, caring only about his cost and his part of the network. We will consider settings modeling routing and network formation. In each setting our goal is to quantify the degradation of quality of solution caused by the selfish behavior of users, comparing the selfish outcome to a centrally designed optimum, or comparing outcomes with different levels of cooperation.

Biography of Speaker:

Eva Tardos received her Ph.D. at Eötvös University in Budapest, Hungary in 1984. After teaching at Eötvös and the MIT, she joined Cornell in 1989. She is a member of the American Academy of Arts and Sciences, an ACM Fellow, was a Guggenheim Fellow, a Packard Fellow, a Sloan Fellow; an NSF Presidential Young Investigator; and has received the Fulkerson Prize in 1988. She is the editor of several journals including SIAM Journal of Computing, Journal of the ACM, and Combinatorica.

Tardos’s research interest focuses on the design and analysis of efficient methods for combinatorial-optimization problems on graphs or networks. Such problems arise in many applications such as vision, and the design, maintenance, and management of communication networks. She is mostly interested in fast combinatorial algorithms that provide provably optimal or close-to-optimal results. 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.