We investigate the speed of convergence of best response dynamics to approximately optimal solutions in weighted congestion games with polynomial delay functions. In [1] it has been shown that the convergence cane of such dynamics to Nash equilibrium may be exponential in the number of players n even for unweighted players and linear delay functions. Nevertheless, extending the work of [11] we show that Theta(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-mill) number of best responses.
On Best Response Dynamics in Weighted Congestion Games with Polynomial Delays
MOSCARDELLI, Luca
2009-01-01
Abstract
We investigate the speed of convergence of best response dynamics to approximately optimal solutions in weighted congestion games with polynomial delay functions. In [1] it has been shown that the convergence cane of such dynamics to Nash equilibrium may be exponential in the number of players n even for unweighted players and linear delay functions. Nevertheless, extending the work of [11] we show that Theta(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-mill) number of best responses.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
