Monday, January 14th, 2013 4pm-5pm Burnside 1205
Department of Computer Engineering and Informatics, University of Patras
Computing approximate pure Nash equilibria in congestion games

Congestion games constitute an important class of games in which computing an exact or even approximate pure Nash equilibrium is in general PLS-hard. We present a simple polynomial-time algorithm that computes O(1)-approximate Nash equilibria in these games. In particular, for congestion games with linear latency functions, our algorithm computes (2+ε)-approximate equilibria in time polynomial in the number of players, the number of resources and 1/ε. It also applies to games with polynomial latency functions with constant maximum degree d; there, the approximation guarantee is dO(d). The algorithm essentially identifies a polynomially long sequence of best-response moves that lead to an approximate equilibrium. We also discuss extensions to weighted congestion games.

Joint work with Angelo Fanelli (CNRS), Nick Gravin (NTU Singapore), and Alexander Skopalik (University of Paderborn).

Winter 2013 Schedule