American Institute of Mathematical Sciences

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

Network formation games with teams

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

Received  October 2015 Revised  March 2016 Published  October 2016

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.
Citation: Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & 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. 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, (2002), 113. 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. 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. [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. doi: 10.1145/872035.872088. [11] D. Foster and H. P. Young, Stochastic evolutionary game dynamics,, Theoretical Population Biology, 38 (1990), 219. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.2307/2951777. [22] B. Klaus, F. Klijn and M. Walzl, Stochastic stability for roommate markets,, Journal of Economic Theory, 145 (2010), 2218. doi: 10.1016/j.jet.2010.07.006. [23] J. Newton, Coalitional stochastic stability,, Games and Economic Behavior, 75 (2012), 842. 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. 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. 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. 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. 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. doi: 10.1109/CAMSAP.2009.5413303. [30] R. Sawa, Coalitional stochastic stability in games, networks and markets,, Games and Economic Behavior, 88 (2014), 90. doi: 10.1016/j.geb.2014.07.005. [31] H. P. Young, The evolution of conventions,, Econometrica, 61 (1993), 57. 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. 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, (2002), 113. 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. 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. [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. doi: 10.1145/872035.872088. [11] D. Foster and H. P. Young, Stochastic evolutionary game dynamics,, Theoretical Population Biology, 38 (1990), 219. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.2307/2951777. [22] B. Klaus, F. Klijn and M. Walzl, Stochastic stability for roommate markets,, Journal of Economic Theory, 145 (2010), 2218. doi: 10.1016/j.jet.2010.07.006. [23] J. Newton, Coalitional stochastic stability,, Games and Economic Behavior, 75 (2012), 842. 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. 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. 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. 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. 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. doi: 10.1109/CAMSAP.2009.5413303. [30] R. Sawa, Coalitional stochastic stability in games, networks and markets,, Games and Economic Behavior, 88 (2014), 90. doi: 10.1016/j.geb.2014.07.005. [31] H. P. Young, The evolution of conventions,, Econometrica, 61 (1993), 57. doi: 10.2307/2951778.
 [1] Jianfeng Feng, Mariya Shcherbina, Brunello Tirozzi. Stability of the dynamics of an asymmetric neural network. Communications on Pure & Applied Analysis, 2009, 8 (2) : 655-671. doi: 10.3934/cpaa.2009.8.655 [2] Saul Mendoza-Palacios, Onésimo Hernández-Lerma. Stability of the replicator dynamics for games in metric spaces. Journal of Dynamics & Games, 2017, 4 (4) : 319-333. doi: 10.3934/jdg.2017017 [3] 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 [4] 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 [5] Mikko Salo. Stability for solutions of wave equations with $C^{1,1}$ coefficients. Inverse Problems & Imaging, 2007, 1 (3) : 537-556. doi: 10.3934/ipi.2007.1.537 [6] Tomás Caraballo, Leonid Shaikhet. Stability of delay evolution equations with stochastic perturbations. Communications on Pure & Applied Analysis, 2014, 13 (5) : 2095-2113. doi: 10.3934/cpaa.2014.13.2095 [7] 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 [8] Nicolas Fourrier, Irena Lasiecka. Regularity and stability of a wave equation with a strong damping and dynamic boundary conditions. Evolution Equations & Control Theory, 2013, 2 (4) : 631-667. doi: 10.3934/eect.2013.2.631 [9] Yaping Wu, Niannian Yan. Stability of traveling waves for autocatalytic reaction systems with strong decay. Discrete & Continuous Dynamical Systems - B, 2017, 22 (4) : 1601-1633. doi: 10.3934/dcdsb.2017033 [10] George Avalos. Strong stability of PDE semigroups via a generator resolvent criterion. Discrete & Continuous Dynamical Systems - S, 2008, 1 (2) : 207-218. doi: 10.3934/dcdss.2008.1.207 [11] Yacine Chitour, Frédéric Grognard, Georges Bastin. Equilibria and stability analysis of a branched metabolic network with feedback inhibition. Networks & Heterogeneous Media, 2006, 1 (1) : 219-239. doi: 10.3934/nhm.2006.1.219 [12] Bara Kim. Stability of a retrial queueing network with different classes of customers and restricted resource pooling. Journal of Industrial & Management Optimization, 2011, 7 (3) : 753-765. doi: 10.3934/jimo.2011.7.753 [13] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [14] Abdallah Ben Abdallah, Farhat Shel. Exponential stability of a general network of 1-d thermoelastic rods. Mathematical Control & Related Fields, 2012, 2 (1) : 1-16. doi: 10.3934/mcrf.2012.2.1 [15] Tomás Caraballo, José Real, T. Taniguchi. The exponential stability of neutral stochastic delay partial differential equations. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 295-313. doi: 10.3934/dcds.2007.18.295 [16] Boris P. Belinskiy, Peter Caithamer. Stochastic stability of some mechanical systems with a multiplicative white noise. Conference Publications, 2003, 2003 (Special) : 91-99. doi: 10.3934/proc.2003.2003.91 [17] Zhiping Chen, Youpan Han. Continuity and stability of two-stage stochastic programs with quadratic continuous recourse. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 197-209. doi: 10.3934/naco.2015.5.197 [18] Min Zhu, Panpan Ren, Junping Li. Exponential stability of solutions for retarded stochastic differential equations without dissipativity. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2923-2938. doi: 10.3934/dcdsb.2017157 [19] Alexandra Rodkina, Henri Schurz, Leonid Shaikhet. Almost sure stability of some stochastic dynamical systems with memory. Discrete & Continuous Dynamical Systems - A, 2008, 21 (2) : 571-593. doi: 10.3934/dcds.2008.21.571 [20] Henri Schurz. Moment attractivity, stability and contractivity exponents of stochastic dynamical systems. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 487-515. doi: 10.3934/dcds.2001.7.487

Impact Factor: