Everyone is welcome to attend the public CWI lecture of Pieter Kleer.
Abstract:
Congestion games are an important class of games, introduced by Rosenthal in 1973, which have been studied extensively. Every player has to choose a subset of resources (which is called a strategy), and her pay-off depends on the the chosen resources and the number of other players that choose the same resources. Nash equilibria of such games can be characterized by the local minima of Rosenthal's potential function.
In this work, we consider polytopal congestion games in which the strategies of the players are (implicitly) given as the binary vectors of some player-dependent polytope. The sum of these polytopes is called the aggregation polytope. For aggregation polytopes with a box-totally dual integral (box-TDI) description, and the integer decomposition property (IDP), we give (i) a unifying approach for computing Nash equilibria in (strongly) polynomial time, and (ii) derive tight inefficiency bounds for these equilibria. Examples of polytopal congestion games which satisfy IDP and box-TDI are symmetric totally unimodular congestion games, non-symmetric matroid congestion games, symmetric r-arborescence congestion games, and common source network congestion games. In general, our results also reveal that the combination of IDP and box-TDI gives rise to an efficient approach to compute a pure Nash equilibrium whose inefficiency is much better than in general congestion games.
Joint work with Guido Schaefer
