Stochastic Coalitional Better-response Dynamics and Strong Nash Equilibrium

Abstract : We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a strong Nash equilibrium or stucks in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all strong Nash equilibria and closed cycles are stochastically stable, i.e., they are selected by perturbed CBR dynamics as mutations vanish. Similar statement holds for strict strong Nash equilibrium. We apply CBR dynamics to the network formation games and we prove that all strongly stable networks and closed cycles are stochastically stable.
Type de document :
Rapport
[Research Report] RR-8716, Inria Sophia Antipolis; INRIA. 2015
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01143912
Contributeur : Konstantin Avrachenkov <>
Soumis le : lundi 20 avril 2015 - 14:55:48
Dernière modification le : jeudi 11 janvier 2018 - 16:58:00
Document(s) archivé(s) le : lundi 14 septembre 2015 - 10:51:27

Fichiers

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

Identifiants

  • HAL Id : hal-01143912, version 1
  • ARXIV : 1506.03311

Collections

Citation

Konstantin Avrachenkov, Vikas Vikram Singh. Stochastic Coalitional Better-response Dynamics and Strong Nash Equilibrium. [Research Report] RR-8716, Inria Sophia Antipolis; INRIA. 2015. 〈hal-01143912〉

Partager

Métriques

Consultations de la notice

276

Téléchargements de fichiers

75