CS 789 THEORY SEMINAR [home]

Speaker:  Ramesh Johari
Affiliation: Electrical Engineering & Computer Science, MIT
Date: Monday, February 3, 2003
Title: Internet Resource Allocation and a Network Congestion Game

Abstract:

The Internet has evolved into a heterogeneous system, comprised of many users who value their own performance, rather than the efficiency of the system as a whole. To investigate this phenomenon, we explore the properties of a network congestion game where users of a congested resource anticipate the effect of their actions on the price of the resource. We show existence and uniqueness of the Nash equilibrium, and establish that the efficiency of the system drops by no more than a factor of 3/4 relative to the optimal operating point of the network. We also consider extensions to a network context, where users submit individual payments for each link in the network where they require service. In this network model, we again show that the selfish behavior of the users causes the efficiency of the system to fall by no more than a factor of 3/4. These results form part of a growing literature on quantifying the extent to which selfish players affect system efficiency, known as the price of anarchy.

Bio:

Ramesh Johari received his B.A. in Mathematics from Harvard in 1998, and a Certificate of Advanced Study in Mathematics from Cambridge University, U.K., in 1999. During the year 1999-2000, he was a graduate student in the Statistical Laboratory at the University of Cambridge, studying stability of congestion control algorithms under the supervision of Prof. Frank Kelly. Since 2000, he has been a doctoral student in Electrical Engineering and Computer Science at MIT, with Prof. John Tsitsiklis of the Laboratory for Information and Decision Systems. His current research interests are competition and cooperation in distributed network resource allocation.