Abstract:

The emergence of the Internet has initiated a radical shift of
focus of our thinking about 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 rational 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 its significance through several prime
examples from my research. In the second part, I will concentrate
on the efficiency loss that is incurred due to users' selfishness
in network routing and network formation. In contrast to the common
measure of "price of anarchy", which quantifies the loss incurred
due to both selfishness and lack of coordination, we acknowledge
the ability of users to coordinate, thus propose to isolate the
loss incurred due to selfishness alone. We show that coordination
among selfish users significantly reduces the price of the open
architecture of Internet-like networks and selfish routing.