Penalty-Regulated Dynamics and Robust Learning Procedures in Games

Abstract : Starting from a heuristic learning scheme for N-person games, we derive a new class of continuous-time learning dynamics consisting of a replicator-like drift adjusted by a penalty term that renders the boundary of the game's strategy space repelling. These penalty-regulated dynamics are equivalent to players keeping an exponentially discounted aggregate of their ongoing payoffs and then using a smooth best response to pick an action based on these performance scores. Owing to this inherent duality, the proposed dynamics satisfy a variant of the folk theorem of evolutionary game theory and they converge to (arbitrarily precise) approximations of Nash equilibria in potential games. Motivated by applications to traffic engineering, we exploit this duality further to design a discrete-time, payoff-based learning algorithm which retains these convergence properties and only requires players to observe their in-game payoffs: moreover, the algorithm remains robust in the presence of stochastic perturbations and observation errors, and it does not require any synchronization between players.
Type de document :
Article dans une revue
Mathematics of Operations Research, INFORMS, 2015, 40 (3), pp.611-633. 〈10.1287/moor.2014.0687〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01235243
Contributeur : Bruno Gaujal <>
Soumis le : dimanche 29 novembre 2015 - 19:38:30
Dernière modification le : samedi 18 février 2017 - 01:17:02
Document(s) archivé(s) le : samedi 29 avril 2017 - 02:14:02

Fichier

1303.2270v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Coucheney, Bruno Gaujal, Panayotis Mertikopoulos. Penalty-Regulated Dynamics and Robust Learning Procedures in Games. Mathematics of Operations Research, INFORMS, 2015, 40 (3), pp.611-633. 〈10.1287/moor.2014.0687〉. 〈hal-01235243〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

74