Consider a 2-player normal-form game repeated over time. We introduce an adaptive learning procedure, where the players only observe their own realized payoff at each stage. We assume that agents do not know their own payoff function, and have no information on the other player. Furthermore, we assume that they have restrictions on their own action set such that, at each stage, their choice is limited to a subset of their action set. We prove that the empirical distributions of play converge to the set of Nash equilibria for zero-sum and potential games, and games where one player has two actions.
Let @math be a compact convex subset of an euclidean space and, for all @math , let @math . We are interested in the asymptotic behavior of the random sequence @math . Let us call In order to maintain the terminology employed in @cite_25 , we introduce the following definition, which is stated in a slightly different form (see [Definition 2.4] br10 ).
@cite_25
2091328462
This paper studies a class of non-Markovian and nonhomogeneous stochastic processes on a finite state space. Relying on a recent paper by Benaim, Hofbauer, and Sorin [SIAM J. Control Optim., 44 (2005), pp. 328-348] it is shown that, under certain assumptions, the asymptotic behavior of occupation measures can be described in terms of a certain set-valued deterministic dynamical system. This provides a unified approach to simulated annealing type processes and permits the study of new models of vertex reinforced random walks and new models of learning in games such as Markovian fictitious play.