Skip to Main content Skip to Navigation
Book sections

Stochastic Coalitional Better-Response Dynamics for Finite Games with Application to Network Formation Games

Abstract : We consider a coalition formation among players, in an $n$-player strategic game, over infinite horizon. At each time a randomly selected coalition makes a joint deviation, from a current action profile to a new action profile, which is strictly beneficial for all the players belonging to the coalition. Such deviations define a stochastic coalitional better-response (CBR) dynamics. The stochastic CBR dynamics either converges to a $\cal{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. We prove that all $\cal{K}$-stable equilibria and all action profiles from closed cycles, having minimum stochastic potential, are stochastically stable. Similar statement holds for strict $\cal{K}$-stable equilibrium. We apply the stochastic CBR dynamics to the network formation games. We show that all strongly stable networks and closed cycles of networks are stochastically stable.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-02372761
Contributor : Konstantin Avrachenkov <>
Submitted on : Friday, October 9, 2020 - 3:03:04 PM
Last modification on : Wednesday, October 14, 2020 - 4:21:28 AM

File

Stoch_Col_BRP.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Konstantin Avrachenkov, Vikas Vikram Singh. Stochastic Coalitional Better-Response Dynamics for Finite Games with Application to Network Formation Games. Altman, Eitan; Avrachenkov, Konstantin; De Pellegrini, Francesco; El-Azouzi, Rachid; Wang, Huijuan. Multilevel Strategic Interaction Game Models for Complex Networks, Springer International Publishing, pp.185-199, 2019, 978-3-030-24454-5. ⟨10.1007/978-3-030-24455-2_10⟩. ⟨hal-02372761⟩

Share

Metrics

Record views

52

Files downloads

32