Stochastic Coalitional Better-Response Dynamics for Finite Games with Application to Network Formation Games - Archive ouverte HAL Access content directly
Book Sections Year : 2019

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

(1, 2) , (3)
1
2
3
Konstantin Avrachenkov
Vikas Vikram Singh
• Function : Author

#### 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.

### Dates and versions

hal-02372761 , version 1 (09-10-2020)

### Identifiers

• HAL Id : hal-02372761 , version 1
• DOI :

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

47 View