Performance of One-Round Walks in Linear Congestion Games

We investigate the approximation ratio of the solutions achieved after aone-round walk in linear congestion games. We consider the social functions SUM,defined as the sum of the players’ costs, and MAX, defined as the maximum costper player, as a measure of the quality of a given solution. For the social functionSUM and one-round walks starting from the empty strategy profile, we close thegap between the upper bound of 2 + √5 ≈ 4.24 given in Christodoulou et al. Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS, vol. 3884, pp. 349–360, Springer, Berlin, 2006) and the lower bound of 4 derived in Caragiannis et al. (Proceedings of the 33rd InternationalColloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 4051,pp. 311–322, Springer, Berlin, 2006) by providing a matching lower bound whoseconstruction and analysis require non-trivial arguments. For the social function MAX, for which, to the best of our knowledge, no results were known prior to this work, we show an approximation ratio of Theta(n^(3/4)) (resp. Theta(n √n)), where n is the number of players, for one-round walks starting from the empty (resp. an arbitrary) strategyprofile.