Le séminaire algorithmique du plateau de Saclay aura lieu le vendredi 9 décembre, à 14H30 2016 au LRI, salle des thèses.

Abstract: Suppose that, at each stage of a repeated non-cooperative game, all players update their individual actions following some rationally justifiable learning rule (for instance, an algorithm that leads to no regret). Does this imply that the players’ actions converge to a Nash equilibrium of the one-shot game? And, if so, does this remain true if the information available to the players is contaminated by noise and uncertainty?

In this talk, we will focus on games with continuous action spaces where players adjust their actions by taking small steps along their individual payoff gradients and then “mirror” the output back to their action spaces to obtain a feasible action. A key element in the analysis of this class of “mirror ascent” schemes is the notion of variational stability (VS), a close relative of the seminal notion of evolutionary stability that was introduced for population games by John Maynard Smith (1972). We will study this relationship in detail, and we will derive conditions under which the process converges (locally or globally) with probability 1, irrespective of the level of the noise. If time permits, we will also discuss the implications of these results for finite games.