Uniqueness and Social Cost of Equilibria in Atomic Splittable Routing Games

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.