Best-response dynamics, playing sequences, and convergence to equilibrium in random games
We analyze the performance of the best-response dynamic across all normal-form games using a random games approach. The playing sequence -- the order in which players update their actions -- is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of games (e.g. in potential games) but, when evaluated across all possible games, convergence to equilibrium depends on the playing sequence in an extreme way. Our main asymptotic result shows that the best-response dynamic converges to a pure Nash equilibrium in a vanishingly small fraction of all (large) games when players take turns according to a fixed cyclic order. By contrast, when the playing sequence is random, the dynamic converges to a pure Nash equilibrium if one exists in almost all (large) games.
Code (0)
등록된 구현이 없습니다.
Tasks
AllSimilar Papers 제목 키워드 기반
Fictitious play in zero-sum stochastic games
We present a novel variant of fictitious play dynamics combining classical fictitious play with Q-learning for stochastic games and analyze its convergence properties in two-player zero-sum stochastic games. Our dynamics…
Q-LearningIndependent Learning in Stochastic Games
Reinforcement learning (RL) has recently achieved tremendous successes in many artificial intelligence applications. Many of the forefront applications of RL involve multiple agents, e.g., playing chess and Go games, aut…
Autonomous DrivingReinforcement Learning (RL)Fast computation of Nash Equilibria in Imperfect Information Games
We introduce and analyze a class of algorithms, called Mirror Ascent against an Improved Opponent (MAIO), for computing Nash equilibria in two-player zero-sum games, both in normal form and in sequential imperfect inform…
FormLearning in games via reinforcement and regularization
We investigate a class of reinforcement learning dynamics where players adjust their strategies based on their actions' cumulative payoffs over time - specifically, by playing mixed strategies that maximize their expecte…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Best Response Convergence for Zero-sum Stochastic Dynamic Games with Partial and Asymmetric Information
We analyze best response dynamics for finding a Nash equilibrium of an infinite horizon zero-sum stochastic linear quadratic dynamic game (LQDG) with partial and asymmetric information. We derive explicit expressions for…