### Abstract

Congestion games constitute an important class of games in which computing an exact or even approximate pure Nash equilibrium is in general {\sf PLS}-complete. We present a surprisingly 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+\epsilon)$-approximate pure Nash equilibria in time polynomial in the number of players, the number of resources and $1/\epsilon$. It also applies to games with polynomial latency functions with constant maximum degree $d$; there, the approximation guarantee is $d^{O(d)}$. The algorithm essentially identifies a polynomially long sequence of best-response moves that lead to an approximate equilibrium; the existence of such short sequences is interesting in itself. These are the first positive algorithmic results for approximate equilibria in non-symmetric congestion games. We strengthen them further by proving that, for congestion games that deviate from our mild assumptions, computing $\rho$-approximate equilibria is {\sf PLS}-complete for any polynomial-time computable $\rho$.

Original language | English |
---|---|

Title of host publication | 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science |

Pages | 532-541 |

Number of pages | 10 |

ISBN (Electronic) | 978-0-7695-4571-4 |

DOIs | |

Publication status | Published - 2011 |

Event | 52nd Annual Symposium on Foundations of Computer Science 2011 - Hotel Zoso , Palm Springs, United States Duration: 22 Oct 2011 → 25 Oct 2011 Conference number: 52 http://ieee-focs.org/focs2011/ |

### Conference

Conference | 52nd Annual Symposium on Foundations of Computer Science 2011 |
---|---|

Abbreviated title | FOCS 2011 |

Country | United States |

City | Palm Springs |

Period | 22/10/11 → 25/10/11 |

Internet address |

### Keywords

- approximate pure Nash equilibria
- computation and complexity
- congestion games

## Fingerprint Dive into the research topics of 'Efficient computation of approximate pure Nash equilibria in congestion games'. Together they form a unique fingerprint.

## Cite this

Caragiannis, I., Fanelli, A., Gravin, N., & Skopalik, A. (2011). Efficient computation of approximate pure Nash equilibria in congestion games. In

*2011 IEEE 52nd Annual Symposium on Foundations of Computer Science*(pp. 532-541) https://doi.org/10.1109/FOCS.2011.50