Synchronous learning of efficient Nash equilibria in potential games with uncoupled dynamics and memoryless players

Game theoretical learning in multi-agent systems is a rapidly developing area of research. It gained popularity since the wide range of optimization problems in multi-agent systems can be reformulated in terms of potential games, where the set of potential function maximizers represents the set of optimal system states. The crucial point of such approach is the design of a distributed algorithm that is guaranteed to converge to the set of potential function maximizers. Various learning algorithms, whose features depend on system properties, have been proposed so far. However, there is currently no learning algorithm that can be efficiently executed in a multi-agent system in which uncoupled agents update their actions synchronously and do not take into account the past history of actions. In this paper, we fill this gap by introducing a new learning algorithm for potential games with uncoupled dynamics and memoryless players who act synchronously. We prove the probabilistic convergence of this algorithm to potential function maximizers, which correspond to the optimal system states under appropriate game settings.