This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) and provides a stochastic-stability analysis in repeatedly-played, positive-utility, finite strategic-form games. Prior work in this class of learning dynamics primarily analyzes asymptotic convergence through stochastic approximations, where convergence can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through an ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the analysis to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing asymptotic convergence that is based upon an explicit characterization of the invariant probability measure of the induced Markov chain. We further provide a methodology for computing the invariant probability measure in positive-utility games, together with an illustration in the context of coordination games.
Although excluding convergence to non-Nash action profiles can be guaranteed by sufficiently small @math , establishing convergence to action profiles that are Nash equilibria () may still be an issue. This is desirable in the context of coordination games @cite_17 , where Pareto-efficient outcomes are usually pure Nash equilibria (see, e.g., the definition of a coordination game in @cite_26 ). As shown in @cite_2 , convergence to pure Nash equilibria can be guaranteed only under strong conditions in the utility function. For example, as shown in [Proposition 8] ChasparisShammaRantzer15 , and under the ODE-method for stochastic approximations, it requires a) the existence of a potential function, and b) conditions over the Jacobian matrix of the potential function. Even if a potential function does exist, verifying conditions (b) is practically infeasible for games of more than 2 players @cite_2 .
@cite_26 @cite_2 @cite_17
2570514057 2015836240
We consider the problem of distributed convergence to efficient outcomes in coordination games through dynamics based on aspiration learning. Our first contribution is the characterization of the asymptotic behavior of the induced Markov chain of the iterated process in terms of an equivalent finite-state Markov chain. We then characterize explicitly the behavior of the proposed aspiration learning in a generalized version of coordination games, examples of which include network formation and common-pool games. In particular, we show that in generic coordination games the frequency at which an efficient action profile is played can be made arbitrarily large. Although convergence to efficient outcomes is desirable, in several coordination games, such as common-pool games, attainability of fair outcomes, i.e., sequences of plays at which players experience highly rewarding returns with the same frequency, might also be of special interest. To this end, we demonstrate through analysis and simulations that aspiration learning also establishes fair outcomes in all symmetric coordination games, including common-pool games. @PARASPLIT Read More: http: epubs.siam.org doi abs 10.1137 110852462 A particle in Rd moves in discrete time. The size of the nth step is of order 1 n and when the particle is at a position v the expectation of the next step is in the direction F(v) for some fixed vector function F of class C2. It is well known that the only possible points p where v(n) may converge are those satisfying F(p) = 0. This paper proves that convergence to some of these points is in fact impossible as long as the "noise" -the difference between each step and its expectation-is sufficiently omnidirectional. The points where convergence is impossible are the unstable critical points for the autonomous flow (d dt)v(t) = F(v(t)). This generalizes several known results that say convergence is impossible at a repelling node of the flow.