Discrete Mathematics and Optimization Seminar

McGill University
Monday January 9th at 4.30pm
Burnside 1205

Title. A Game Theoretic View of Efficiency Loss in Network Resource Allocation.

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; as a result, proposals for network resource allocation must be robust against self-interested
behavior of the network users. With this motivation, we analyze a network congestion game in which the users of congested
finite-capacity links anticipate the effect of their actions on the link prices. We show existence of a Nash equilibrium, discuss
uniqueness, and establish that the efficiency of the system drops by no more than 25% relative to the social optimum.
We conclude by discussing several extensions, including: models where links have elastic capacity and models where the utility of
the players is stochastic. This is joint work with Ramesh Johari, John Tsitsiklis, and Jia-Yu Yuan.