Résultat de la recherche
Strongly Vertex-Reinforced-Random-Walk on the complete graph
We study Vertex-Reinforced-Random-Walk on the complete graph with weights of the form $w(n)=n^\alpha$, with $\alpha>1$. Unlike for the Edge-Reinforced-Random-Walk, which in this case localizes a.s. on 2 sites, here we observe various phase transitions, and in particular localization on arbitrary large sets is possible, provided $\alpha$ is close enough to 1. Our proof relies on stochastic approximation techniques. At the end of the paper, we also prove a general result ensuring that any strongly reinforced VRRW on any bounded degree graph localizes a.s. on a finite subgraph.
Stochastic approximations and differential inclusions
The dynamical systems approach to stochastic approximation is generalized to the case where the mean differential equation is replaced by a differential inclusion. The limit set theorem of Benaim and Hirsch is extended to this situation. Internally chain transitive sets and attractors are studied in detail for set-valued dynamical systems. Applications to game theory are given, in particular to Blackwell's approachability theorem and the convergence of fictitious play.
Stochastic approximation algorithms with constant step size whose average is cooperative
We consider stochastic approximation algorithms with constant step size whose average ordinary differential equation (ODE) is cooperative and irreducible. We show that, under mild conditions on the noise process, invariant measures and empirical occupations measures of the process weakly converge (as the time goes to infinity and the step size goes to zero) toward measures which are supported by stable equilibria of the ODE. These results are applied to analyzing the long-term behavior of a class of learning processes arising in game theory.
Stochastic approximations and differential inclusions, part II: Applications
We apply the theoretical results on "stochastic approximations and differential inclusions" developed in Benaim et al. [M. Benaim, J. Hofbauer, S. Sorin. 2005. Stochastic approximations and differential inclusions. SIAM J. Control Optim. 44 328-348] to several adaptive processes used in game theory, including classical and generalized approachability, no-regret potential procedures (Hart and Mas-Colell [S. Hart, A. Mas-Colell. 2003. Regret-based continuous time dynamics. Games Econom. Behav. 45 375-394]), and smooth fictitious play [D. Fudenberg, D. K. Levine. 1995. Consistency and cautious fictitious play. J. Econom. Dynam. Control 19 1065-1089].