Please use this identifier to cite or link to this item:
Title: The speed of convergence in congestion games under best-response dynamics
Authors: Fanelli, Angelo.
Flammini, Michele.
Moscardelli, Luca.
Issue Date: 2012
Source: Fanelli, A., Flammini, M., & Moscardelli, L. (2012). The speed of convergence in congestion games under best-response dynamics. ACM Transactions on Algorithms, 8(3).
Series/Report no.: ACM transactions on algorithms
Abstract: We investigate the speed of convergence of best response dynamics to approximately optimal solutions in congestion games with linear delay functions. In Ackermann et al. [2008] it has been shown that the convergence time of such dynamics to Nash equilibrium may be exponential in the number of players n. Motivated by such a negative result, we focus on the study of the states (not necessarily being equilibria) reached after a limited number of players' selfish moves, and we show that Θ(n log log n) best responses are necessary and sufficient to achieve states that approximate the optimal solution by a constant factor, under the assumption that every O(n) steps each player performs a constant (and nonnull) number of best responses. We show that such result is tight also for the simplest case of singleton congestion games.
ISSN: 1549-6325
DOI: 10.1145/2229163.2229169
Rights: © 2012 ACM.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Citations 20

Updated on Jan 13, 2023

Web of ScienceTM
Citations 20

Updated on Jan 25, 2023

Page view(s) 50

Updated on Jan 28, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.