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.
|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.  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.||URI:||https://hdl.handle.net/10356/98035
|ISSN:||1549-6325||DOI:||http://dx.doi.org/10.1145/2229163.2229169||Rights:||© 2012 ACM.||Fulltext Permission:||none||Fulltext Availability:||No Fulltext|
|Appears in Collections:||SPMS Journal Articles|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.