Computer Science Colloquium, 2006-2007

Michal Feldman
November 29th, 2006

Selfishness and Incentives in Networked Systems

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 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 the inherent tension between individual rationality and
collective welfare in computer networks through several prime examples
from my own research. In the second part of the talk, 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 network routing.

Benny Pinkas