Complexity and Optimality of the Best Response Algorithm in Random Potential Games

Stéphane Durand 1, 2 Bruno Gaujal 2, 3
1 NECS - Networked Controlled Systems
Inria Grenoble - Rhône-Alpes, GIPSA-DA - Département Automatique
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Résumé : Dans cet article, nous calculons le temps d’exécution en moyenne et en pire cas de l’algorithme de meilleure réponse (AMR) pour calculer un équilibre de Nash pur dans les jeux de potentiel finis. Notre approche utilise une chaîne de Markov pour modéliser le comportement de AMR et un couplage qui transforme le temps d’exécution de AMR en la solution d’une équation différentielle. Pour un jeu de potentiel avec N joueurs et A stratégies par joueur, le nombre d’itérations de AMR est exactement N A^(N-1), dans le pire cas et e^gamma N + O(N) dans le cas moyen, où est la constante d’Euler. Nous montrons aussi que le nombre de changements d’état est \log N + c + O(1/N) (with c < e^\gamma), en moyenne. Finalement, nous montrons aussi que AMR calcule un équilibre de Nash plus vite que tout algorithme de recherche local, pour l’ordre stochastique fort.
Type de document :
Rapport
[Research Report] RR-8925, Inria - Research Centre Grenoble – Rhône-Alpes; Grenoble 1 UGA - Université Grenoble Alpe. 2016, pp.30
Liste complète des métadonnées

https://hal.inria.fr/hal-01330805
Contributeur : Stephane Durand <>
Soumis le : mardi 12 juillet 2016 - 13:52:30
Dernière modification le : jeudi 11 janvier 2018 - 06:27:41

Fichier

RR-8925v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01330805, version 2

Citation

Stéphane Durand, Bruno Gaujal. Complexity and Optimality of the Best Response Algorithm in Random Potential Games. [Research Report] RR-8925, Inria - Research Centre Grenoble – Rhône-Alpes; Grenoble 1 UGA - Université Grenoble Alpe. 2016, pp.30. 〈hal-01330805v2〉

Partager

Métriques

Consultations de la notice

638

Téléchargements de fichiers

121