Stochastic Coalitional Better-response Dynamics and Stable 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 the 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 K-stable equilibrium or becomes stuck 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 K-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar statement holds for strict K-stable equilibrium. We apply the CBR dynamics to study the dynamic formation of the networks in the presence of mutations. Under the CBR dynamics all strongly stable networks and closed cycles of networks are stochastically stable.
Type de document :
Article dans une revue
Mathematical Game Theory and Applications, Institute of Applied Mathematical Research Karelian Research Centre of RAS, 2016
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01403039
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 25 novembre 2016 - 14:05:56
Dernière modification le : jeudi 5 avril 2018 - 12:30:09
Document(s) archivé(s) le : lundi 20 mars 2017 - 20:58:59

Fichier

MGT_Strong-Nash.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01403039, version 1

Collections

Citation

Konstantin Avrachenkov, Vikas Singh. Stochastic Coalitional Better-response Dynamics and Stable Equilibrium. Mathematical Game Theory and Applications, Institute of Applied Mathematical Research Karelian Research Centre of RAS, 2016. 〈hal-01403039〉

Partager

Métriques

Consultations de la notice

268

Téléchargements de fichiers

61