• Calendar

December 26, Tuesday
12:00 – 14:00

The emergence of the Internet has initiated a radical shift of focus of our thinking about computational networked systems. While traditional system design assumes that all participants behave according to the intentions of the system designers, in reality, computer networks are built, operated and used by multiple users with diverse sets of interests. Hence, Internet protocols must be explicitly designed to work with interacting strategic individuals. Recently, there has been a growing interest in using tools from game theory and mechanism design to tackle incentive-related problems in these complex environments. In the first part of the talk, I will give an overview of the field, and demonstrate the inherent tension between individual rationality and collective welfare in computer networks through prime examples from my research. In the second part of the talk, I will concentrate on the inefficiency that is incurred due to users' selfishness in network routing, network formation and multicast transmission. In contrast to the common measure of "price of anarchy", which quantifies the loss incurred due to both selfishness and lack of coordination, we isolate the inefficiency originated from selfishness from that originated from lack of coordination. We show that coordination among selfish users can significantly improve the efficiency of the studied applications.