Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 316
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.