Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Friday, November 25, 2016 - 2:05:56 PM
Last modification on : Saturday, June 25, 2022 - 10:22:34 PM
Long-term archiving on: : Monday, March 20, 2017 - 8:58:59 PM


Files produced by the author(s)


  • HAL Id : hal-01403039, version 1


Konstantin Avrachenkov, Vikas Vikram 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⟩



Record views


Files downloads