Fast convergence for time-varying semi-anonymous potential games

摘要

Log-linear learning and its variants have received significant attention in recent literature on networked control systems. In potential games, log-linear learning guarantees that agents' behavior will converge to the potential function maximizer. The appeal of log-linear learning for distributed control stems from the fact that distributed engineering systems can often be modeled as potential games where the potential function maximizers correspond to the optimal system behavior. In this paper we seek to characterize the mixing times for log-linear learning. For a specific class of potential games, called semi-anonymous potential games, previous results have shown that a mild variant of log-linear learning guarantees convergence to the set of potential function maximizers in time that is linear in the number of players. In this paper, we show that such convergence guarantees continue to hold even in the setting where players enter and exit the game.