Network formation games with teams

Konstantin  Avrachenkov; Giovanni  Neglia; Vikas Vikram  Singh

doi:10.3934/jdg.2016016

Article Contents

2016, Volume 3, Issue 4: 303-318. Doi: 10.3934/jdg.2016016

This issue Previous Article Next Article Competition with high number of agents and a major one

Network formation games with teams

1.
INRIA Sophia-Antipolis, 2004 route des Lucioles, 06902 Sophia-Antipolis

Received: September 30, 2015

Revised: February 29, 2016

Published: September 2016

Abstract Related Papers Cited by

Abstract

Network formation games have been proposed as a tool to explain the topological characteristics of existing networks. They assume that each node is an autonomous decision-maker, ignoring that in many cases different nodes are under the control of the same authority (e.g. an Autonomous System) and then they operate as a team. In this paper we introduce the concept of network formation games for teams of nodes and show how very different network structures can arise also for some simple games studied in the literature. Beside extending the usual definition of pairwise stable networks to this new setting, we define a more general concept of stability toward deviations from a specific set $\mathcal{C}$ of teams' coalitions ($\mathcal{C}$-stability). We study then a trembling-hand dynamics, where at each time a coalition of teams can create or sever links in order to reduce its cost, but it can also take wrong decisions with some small probability. We show that this stochastic dynamics selects $\mathcal{C}$-stable networks or networks from closed cycles in the long run as the error probability vanishes.

Keywords:

Mathematics Subject Classification: Primary: 91A25, 91A43, 91A06; Secondary: 93E15, 60J10.

Citation:

Related Papers

Cited by

References

[1]	E. Anshelevich, F. B. Shepherd and G. Wilfong, Strategic network formation through peering and service agreements, Games and Economic Behavior, 73 (2011), 17-38.doi: 10.1016/j.geb.2011.01.002.
[2]	K. Avrachenkov, J. Filar and M. Haviv, Singular perturbations of Markov chains and decision processes, in Handbook of Markov Decision Processes, 113-150, International Series in Operations Research and Management Science, 40, Kluwer Acad. Publ., Boston, MA, 2002.doi: 10.1007/978-1-4615-0805-2_4.
[3]	K. Avrachenkov, J. Filar and P. Howlett, Analytic Perturbation Theory and Its Applications, SIAM, 2013.doi: 10.1137/1.9781611973143.
[4]	L. Boncinelli and P. Pin, Efficiency and stability in a process of teams formation, 2014.
[5]	J. Corbo, S. Jain, M. Mitzenmacher and D. C. Parkes, An economically-principled generative model of AS graph connectivity, in Proceedings of NetEcon+IBC, 2007.
[6]	J. Corbo and D. Parkes, The price of selfish behavior in bilateral network formation, in Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, 2005, 99-107.doi: 10.1145/1073814.1073833.
[7]	G. Demange and M. Wooders (eds.), Group Formation in Economics: Networks, Clubs, and Coalitions, Cambridge University Press, 2005.doi: 10.1017/CBO9780511614385.
[8]	B. Dutta and M. O. Jackson (eds.), Networks and Groups: Models of Strategic Formation, Springer Berlin Heidelberg, 2003.doi: 10.1007/978-3-540-24790-6.
[9]	J. Elias, F. Martignon, K. Avrachenkov and G. Neglia, A game theoretic analysis of network design with socialy-aware users, Computer Networks, 55 (2011), 106-118.
[10]	A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou and S. Shenker, On a network creation game, in Proceedings of the twenty-second annual symposium on Principles of distributed computing, 2003, 347-351.doi: 10.1145/872035.872088.
[11]	D. Foster and H. P. Young, Stochastic evolutionary game dynamics, Theoretical Population Biology, 38 (1990), 219-232.doi: 10.1016/0040-5809(90)90011-J.
[12]	D. Fudenberg and L. A. Imhof, Imitation processes with small mutations, Journal of Economic Theory, 131 (2006), 251-262.doi: 10.1016/j.jet.2005.04.006.
[13]	D. Fudenberg, M. A. Nowak, C. Taylor and L. A. Imhof, Evolutionary game dynamics in finite populations with strong selection and weak mutations, Theoretical Population Biology, 70 (2006), 352-363.doi: 10.1016/j.tpb.2006.07.006.
[14]	D. Gale and L. S. Shapley, College admissions and the stability of marriage, The American Mathematical Monthly, 69 (1962), 9-15.doi: 10.2307/2312726.
[15]	S. Goyal, Connections: An Introduction to the Economics of Networks, Princeton University Press, 2007.
[16]	M. O. Jackson, Social and Economic Networks, Princeton University Press, 2008.
[17]	M. O. Jackson and A. van den Nouweland, Strongly stable networks, Games and Economic Behavior, 51 (2005), 420-444.doi: 10.1016/j.geb.2004.08.004.
[18]	M. O. Jackson and A. Watts, The evolution of social and economic networks, Journal of Economic Theory, 106 (2002), 265-295.doi: 10.1006/jeth.2001.2903.
[19]	M. O. Jackson and A. Wolinsky, A strategic model of social and economic networks, Journal of Economic Theory, 71 (1996), 44-74.doi: 10.1006/jeth.1996.0108.
[20]	R. Johari, S. Mannor and J. N. Tsitsiklis, A contract-based model for directed network formation, Games and Economic Behavior, 56 (2006), 201-224.doi: 10.1016/j.geb.2005.08.010.
[21]	M. Kandori, G. J. Mailath and R. Rob, Learning, mutation, and long run equilibria in games, Econometrica, 61 (1993), 29-56.doi: 10.2307/2951777.
[22]	B. Klaus, F. Klijn and M. Walzl, Stochastic stability for roommate markets, Journal of Economic Theory, 145 (2010), 2218-2240.doi: 10.1016/j.jet.2010.07.006.
[23]	J. Newton, Coalitional stochastic stability, Games and Economic Behavior, 75 (2012), 842-854.doi: 10.1016/j.geb.2012.02.014.
[24]	J. Newton, Recontracting and stochastic stability in cooperative games, Journal of Economic Theory, 147 (2012), 364-381.doi: 10.1016/j.jet.2011.11.007.
[25]	J. Newton and S. D. Angus, Coalitions, tipping points and the speed of evolution, Journal of Economic Theory, 157 (2015), 172-187.doi: 10.1016/j.jet.2015.01.003.
[26]	J. Newton and R. Sawa, A one-shot deviation principle for stability in matching problems, Journal of Economic Theory, 157 (2015), 1-27.doi: 10.1016/j.jet.2014.11.015.
[27]	A. Roth and M. Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, 1992.
[28]	W. Saad, Z. Han, T. Basar, M. Debbah and A. Hjorungnes, Network formation games among relay stations in next generation wireless networks, IEE Transactions on Communications, 59 (2011), 2528-2542.doi: 10.1109/TCOMM.2011.062311.100046.
[29]	W. Saad, A. Hjorungnes, Z. Han and T. Basar, Network formation games for wireless multi-hop networks in the presence of eavesdroppers, in 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2009, 1-4.doi: 10.1109/CAMSAP.2009.5413303.
[30]	R. Sawa, Coalitional stochastic stability in games, networks and markets, Games and Economic Behavior, 88 (2014), 90-111.doi: 10.1016/j.geb.2014.07.005.
[31]	H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84.doi: 10.2307/2951778.