## Speaker:

## Affiliation:

Max-Planck-Institut für Informatik

Department 1: Algorithms and Complexity

Campus E1 4, Room 316

66123 Saarbrücken

Germany

## Webpage:

## Time:

## Venue:

- A-212 (STCS Seminar Room)

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.