Performances of One-Round Walks in Linear Congestion Games

摘要

We investigate the approximation ratio of the solutions achieved after a one-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 cost per player, as a measure of the quality of a given solution. For the social function Sum and one-round walks starting from the empty strategy profile, we close the gap between the upper bound of 2 + 5~(1/2) ≈ 4.24 given in [8] and the lower bound of 4 derived in [4] by providing a matching lower bound whose construction 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 θ((n~3)~(1/4)) (resp. θ(n n~(1/2))), where n is the number of players, for one-round walks starting from the empty (resp. an arbitrary) strategy profile.