Title:

Computing Efficient Nash Equilibria in Congestion Games

Abstract:

Congestion games constitute an important class of games which capture many applications in network routing, resource allocation and scheduling. Intuitively, these games model situations in which several independent agents (or players) compete over a limited number of resources, where each resource has a cost that increases with the number of players using it. The goal of each player is to allocate a feasible subset of the resources such that her individual cost is minimized. 

In a seminal paper, Rosenthal (1973) establishes the existence of pure Nash equilibria in congestion games by exhibiting an exact potential function whose local minima coincide with the set of pure Nash equilibria of the game. This correspondence has helped to shed light on several important aspects of congestion games in recent years. In particular, it is exploited crucially to show that finding pure Nash equilibria is a computationally hard problem in general.

We investigate structural properties which allow us to compute global minima of Rosenthal's potential function efficiently. To this aim, we use a polyhedral description to represent the strategy sets of the players and identify two general properties which are sufficient for our result to go through. In addition, we show that the resulting Nash equilibria provide attractive social cost approximation guarantees. Our contributions thus provide an efficient algorithm to find an approximately optimal Nash equilibrium for a large class of polytopal congestion games. 

In this talk, we review some of the classical results and elaborate in more detail on our recent results on polytopal congestion games (joint work with Pieter Kleer).

Location:

KdVI meeting room, room F3.20