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

https://hal.inria.fr/hal-01403039
Contributor : Konstantin Avrachenkov <>
Submitted on : Friday, November 25, 2016 - 2:05:56 PM
Last modification on : Friday, April 30, 2021 - 9:58:07 AM
Long-term archiving on: : Monday, March 20, 2017 - 8:58:59 PM

File

MGT_Strong-Nash.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01403039, version 1

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⟩

Share

Metrics

Record views

428

Files downloads

274