Network formation games with teams

Previous Article
Competition with high number of agents and a major one
JDG Home
This Issue
Next Article

October 2016, 3(4): 303-318. doi: 10.3934/jdg.2016016

Network formation games with teams

Konstantin Avrachenkov ^1, , Giovanni Neglia ^1, and Vikas Vikram Singh ^1,

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

Received October 2015 Revised March 2016 Published October 2016

Abstract
Related Papers

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: teams, Network formation games, strong stability, $\mathcal{C}$-stability, stochastic stability..

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

Citation: Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics and Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016

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.

show all references

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.

[1]	Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics and Games, 2021 doi: 10.3934/jdg.2021021
[2]	Aradhana Narang, A. J. Shaiju. Neighborhood strong superiority and evolutionary stability of polymorphic profiles in asymmetric games. Journal of Dynamics and Games, 2022 doi: 10.3934/jdg.2022012
[3]	Ryoji Sawa. Stochastic stability in the large population and small mutation limits for coordination games. Journal of Dynamics and Games, 2021 doi: 10.3934/jdg.2021015
[4]	Jianfeng Feng, Mariya Shcherbina, Brunello Tirozzi. Stability of the dynamics of an asymmetric neural network. Communications on Pure and Applied Analysis, 2009, 8 (2) : 655-671. doi: 10.3934/cpaa.2009.8.655
[5]	Karim El Mufti, Rania Yahia. Polynomial stability in viscoelastic network of strings. Discrete and Continuous Dynamical Systems - S, 2022, 15 (6) : 1421-1438. doi: 10.3934/dcdss.2022073
[6]	Yiqiu Mao, Dongming Yan, ChunHsien Lu. Dynamic transitions and stability for the acetabularia whorl formation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (11) : 5989-6004. doi: 10.3934/dcdsb.2019117
[7]	Saul Mendoza-Palacios, Onésimo Hernández-Lerma. Stability of the replicator dynamics for games in metric spaces. Journal of Dynamics and Games, 2017, 4 (4) : 319-333. doi: 10.3934/jdg.2017017
[8]	Miguel A. Dumett, Roberto Cominetti. On the stability of an adaptive learning dynamics in traffic games. Journal of Dynamics and Games, 2018, 5 (4) : 265-282. doi: 10.3934/jdg.2018017
[9]	Ndolane Sene. Fractional input stability and its application to neural network. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 853-865. doi: 10.3934/dcdss.2020049
[10]	Ying Sue Huang, Chai Wah Wu. Stability of cellular neural network with small delays. Conference Publications, 2005, 2005 (Special) : 420-426. doi: 10.3934/proc.2005.2005.420
[11]	Mikko Salo. Stability for solutions of wave equations with $C^{1,1}$ coefficients. Inverse Problems and Imaging, 2007, 1 (3) : 537-556. doi: 10.3934/ipi.2007.1.537
[12]	Yuanyuan Huang, Yiping Hao, Min Wang, Wen Zhou, Zhijun Wu. Optimality and stability of symmetric evolutionary games with applications in genetic selection. Mathematical Biosciences & Engineering, 2015, 12 (3) : 503-523. doi: 10.3934/mbe.2015.12.503
[13]	Jewaidu Rilwan, Poom Kumam, Onésimo Hernández-Lerma. Stability of international pollution control games: A potential game approach. Journal of Dynamics and Games, 2022, 9 (2) : 191-202. doi: 10.3934/jdg.2022003
[14]	Nicolas Fourrier, Irena Lasiecka. Regularity and stability of a wave equation with a strong damping and dynamic boundary conditions. Evolution Equations and Control Theory, 2013, 2 (4) : 631-667. doi: 10.3934/eect.2013.2.631
[15]	Yaping Wu, Niannian Yan. Stability of traveling waves for autocatalytic reaction systems with strong decay. Discrete and Continuous Dynamical Systems - B, 2017, 22 (4) : 1601-1633. doi: 10.3934/dcdsb.2017033
[16]	George Avalos. Strong stability of PDE semigroups via a generator resolvent criterion. Discrete and Continuous Dynamical Systems - S, 2008, 1 (2) : 207-218. doi: 10.3934/dcdss.2008.1.207
[17]	Agissilaos G. Athanassoulis, Gerassimos A. Athanassoulis, Mariya Ptashnyk, Themistoklis Sapsis. Strong solutions for the Alber equation and stability of unidirectional wave spectra. Kinetic and Related Models, 2020, 13 (4) : 703-737. doi: 10.3934/krm.2020024
[18]	Tomás Caraballo, Leonid Shaikhet. Stability of delay evolution equations with stochastic perturbations. Communications on Pure and Applied Analysis, 2014, 13 (5) : 2095-2113. doi: 10.3934/cpaa.2014.13.2095
[19]	Miljana Jovanović, Vuk Vujović. Stability of stochastic heroin model with two distributed delays. Discrete and Continuous Dynamical Systems - B, 2020, 25 (7) : 2407-2432. doi: 10.3934/dcdsb.2020016
[20]	K Najarian. On stochastic stability of dynamic neural models in presence of noise. Conference Publications, 2003, 2003 (Special) : 656-663. doi: 10.3934/proc.2003.2003.656

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Konstantin Avrachenkov Giovanni Neglia Vikas Vikram Singh
on Google Scholar
Konstantin Avrachenkov Giovanni Neglia Vikas Vikram Singh

[Back to Top]