Computer Science/Discrete Mathematics Seminar I

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.