The speed of convergence in congestion games under best-response dynamics

Angelo Fanelli (), Michele Flammini () and Luca Moscardelli ()
Additional contact information
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique, C2I - Centre for Computational Intelligence [Nanyang] - NTU - Nanyang Technological University [Singapour]
Michele Flammini: GSSI - Gran Sasso Science Institute, DISIM - Department of Information Engineering, Computer Science and Mathematics = Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica [L'Aquila] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Luca Moscardelli: Dipartimento di Scienze - Universita di Chieti-Pescara - UNICH - Universita' degli Studi "G. d'Annunzio" Chieti-Pescara

Post-Print from HAL

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.

Date: 2012-07-01
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Published in ACM Transactions on Algorithms, 2012, 8 (3), pp.1-15. ⟨10.1145/2229163.2229169⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-02094392

DOI: 10.1145/2229163.2229169

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().