**Tuesday, 14:15 - 14:40 h, Room: MA 043**

**Martin Gairing**

Coordination mechanisms for congestion games

**Coauthor: Giorgos Christodoulou**

**Abstract:**

In a congestion game, we are given a set of resources and each player selects a subset of them (e.g., a path in a network). Each resource has a univariate cost (or utility) function that only depends on the load induced by the players that use it. Each player aspires to minimise (maximise) the sum of the resources's cost (utilities) in its strategy given the strategies

chosen by the other players.

Congestion games have played a starring role in recent research on quantifying the inefficiency of game theoretic equilibria. Most of this research focused on the price of anarchy.

In this talk, we will discuss coordination mechanisms for congestion games. That is, we study how much we can improve the price of anarchy by certain local modifications to the resource cost/utility functions. We will also discuss when such modifications yield polynomial-time convergence of best-reply dynamics.

Talk 3 of the invited session Tue.2.MA 043

**"Coordination mechanisms for efficient equilibria"** [...]

Cluster 8

**"Game theory"** [...]