Tata Institute of Fundamental Research
Uniqueness and Social Cost of Equilibria in Atomic Splittable Routing Games
Student Seminar
Speaker:
Chien-Chung Huang (Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 316
66123 Saarbrücken
Germany)
Date:
Friday, 1 Feb 2013, 14:30 to 16:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In an atomic splittable routing game, each player controls a non-negligible, splittable flow in a network. Each edge has a delay that is a function of the total flow on the edge. Each player seeks a routing strategy to minimize the total delay of his flow, measured as the sum over edges of his flow on the edge times that edge's delay. In this setting, a flow is at a Nash equilibrium if no player can unilaterally alter his individual flow and reduce his total cost.
In this talk, I will discuss two topics about equilibria in atomic splittable routing games. The first is the uniqueness of Nash equilibria. I will give a complete characterization on the multiplicity of equilibria based on graph topology. The second topic is the social cost of equilibria when players form coalitions. In particular, I will talk about the conditions under which the post-collusion equilibrium are guaranteed to have less social cost than the pre-collusion equilibrium.
| Speaker: | Chien-Chung Huang (Max-Planck-Institut für Informatik Department 1: Algorithms and Complexity Campus E1 4, Room 316 66123 Saarbrücken Germany) |
| Date: | Friday, 1 Feb 2013, 14:30 to 16:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
In an atomic splittable routing game, each player controls a non-negligible, splittable flow in a network. Each edge has a delay that is a function of the total flow on the edge. Each player seeks a routing strategy to minimize the total delay of his flow, measured as the sum over edges of his flow on the edge times that edge's delay. In this setting, a flow is at a Nash equilibrium if no player can unilaterally alter his individual flow and reduce his total cost.
In this talk, I will discuss two topics about equilibria in atomic splittable routing games. The first is the uniqueness of Nash equilibria. I will give a complete characterization on the multiplicity of equilibria based on graph topology. The second topic is the social cost of equilibria when players form coalitions. In particular, I will talk about the conditions under which the post-collusion equilibrium are guaranteed to have less social cost than the pre-collusion equilibrium.
In this talk, I will discuss two topics about equilibria in atomic splittable routing games. The first is the uniqueness of Nash equilibria. I will give a complete characterization on the multiplicity of equilibria based on graph topology. The second topic is the social cost of equilibria when players form coalitions. In particular, I will talk about the conditions under which the post-collusion equilibrium are guaranteed to have less social cost than the pre-collusion equilibrium.