A Simple Learning Rule in Games and Its Convergence to Pure-Strategy Nash Equilibria

摘要

We propose a simple learning rule in games. The proposed rule only requires that (i) if there exists at least one strictly better reply (SBR), an agent switches its action to each SBR with positive probability or stay with the same action (with positive probability), and (ii) when there is no SBR, the agent either stays with the previous action or switches to another action that yields the same payoff. We first show that some of existing algorithms (or simple modifications) are special cases of our proposed algorithm. Secondly, we demonstrate that this intuitive rule guarantees almost sure convergence to a pure-strategy Nash equilibrium in a large class of games that we call generalized weakly acyclic games. Finally, we show that the probability that the action profile does not converge to a pure-strategy Nash equilibrium decreases geometrically fast in the aforementioned class of games.