Fast convergence to nearly optimal solutions in potential games

Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab Seyed Mirrokni, Alexander Skopalik

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

    82 Citations (Scopus)
    1 Downloads (Pure)


    We study the speed of convergence of decentralized dynam-ics to approximately optimal solutions in potential games. We consider α-Nash dynamics in which a player makes a move if the improvement in his payoff is more than an α fac-tor of his own payoff. Despite the known polynomial conver-gence of α-Nash dynamics to approximate Nash equilibria in symmetric congestion games [7], it has been shown that the convergence time to approximate Nash equilibria in asym-metric congestion games is exponential [25]. In contrast to this negative result, and as the main result of this paper, we show that for asymmetric congestion games with linear and polynomial delay functions, the convergence time of α-Nash dynamics to an approximate optimal solution is polynomial in the number of players, with approximation ratio that is arbitrarily close to the price of anarchy of the game. In particular, we show this polynomial convergence under the minimal liveness assumption that each player gets at least one chance to move in every T steps. We also prove that the same polynomial convergence result does not hold for (ex-act) best-response dynamics, showing the α-Nash dynamics is required. We extend these results for congestion games to other potential games including weighted congestion games with linear delay functions, cut games (also called party af-filiation games) and market sharing games.
    Original languageEnglish
    Title of host publicationProceedings of the 9th ACM conference on Electronic commerce - EC '08
    Publication statusPublished - 2008
    Event9th ACM conference on Electronic commerce 2008 - Chicago, United States
    Duration: 8 Jul 200812 Jul 2008
    Conference number: 9


    Conference9th ACM conference on Electronic commerce 2008
    Abbreviated titleEC 2008
    CountryUnited States
    Internet address


    • congestion games
    • conver-
    • game theory
    • gence time
    • nash equilibrium
    • potential games
    • price of anarchy

    Fingerprint Dive into the research topics of 'Fast convergence to nearly optimal solutions in potential games'. Together they form a unique fingerprint.

    Cite this