Efficient computation of approximate pure Nash equilibria in congestion games

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    33 Citations (Scopus)

    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 languageEnglish
    Title of host publication2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
    Pages532-541
    Number of pages10
    ISBN (Electronic)978-0-7695-4571-4
    DOIs
    Publication statusPublished - 2011
    Event52nd Annual Symposium on Foundations of Computer Science 2011 - Hotel Zoso , Palm Springs, United States
    Duration: 22 Oct 201125 Oct 2011
    Conference number: 52
    http://ieee-focs.org/focs2011/

    Conference

    Conference52nd Annual Symposium on Foundations of Computer Science 2011
    Abbreviated titleFOCS 2011
    CountryUnited States
    CityPalm Springs
    Period22/10/1125/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