A First Step Towards Analyzing the Convergence Time in Player-Specific Singleton Congestion Games.

We initiate studying the convergence time to Nash equilibria in player-specific singleton congestion games. We consider simple games that have natural representations as graphs as we assume that each player chooses between two resources. We are not able to present an analysis for general graphs. However, we present first results for interesting classes of graphs. For the class of games that are represented as trees, we show that every best-response schedule terminates after O(n2) steps. We also consider games that are represented as circles. We show that deterministic best response schedules may cycle, whereas the random best response schedule, which selects the next player to play a best response uniformly at random, terminates after O(n2) steps in expectation. These results imply that in player-specific congestion games in which each player chooses between two resources, and each resource is allocated by at most two players, the random best response schedule terminates quickly. Our analysis reveals interesting relationships between random walks on lines and the random best response schedule. [ABSTRACT FROM AUTHOR]