Learning Equilibria in Games by Stochastic Distributed Algorithms

Abstract : We consider a family of stochastic distributed dynamics to learn equilibria in games, that we prove to correspond to an Ordinary Differential Equation (ODE). We focus then on a class of stochastic dynamics where this ODE turns out to be related to multipopulation replicator dynamics. % , well-known and studied in evolutionary game theory. Using facts known about convergence of this ODE, we discuss the convergence of the initial stochastic dynamics. For general games, there might be non-convergence, but when the convergence of the ODE holds, considered stochastic algorithms converge towards Nash equilibria. For games admitting a multiaffine Lyapunov function, we prove that this Lyapunov function is a super-martingale over the stochastic dynamics and that the stochastic dynamics converge. This leads a way to provide bounds on their time of convergence by martingale arguments. This applies in particular for many classes of games considered in literature, including several load balancing games and congestion games.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-polytechnique.archives-ouvertes.fr/hal-00760749
Contributor : Olivier Bournez <>
Submitted on : Tuesday, December 4, 2012 - 1:24:35 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on : Saturday, December 17, 2016 - 7:45:46 PM

File

ISCIS-2012.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00760749, version 1

Collections

Citation

Olivier Bournez, Johanne Cohen. Learning Equilibria in Games by Stochastic Distributed Algorithms. 27th International Symposium on Computer and Information Sciences, ISCIS'2012, 2012, France. ⟨hal-00760749⟩

Share

Metrics

Record views

414

Files downloads

245