Abstract |
In this talk we give a brief outline of our recent results about the speed of convergence of best response dynamics to approximate solutions in congestion games with linear latency functions, in which the social cost is defined as the sum of the players’ cost. Namely, we present new bounds on the social performance achieved after any k-round walk starting from an arbitrary state and after any 1-round walk starting from the empty state. In particular, we show that the approximation ratio of the solution achieved after k-round walks is O( 2k−1 p n). For constant values of k such a bound asymptotically matches the ( 2k−1 p n/k) lower bound that we determine as a refinement of the one provided by Christodoulou et al.(STACS ’06). We then provide a new lower bound of ( 2k−1 p n) for load balancing games (that is congestion games in which every strategy consists of a single resource), thus showing that a number of rounds proportional to log log n is necessary and sufficient also under such a restriction. Finally, we prove that the approximation ratio of the solution reached after a 1-round walk starting from the empty state is at most 4, thus improving the 4.24 bound provided by Christodoulou et al.(STACS ’06). We also give a matching lower bound. |