Congestion Games: Optimization in Competition

Опубликовано 6 сентября 2016, 16:30

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.