Stochastic coalitional better-response dynamics and stable equilibrium

Konstantin Avrachenkov ; Vikas Vikram Singh

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 8 (2016) no. 1, pp. 4-26.

Résumé

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.

Détail

Keywords: strong Nash equilibrium, coalitional better-response, stochastic stability, network formation games, strongly stable networks.

Bibliographie

[1] Aumann R. J., “Acceptable points in general cooperative $n$-person games”, Contribution to the theory of game IV, Annals of Mathematical Study, 40, eds. R. D. Luce, A. W. Tucker, 1959, 287–324 | MR | Zbl

[2] Avrachenkov K., Filar J., Haviv M., “Singular perturbations of Markov chains and decision processes”, Handbook of Markov Decision Processes, International Series in Operations Research and Management Science, Springer, 2002 | MR | Zbl

[3] Avrachenkov K., Filar J., Howlett P., Analytic perturbation theory and its applications, SIAM, 2013 | MR | Zbl

[4] Avrachenkov K., Neglia G., Singh V. V., “Network formation games with teams”, Journal of Dynamics and Games (to appear)

[5] Demange G., Wooders M. (eds.), Group Formation in Economics: Networks, Clubs, and Coalitions, Cambridge University Press, 2005

[6] Dutta B., Jackson M. O. (eds.), Networks and Groups: Models of Strategic Formation, Springer, Berlin–Heidelberg, 2003

[7] Dutta B., Mutuswami S., “Stable networks”, Journal of Economic Theory, 76 (1997), 322–344 | DOI | MR | Zbl

[8] Foster D., Young H. P., “Stochastic evolutionary game dynamics”, Theoretical Population Biology, 38:2 (1990), 219–232 | DOI | MR | Zbl

[9] Fudenberg D., Imhof L. A., “Imitation processes with small mutations”, Journal of Economic Theory, 131 (2006), 251–262 | DOI | MR | Zbl

[10] Fudenberg D., Nowak M. A., Taylor C., Imhof L. A., “Evolutionary game dynamics in finite populations with strong selection and weak mutation”, Theoretical Population Biology, 70 (2006), 352–363 | DOI | Zbl

[11] Gale D., Shapley L. S., “College admissions and the stability of marriage”, The Americal Mathematical Monthly, 69:1 (1962), 9–15 | DOI | MR | Zbl

[12] Harsanyi J. C., Selten R., A general theory of equilibrium selection in games, MIT Press, 1988 | MR | Zbl

[13] Jackson M. O., Social and Economic Networks, Princeton University Press, 2010 | MR | Zbl

[14] Jackson M. O., van den Nouweland A., “Strongly stable networks”, Games and Economic Behavior, 51:2 (2005), 420–444 | DOI | MR | Zbl

[15] Jackson M. O., Watts A., “The evolution of social and economic networks”, Journal of Economic Theory, 106:2 (2002), 265–295 | DOI | MR | Zbl

[16] Jackson M. O., Watts A., “On the formation of interaction networks in social coordination games”, Games and Economic Behavior, 41 (2002), 265–291 | DOI | MR | Zbl

[17] Jackson M. O., Wolinsky A., “A strategic model of social and economic networks”, Journal of Economic Theory, 71:1 (1996), 44–74 | DOI | MR | Zbl

[18] Kandori M., Mailath G. J., Rob R., “Learning, mutation, and long run equilibria in games”, Econometrica, 61:1 (1993), 29–56 | DOI | MR | Zbl

[19] Kemeny J. G., Snel J. L., Finite Markov Chains, Springer-Verlag, 1976 | MR | Zbl

[20] Klaus B., Klijn F., Walzl M., “Stochastic stability for roommate markets”, Journal of Economic Theory, 145:6 (2010), 2218–2240 | DOI | MR | Zbl

[21] Newton J., “Coalitional stochastic stability”, Games and Economic Behavior, 75:2 (2012), 842–854 | DOI | MR | Zbl

[22] Newton J., “Recontracting and stochastic stability in cooperative games”, Journal of Economic Theory, 147 (2012), 364–381 | DOI | MR | Zbl

[23] Newton J., Angus S. D., “Coalitions, tipping points and the speed of evolution”, Journal of Economic Theory, 157 (2015), 172–187 | DOI | MR | Zbl

[24] Newton J., Sawa R., “A one-shot deviation principle for stability in matching problems”, Journal of Economic Theory, 157 (2015), 1–27 | DOI | MR | Zbl

[25] Roth A., Sotomayor M., Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, 1992 | MR | Zbl

[26] Sawa R., “Coalitional stochastic stability in games, networks and markets”, Games and Economic Behavior, 88 (2014), 90–111 | DOI | MR | Zbl

[27] Young H. P., “The evolution of conventions”, Econometrica, 61:1 (1993), 57–84 | DOI | MR | Zbl