https://hal.inria.fr/hal-02372761Avrachenkov, KonstantinKonstantinAvrachenkovNEO - Network Engineering and Operations - CRISAM - Inria Sophia Antipolis - Méditerranée - Inria - Institut National de Recherche en Informatique et en AutomatiqueCOMUE UCA - COMUE Université Côte d'Azur (2015-2019)Singh, Vikas VikramVikas VikramSinghIIT Delhi - Indian Institute of Technology DelhiStochastic Coalitional Better-Response Dynamics for Finite Games with Application to Network Formation GamesHAL CCSD2019Strong Nash equilibriumCoalitional better-responseStochastic stabilityNetwork formation gamesStrongly stable networks[INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT][INFO.INFO-SI] Computer Science [cs]/Social and Information Networks [cs.SI][INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI][MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC]Avrachenkov, KonstantinAltman, EitanAvrachenkov, KonstantinDe Pellegrini, FrancescoEl-Azouzi, RachidWang, Huijuan2020-10-09 15:03:042023-03-15 08:58:092020-10-09 16:44:16enBook sectionshttps://hal.inria.fr/hal-02372761/document10.1007/978-3-030-24455-2_10application/pdf1We 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.