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.