Convergence and Approximation in Potential Games

George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos

Abstract

We 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 [7]).
BibTeX
@inproceedings{christodoulou2006convergence,
  author = {George Christodoulou and Vahab S. Mirrokni and Anastasios Sidiropoulos},
  title = {{Convergence and Approximation in Potential Games}},
  booktitle = {STACS},
  year = {2006},
  doi = {10.1007/11672142\_28},
}

Loading related content...

Figure