Distinguished Lecturer Series

Network Games and the Price of Stability or Anarchy

Eva Tardos

Cornell University

Friday, February 25, 2005
10:30am - SENSQ 5317

Refreshments at 10:00am

Abstract

In this talk we will consider settings where multiple agents each pursue their own selfish interests, each represented by his own objective function. Traditional algorithms design assumes that the problem is described by a single objective function, and the algorithm designer has the information and power to decide on the outcome. Our goal is to quantify the degradation of quality of solution caused by the selfish behavior of users, compared to a centrally designed optimum.

We will consider simple network games modeling routing or network design. Networks that operate and evolve through interactions of large numbers of participants play a fundamental role in many domains, ranging from communication networks to social networks. They can also naturally model the behavior of many physical systems, such as electricity in electric networks, and the distribution of forces in mechanical structures.

Biography of Speaker

Éva 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.