Discrete Mathematics and Optimization Seminar
SHIE MANNOR |
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.