caa a22 4500 445355069 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00446-011-0145-5 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0145-5 On best response dynamics in weighted congestion games with polynomial delays [Elektronische Daten] [Angelo Fanelli, Luca Moscardelli] We investigate the speed of convergence of best response dynamics to approximately optimal solutions in weighted congestion games with polynomial delay functions. Awerbuch etal. (Fast convergence to nearly optimal solutions in potential games. ACM Conference on Electronic Commerce, 2008) showed that the convergence time of such dynamics to Nash equilibrium may be exponential in the number of players n even for unweighted players and linear delay functions. Nevertheless, we show that Θ(n log log W) (where W is the sum of all the players' weights) 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 non-null) number of best responses. For congestion games in which computing a best response is a polynomial time solvable problem, such a dynamics naturally implies a polynomial time distributed algorithm for the problem of computing the social optimum in congestion games, approximating the optimal solution by a constant factor. Springer-Verlag, 2011 Speed of convergence nationallicence Congestion games nationallicence Algorithmic game theory nationallicence Fanelli Angelo Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Nanyang Avenue, Singapore, Singapore aut Moscardelli Luca Department of Science, University of Chieti-Pescara, Pescara, Italy aut Distributed Computing Springer-Verlag 24/5(2011-12-01), 245-254 0178-2770 24:5<245 2011 24 446 https://doi.org/10.1007/s00446-011-0145-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0145-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fanelli Angelo Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Nanyang Avenue, Singapore, Singapore aut NATIONALLICENCE 700 1- Moscardelli Luca Department of Science, University of Chieti-Pescara, Pescara, Italy aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/5(2011-12-01), 245-254 0178-2770 24:5<245 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer