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

Konstantin Avrachenkov (1, 2) , Vikas Vikram Singh (3)

1 NEO - Network Engineering and Operations
2 COMUE UCA - COMUE Université Côte d'Azur (2015-2019)
3 IIT Delhi - Indian Institute of Technology Delhi

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.

Mots clés: Strong Nash equilibrium; Coalitional better-response; Stochastic stability; Network formation games; Strongly stable networks

Domaines: Informatique et théorie des jeux [cs.GT]; Réseaux sociaux et d'information [cs.SI]; Réseaux et télécommunications [cs.NI]; Optimisation et contrôle [math.OC]

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⟩