|Discrete Mathematics and Optimization Seminar
Monday January 9th at 4.30pm
Title. A Game Theoretic View of Efficiency Loss in Network Resource Allocation.
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