Login
Computer Science @ Rochester
Monday, December 06, 2004
11:00 AM
CSB 209
Eva Tardos
Cornell U.
Network Games and the Price of Anarchy or Stability
Networks that operate and evolve through interactions of large numbers of participants play a fundamental role in many domains, ranging from communication networks, such as the Internet, to social networks. These networks, give rise to a number of challenging algorithmic questions.

Traditional algorithm 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. In this talk, we approach traditional algorithmic questions from the perspective of game theory: we will focus on settings where multiple agents each pursue their own selfish interests, each represented by his own objective function. We will consider simple network games modeling routing or network design, and try to quantify the degradation of quality of solution caused by the selfish behavior of users, and design algorithms that can help mitigate this degradation.