Games in Networks

Friday, September 28, 2007 - 4:30pm
Tennenbaum Auditorium in the Instructional Center
√Čva Tardos
Cornell University, Computer Science

Many large networks operate and evolve through interactions of large numbers of diverse participants. Such networks play a fundamental role in many domains, ranging from communication networks to social networks. In light of these competing forces, it is surprising how efficient these networks are. It is an exciting challenge to understand the success of these networks in game theoretic terms; what principles of interaction lead selfish participants to form such efficient networks? In this talk we present a number of network formation and routing games. We focus on simple games that have been analyzed in terms of the efficiency loss that results from selfishness. In each setting our goal is to quantify the degradation of quality of solution caused by the selfish behavior of users, comparing the selfish outcome to a centrally designed optimum, or comparing outcomes with different levels of cooperation.