Discrete Mathematics and Optimization Seminar


EVA TARDOS
Cornell University
Monday January 17th at 4.30pm
Burnside 1205



Title. Network Games and the Price of Anarchy or Stability.

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.