|Discrete Mathematics and Optimization Seminar
Monday January 17th at 4.30pm
Title. Network Games and the Price of Anarchy or Stability.
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
behavior of many physical systems, such as electricity in electric networks,
and the distribution of forces in mechanical structures.