Convergence and approximation in potential games

AbstractWe study the speed of convergence to approximately optimal states in two classes of potential games. We provide bounds in terms of the number of rounds, where a round consists of a sequence of movements, with each player appearing at least once in each round. We model the sequential interaction between players by a best-response walk in the state graph, where every transition in the walk corresponds to a best response of a player. Our goal is to bound the social value of the states at the end of such walks. In this paper, we focus on two classes of potential games: selfish routing games, and cut games (or party affiliation games (Fabrikant et al. 2004 [12])).Other than bounding the price of anarchy of selfish routing games (Roughgarden and Tardos, 2002 [25], Awerbuch et al. 2005 [2], Christodoulou and Koutsoupias, 2005 [9]), there are many interesting problems about game dynamics in these games. It is known that exponentially long best-response walks may exist to pure Nash equilibria (Fabrikant et al. 2004 [12]), and random best-response walks converge to solutions with good approximation guarantees after polynomially many best responses (Goemans et al. 2005 [17]). In this paper, we study the speed of convergence on deterministic best-response walks in these games and prove that starting from an arbitrary configuration, after one round of best responses of players, the resulting configuration is a Θ(n)-approximate solution. Furthermore, we show that starting from an empty configuration, the solution after any round of best responses is a constant-factor approximation. We also provide a lower bound for the multi-round case, where we show that for any constant number of rounds t, the approximation guarantee cannot be better than nϵ(t), for some ϵ(t)>0.We also study cut games, that provide an illustrative example of potential games. The convergence of potential games to locally optimum solutions has been studied in the context of local search algorithms (Johnson et al. 1988 [19], Schaffer and Yannakakis, 1991 [28]). In these games, we consider two social functions: the cut (defined as the weight of the edges in the cut), and the total happiness (defined as the weight of the edges in the cut, minus the weight of the remaining edges). For the cut social function, we prove that the expected social value after one round of a random best-response walk is at least a constant factor approximation to the optimal social value. We also exhibit exponentially long best-response walks with poor social value. For the unweighted version of this cut game, we prove Ω(n) and O(n) lower and upper bounds on the number of rounds of best responses to converge to a constant-factor cut. In addition, we suggest a way to modify the game to enforce a fast convergence in any fair best-response walk. For the total happiness social function, we show that for unweighted graphs of sufficiently large girth, starting from a random configuration, greedy behavior of players in a random order converges to an approximate solution after one round