American Institute of Mathematical Sciences

Advanced
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

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 & 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.  Google Scholar

[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.  Google Scholar

[3]

K. Avrachenkov, J. Filar and P. Howlett, Analytic Perturbation Theory and Its Applications, SIAM, 2013. doi: 10.1137/1.9781611973143.  Google Scholar

[4]

L. Boncinelli and P. Pin, Efficiency and stability in a process of teams formation,, 2014., ().   Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7]

G. Demange and M. Wooders (eds.), Group Formation in Economics: Networks, Clubs, and Coalitions, Cambridge University Press, 2005. doi: 10.1017/CBO9780511614385.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

S. Goyal, Connections: An Introduction to the Economics of Networks, Princeton University Press, 2007.  Google Scholar

[16]

M. O. Jackson, Social and Economic Networks, Princeton University Press, 2008.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

J. Newton, Coalitional stochastic stability, Games and Economic Behavior, 75 (2012), 842-854. doi: 10.1016/j.geb.2012.02.014.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

A. Roth and M. Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, 1992. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[31]

H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84. doi: 10.2307/2951778.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[3]

K. Avrachenkov, J. Filar and P. Howlett, Analytic Perturbation Theory and Its Applications, SIAM, 2013. doi: 10.1137/1.9781611973143.  Google Scholar

[4]

L. Boncinelli and P. Pin, Efficiency and stability in a process of teams formation,, 2014., ().   Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7]

G. Demange and M. Wooders (eds.), Group Formation in Economics: Networks, Clubs, and Coalitions, Cambridge University Press, 2005. doi: 10.1017/CBO9780511614385.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

S. Goyal, Connections: An Introduction to the Economics of Networks, Princeton University Press, 2007.  Google Scholar

[16]

M. O. Jackson, Social and Economic Networks, Princeton University Press, 2008.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

J. Newton, Coalitional stochastic stability, Games and Economic Behavior, 75 (2012), 842-854. doi: 10.1016/j.geb.2012.02.014.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

A. Roth and M. Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, 1992. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[31]

H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84. doi: 10.2307/2951778.  Google Scholar

[1]

Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021021
[2]

Ryoji Sawa. Stochastic stability in the large population and small mutation limits for coordination games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021015
[3]

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
[4]

Yiqiu Mao, Dongming Yan, ChunHsien Lu. Dynamic transitions and stability for the acetabularia whorl formation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 5989-6004. doi: 10.3934/dcdsb.2019117
[5]

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
[6]

Miguel A. Dumett, Roberto Cominetti. On the stability of an adaptive learning dynamics in traffic games. Journal of Dynamics & Games, 2018, 5 (4) : 265-282. doi: 10.3934/jdg.2018017
[7]

Ndolane Sene. Fractional input stability and its application to neural network. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 853-865. doi: 10.3934/dcdss.2020049
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

Agissilaos G. Athanassoulis, Gerassimos A. Athanassoulis, Mariya Ptashnyk, Themistoklis Sapsis. Strong solutions for the Alber equation and stability of unidirectional wave spectra. Kinetic & Related Models, 2020, 13 (4) : 703-737. doi: 10.3934/krm.2020024
[15]

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
[16]

Miljana Jovanović, Vuk Vujović. Stability of stochastic heroin model with two distributed delays. Discrete & Continuous Dynamical Systems - B, 2020, 25 (7) : 2407-2432. doi: 10.3934/dcdsb.2020016
[17]

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
[18]

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
[19]

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
[20]

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

 Impact Factor: 

Tools

Metrics

  • PDF downloads (126)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy