Congestion Games: Optimization in Competition

Congestion games are a natural approach to model resource allocation among selfish or myopic players. In a congestion game there is a set of resources, and a strategy of a player corresponds to the selection of a subset of these resources, e.g., each player aims at allocating a shortest path between a source/destination pair in a given network or each player aims at allocating a minimum weight spanning tree in a given graph. The cost (delay, payoff) of a resource (edge) is a function of the congestion, i.e., the number of players allocating the resource.

We survey recent results on the complexity of computing Nash equilibria for congestion games and the convergence time towards Nash equilibria. In particular, we study how the combinatorial structure of the strategy spaces influences the complexity and convergence time. We also discuss extensions of congestion games towards congestion games with weighted players and player-specific latency functions.

This talk is based on joint work with Heiner Ackermann and Berthold Voecking.

Speaker Details

Since 2004 PhD-student in the research group of Berthold Voecking at RWTH Aachen, Germany.

Date:
Speakers:
Heiko Röglin
Affiliation:
Department of Computer Science, RWTH Aachen, Germany
    • Portrait of Jeff Running

      Jeff Running