Geodesic
Stochastic coalitional better-response dynamics and stable equilibrium
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 8 (2016) no. 1, pp. 4-26

Voir la notice de l'article provenant de la source Math-Net.Ru

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 строго benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a $\mathcal{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 $\mathcal{K}$-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar statement holds for strict $\mathcal{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.
Keywords: strong Nash equilibrium, coalitional better-response, stochastic stability, network formation games, strongly stable networks. 
@article{MGTA_2016_8_1_a1,
     author = {Konstantin Avrachenkov and Vikas Vikram Singh},
     title = {Stochastic coalitional better-response dynamics and stable equilibrium},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {4--26},
     publisher = {mathdoc},
     volume = {8},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2016_8_1_a1/}
}
TY  - JOUR
AU  - Konstantin Avrachenkov
AU  - Vikas Vikram Singh
TI  - Stochastic coalitional better-response dynamics and stable equilibrium
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2016
SP  - 4
EP  - 26
VL  - 8
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2016_8_1_a1/
LA  - ru
ID  - MGTA_2016_8_1_a1
ER  - 
%0 Journal Article
%A Konstantin Avrachenkov
%A Vikas Vikram Singh
%T Stochastic coalitional better-response dynamics and stable equilibrium
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2016
%P 4-26
%V 8
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2016_8_1_a1/
%G ru
%F MGTA_2016_8_1_a1
Konstantin Avrachenkov; Vikas Vikram Singh. Stochastic coalitional better-response dynamics and stable equilibrium. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 8 (2016) no. 1, pp. 4-26. http://geodesic.mathdoc.fr/item/MGTA_2016_8_1_a1/