American Institute of Mathematical Sciences

Advanced
January  2020, 7(1): 37-64. doi: 10.3934/jdg.2020003

Game theoretical modelling of a dynamically evolving network Ⅱ: Target sequences of score 1

Chris Cannings 1, and  Mark Broom 2,,

1. 

School of Mathematics and Statistics, The University of Sheffield, Hounsfield Road, Sheffield, S3 7RH, UK
2. 

Department of Mathematics, City, University of London, Northampton Square, London EC1V 0HB, UK

* Corresponding author: Mark Broom

Received  December 2018 Revised  September 2019 Published  December 2019

In previous work we considered a model of a population where individuals have an optimum level of social interaction, governed by a graph representing social connections between the individuals, who formed or broke those links to achieve their target number of contacts. In the original work an improvement in the number of links was carried out by breaking or joining to a randomly selected individual. In the most recent work, however, these actions were often not random, but chosen strategically, and this led to significant complications. One of these was that in any state, multiple individuals might wish to change their number of links. In this paper we consider a systematic analysis of the structure of the simplest class of non-trivial cases, where in general only a single individual has reason to make a change, and prove some general results. We then consider in detail an example game, and introduce a method of analysis for our chosen class based upon cycles on a graph. We see that whilst we can gain significant insight into the general structure of the state space, the analysis for specific games remains difficult.

Keywords: Degree preferences, graphic sequences, Nash equilibrium, Markov process, stationary distribution.
Mathematics Subject Classification: Primary: 05C57, 91A43; Secondary: 05C81.
Citation: Chris Cannings, Mark Broom. Game theoretical modelling of a dynamically evolving network Ⅱ: Target sequences of score 1. Journal of Dynamics & Games, 2020, 7 (1) : 37-64. doi: 10.3934/jdg.2020003
References:
[1]

B. Allen and M. A. Nowak, Games on graphs, EMS Surveys in Mathematical Sciences, 1 (2014), 113-151.  doi: 10.4171/EMSS/3.  Google Scholar

[2]

V. Bala and S. Goyal, A model of non-cooperative network formation, Econometrica, 68 (2000), 1181-1230.  doi: 10.1111/1468-0262.00155.  Google Scholar

[3]

M. Broom and C. Cannings, A dynamic network population model with strategic link formation governed by individual preferences, J. Theor. Biol., 335 (2013), 160-168.  doi: 10.1016/j.jtbi.2013.06.024.  Google Scholar

[4]

M. Broom and C. Cannings, Graphic deviation, Discrete Mathematics, 338 (2015), 701-711.  doi: 10.1016/j.disc.2014.12.011.  Google Scholar

[5]

M. Broom and C. Cannings, Game theoretical modelling of a dynamically evolving network Ⅰ: General target sequences, Journal of Dynamic Games, 4 (2017), 285-318.  doi: 10.3934/jdg.2017016.  Google Scholar

[6]

C. Capitanio, Sociability and response to video playback in adult male rhesus monkeys (macac mulatta), Primates, 43 (2002), 169-177.   Google Scholar

[7]

R. C. Connor, M. R. Helthaus and L. M. Barre, Superalliances of bottlenose dolphins, Nature, 397 (1999), 571-572.  doi: 10.1038/17501.  Google Scholar

[8]

P. I. M. Dunbar, Neocortex size as a constraint on group size in primates, J. Human Evoluion, 22 (1992), 469-493.  doi: 10.1016/0047-2484(92)90081-J.  Google Scholar

[9]

B. Dutta and M. O. Jackson, The stability and effeciency of directed communication networks, Rev. Econ. Design, 5 (2015), 251-272.   Google Scholar

[10]

C. S. Elton, Animal Ecology, Sidgwick & Jackson, London, 1927. Google Scholar

[11]

P. Erdos and P. T. Gallai, Grafok eloirt fokszamu pontokkal, Matematikai Lapo, 11 (1960), 264-274.   Google Scholar

[12]

S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph. Ⅰ, J. Soc. Indust. Appl. Math., 10 (1962), 496-506.  doi: 10.1137/0110037.  Google Scholar

[13]

W. Hässelbarth, Die Verzweightheit von Graphen, Comm. in Math. and Computer Chem. (MATCH), 16 (1984), 3-17.   Google Scholar

[14]

V. Havel, A remark on the existence of finite graphs, Časopis Pěst. Mat., 81 (1956), 477–480.  Google Scholar

[15]

M. O. Jackson, The stability and efficiency of economic and social networks, Networks and Groups, Springer, (2003). Google Scholar

[16]

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

[17]

M. O. Jackson, An overview of social networks and economic applications, Handbook of Social Economics, Elsevier, (2011), 512–585 Google Scholar

[18]

M. O. Jackson and A. Wolinsky, A strategic model of social and economic networks, J. Econ. Theory, 71 (1996), 44-74.  doi: 10.1006/jeth.1996.0108.  Google Scholar

[19]

R. Merris and T. Roby, The lattice of threshold graphs, J. Inequal. Pure and Appl. Math., 6 (2005), Art. 2, 21 pp.  Google Scholar

[20]

R. Noë, Biological markets: Partner choice as the driving force behind the evolution of cooperation, Economics in Nature. Social Dilemmas, Mate Choice and Biological Markets, (2001), 93–118. Google Scholar

[21]

R. Noë and P. Hammerstein, Biological markets: Supply and demand determine the effect of partner choice in cooperation, mutualism and mating, Behav. Ecol. Sociobio., 35 (1994), 1-11.   Google Scholar

[22]

J. M. Pacheco, A. Traulsen and M. A. Nowak, Active linking in evolutionary games, J. Theor. Biol., 243 (2006), 437-443.  doi: 10.1016/j.jtbi.2006.06.027.  Google Scholar

[23]

J. M. Pacheco, A. Traulsen and M. A. Nowak, Coevolution of strategy and structure in complex networks with dynamical linking, Phys. Rev. Lett., 97 (2006), 258103. doi: 10.1103/PhysRevLett.97.258103.  Google Scholar

[24]

J. Pepper, J. Mitani and D. Watts, General gregariousness and specific social preferences among wild chimpanzees, Int. J. Primatol., 20 (1999), 613-632.   Google Scholar

[25]

M. Perc and A. Szolnoki, Coevolutionarygames - A mini review, BioSystems, 99 (2010), 109-125.   Google Scholar

[26]

E. Ruch and I. Gutman, The branching extent of graphs, J. Combin. Inform. Systems Sci., 4 (1979), 285-295.   Google Scholar

[27]

L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. U.S.A., 39 (1979), 1095-1100.  doi: 10.1073/pnas.39.10.1953.  Google Scholar

[28]

A. M. Sibbald and R. J. Hooper, Sociability and willingness of individual sheep to move away from their companions in order to graze, Applied Animal Behaviour, 86 (2004), 51-62.  doi: 10.1016/j.applanim.2003.11.010.  Google Scholar

[29]

R. Southwell and C. Cannings, Some models of reproducing graphs: Ⅰ pure reproduction, Applied Mathematics, 1 (2010), 137-145.  doi: 10.4236/am.2010.13018.  Google Scholar

[30]

R. Southwell and C. Cannings, Some models of reproducing graphs. Ⅱ. Age capped reproduction, Applied Mathematics, 1 (2010), 251-259.   Google Scholar

[31]

R. Southwell and C. Cannings, Some models of reproducing graphs. Ⅲ. Game based reproduction, Applied Mathematics, 1 (2010), 335-343.  doi: 10.4236/am.2010.15044.  Google Scholar

[32]

B. Voelkl and C. Kasper, Social structure of primate interaction networks facilitates the emergence of cooperation, Biology Letters, 5 (2009), 462-464.  doi: 10.1098/rsbl.2009.0204.  Google Scholar

[33]

B. Voelkl and R. Noë, The influence of social structure on the propagation of social information in artificial primate groups: A graph-based simulation approach, J. Theor. Biol., 252 (2008), 77-86.  doi: 10.1016/j.jtbi.2008.02.002.  Google Scholar

[34]

J. Wiszniewski, C. Brown and L. M. Möller, Complex patterns of male alliance formation in dolphin social networks, Journal of Mammalogy, 93 (2012), 239-250.  doi: 10.1644/10-MAMM-A-366.1.  Google Scholar

show all references

References:
[1]

B. Allen and M. A. Nowak, Games on graphs, EMS Surveys in Mathematical Sciences, 1 (2014), 113-151.  doi: 10.4171/EMSS/3.  Google Scholar

[2]

V. Bala and S. Goyal, A model of non-cooperative network formation, Econometrica, 68 (2000), 1181-1230.  doi: 10.1111/1468-0262.00155.  Google Scholar

[3]

M. Broom and C. Cannings, A dynamic network population model with strategic link formation governed by individual preferences, J. Theor. Biol., 335 (2013), 160-168.  doi: 10.1016/j.jtbi.2013.06.024.  Google Scholar

[4]

M. Broom and C. Cannings, Graphic deviation, Discrete Mathematics, 338 (2015), 701-711.  doi: 10.1016/j.disc.2014.12.011.  Google Scholar

[5]

M. Broom and C. Cannings, Game theoretical modelling of a dynamically evolving network Ⅰ: General target sequences, Journal of Dynamic Games, 4 (2017), 285-318.  doi: 10.3934/jdg.2017016.  Google Scholar

[6]

C. Capitanio, Sociability and response to video playback in adult male rhesus monkeys (macac mulatta), Primates, 43 (2002), 169-177.   Google Scholar

[7]

R. C. Connor, M. R. Helthaus and L. M. Barre, Superalliances of bottlenose dolphins, Nature, 397 (1999), 571-572.  doi: 10.1038/17501.  Google Scholar

[8]

P. I. M. Dunbar, Neocortex size as a constraint on group size in primates, J. Human Evoluion, 22 (1992), 469-493.  doi: 10.1016/0047-2484(92)90081-J.  Google Scholar

[9]

B. Dutta and M. O. Jackson, The stability and effeciency of directed communication networks, Rev. Econ. Design, 5 (2015), 251-272.   Google Scholar

[10]

C. S. Elton, Animal Ecology, Sidgwick & Jackson, London, 1927. Google Scholar

[11]

P. Erdos and P. T. Gallai, Grafok eloirt fokszamu pontokkal, Matematikai Lapo, 11 (1960), 264-274.   Google Scholar

[12]

S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph. Ⅰ, J. Soc. Indust. Appl. Math., 10 (1962), 496-506.  doi: 10.1137/0110037.  Google Scholar

[13]

W. Hässelbarth, Die Verzweightheit von Graphen, Comm. in Math. and Computer Chem. (MATCH), 16 (1984), 3-17.   Google Scholar

[14]

V. Havel, A remark on the existence of finite graphs, Časopis Pěst. Mat., 81 (1956), 477–480.  Google Scholar

[15]

M. O. Jackson, The stability and efficiency of economic and social networks, Networks and Groups, Springer, (2003). Google Scholar

[16]

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

[17]

M. O. Jackson, An overview of social networks and economic applications, Handbook of Social Economics, Elsevier, (2011), 512–585 Google Scholar

[18]

M. O. Jackson and A. Wolinsky, A strategic model of social and economic networks, J. Econ. Theory, 71 (1996), 44-74.  doi: 10.1006/jeth.1996.0108.  Google Scholar

[19]

R. Merris and T. Roby, The lattice of threshold graphs, J. Inequal. Pure and Appl. Math., 6 (2005), Art. 2, 21 pp.  Google Scholar

[20]

R. Noë, Biological markets: Partner choice as the driving force behind the evolution of cooperation, Economics in Nature. Social Dilemmas, Mate Choice and Biological Markets, (2001), 93–118. Google Scholar

[21]

R. Noë and P. Hammerstein, Biological markets: Supply and demand determine the effect of partner choice in cooperation, mutualism and mating, Behav. Ecol. Sociobio., 35 (1994), 1-11.   Google Scholar

[22]

J. M. Pacheco, A. Traulsen and M. A. Nowak, Active linking in evolutionary games, J. Theor. Biol., 243 (2006), 437-443.  doi: 10.1016/j.jtbi.2006.06.027.  Google Scholar

[23]

J. M. Pacheco, A. Traulsen and M. A. Nowak, Coevolution of strategy and structure in complex networks with dynamical linking, Phys. Rev. Lett., 97 (2006), 258103. doi: 10.1103/PhysRevLett.97.258103.  Google Scholar

[24]

J. Pepper, J. Mitani and D. Watts, General gregariousness and specific social preferences among wild chimpanzees, Int. J. Primatol., 20 (1999), 613-632.   Google Scholar

[25]

M. Perc and A. Szolnoki, Coevolutionarygames - A mini review, BioSystems, 99 (2010), 109-125.   Google Scholar

[26]

E. Ruch and I. Gutman, The branching extent of graphs, J. Combin. Inform. Systems Sci., 4 (1979), 285-295.   Google Scholar

[27]

L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. U.S.A., 39 (1979), 1095-1100.  doi: 10.1073/pnas.39.10.1953.  Google Scholar

[28]

A. M. Sibbald and R. J. Hooper, Sociability and willingness of individual sheep to move away from their companions in order to graze, Applied Animal Behaviour, 86 (2004), 51-62.  doi: 10.1016/j.applanim.2003.11.010.  Google Scholar

[29]

R. Southwell and C. Cannings, Some models of reproducing graphs: Ⅰ pure reproduction, Applied Mathematics, 1 (2010), 137-145.  doi: 10.4236/am.2010.13018.  Google Scholar

[30]

R. Southwell and C. Cannings, Some models of reproducing graphs. Ⅱ. Age capped reproduction, Applied Mathematics, 1 (2010), 251-259.   Google Scholar

[31]

R. Southwell and C. Cannings, Some models of reproducing graphs. Ⅲ. Game based reproduction, Applied Mathematics, 1 (2010), 335-343.  doi: 10.4236/am.2010.15044.  Google Scholar

[32]

B. Voelkl and C. Kasper, Social structure of primate interaction networks facilitates the emergence of cooperation, Biology Letters, 5 (2009), 462-464.  doi: 10.1098/rsbl.2009.0204.  Google Scholar

[33]

B. Voelkl and R. Noë, The influence of social structure on the propagation of social information in artificial primate groups: A graph-based simulation approach, J. Theor. Biol., 252 (2008), 77-86.  doi: 10.1016/j.jtbi.2008.02.002.  Google Scholar

[34]

J. Wiszniewski, C. Brown and L. M. Möller, Complex patterns of male alliance formation in dolphin social networks, Journal of Mammalogy, 93 (2012), 239-250.  doi: 10.1644/10-MAMM-A-366.1.  Google Scholar

Figure 1.  The transition graph for the target $ 111 $ with six states. The vertex in deficit in each state is highlighted by a dot, and corresponding possible transitions are shown
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The two possible configurations for members of the minimal set with target 11111. The uppermost vertex is the one not attaining its target. There are 15 different cases of the configuration on the left, and 30 of the configuration on the right
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The Petersen triangle with associated sets. Vertices are joined if the set-intersection is empty
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  The transition graph for the graphs within the minimal set for target 11111. Each triangle is labelled internally with the edge fixed in its configurations. Note that each edge has a vertex at its mid-point. Each vertex is labelled $ a/ b $ with a unique state number $ a $, and the vertex $ b $ which is deficient in state $ a $. Three vertices 1, 2 and 32 are duplicated (shown as different shapes) to allow a planar representation
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The choice graph for the graphs within the minimal set for target 11111. Each vertex has an arrow which is the choice that the deficient vertex would make in that state. There is a stable cycle of length 30, specifically (36; 37; 38; 31; 29; 25; 18; 19; 20; 14; 11; 15; 22; 27; 40; 41; 32; 33; 34; 24; 16; 12; 7; 3; 1; 4; 9; 5; 2; 43; 36), which is shown in bold
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The choice graph for the minimal set for target 11111. Here we have a stable 24-cycle. (1; 4; 9; 5; 2; 6; 11; 14; 20; 21; 22; 27; 40; 41; 32; 23; 16; 17; 18; 13; 7; 3; 1)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Two intersecting 14-cycles with 9 common vertices
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Score 1 sequences generated from the graphic sequence 766543221. In each case we identify the set, one of $ S_{A} $, $ S_{B} $, $ S_{J} $ or $ S_{N} $ that each element is in, in the corresponding position to the target sequence
766543221 $ f_{1}=-1, f_{2}=-2, f_{3}=-1, f_{4}=0, $
$ \lambda=4, K=4, K'=4 $
866543221 $ i=1, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
666543221 $ i=1, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
776543221 $ i=2, 3, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
765543221 $ i=2, 3, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766643221 $ i=4, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
766443221$ ^{a} $ $ i=4, \lambda*=5 $ never AAAAAAAAA
766553221 $ i=5, \lambda*=5 $ for all but $ m=4, 5 $ down JJJJJBBBB
766533221 $ i=5, \lambda*=5 $ never JJJJBBBBB
766544221$ ^{b} $ $ i=6, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766542221 $ i=6, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
766543321 $ i=7, 8, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766543211 $ i=7, 8, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
766543222 $ i=9, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766543220 $ i=9, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
Table Options

Download as excel

766543221 $ f_{1}=-1, f_{2}=-2, f_{3}=-1, f_{4}=0, $
$ \lambda=4, K=4, K'=4 $
866543221 $ i=1, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
666543221 $ i=1, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
776543221 $ i=2, 3, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
765543221 $ i=2, 3, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766643221 $ i=4, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
766443221$ ^{a} $ $ i=4, \lambda*=5 $ never AAAAAAAAA
766553221 $ i=5, \lambda*=5 $ for all but $ m=4, 5 $ down JJJJJBBBB
766533221 $ i=5, \lambda*=5 $ never JJJJBBBBB
766544221$ ^{b} $ $ i=6, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766542221 $ i=6, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
766543321 $ i=7, 8, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766543211 $ i=7, 8, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
766543222 $ i=9, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766543220 $ i=9, \lambda*=5 $ for $ m=5 $ up JJJJNBBBB
Table 2.  Score 1 sequences generated from the graphic sequence 766444221. In each case we indentify the set, one of $ S_{A} $, $ S_{B} $, $ S_{J} $ or $ S_{N} $ that each element is in, in the corresponding position to the target sequence
766444221 $ f_{1}=-1, f_{2}=-2, f_{3}=-1, f_{4}=-2, $
$ \lambda=4, K=3, K'=0 $
866444221 $ i=1, \lambda*=5 $ never JJJAAABBB
666444221 $ i=1, \lambda*=5 $ never AAAAAAAAA
776444221 $ i=2, 3, \lambda*=5 $ never JJJAAABBB
765444221 $ i=2, 3, \lambda*=5 $ never AAAAAAAAA
766544221$ ^{b} $ $ i=4, 5, 6, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766443221$ ^{a} $ $ i=4, 5, 6, \lambda*=5 $ never AAAAAAAAA
766444321 $ i=7, 8, \lambda*=5 $ never AAAAAAAAA
766444211 $ i=7, 8, \lambda*=5 $ never JJJAAABBB
766444222 $ i=9, \lambda*=5 $ never AAAAAAAAA
766444220 $ i=9, \lambda*=5 $ never JJJAAABBB
Table Options

Download as excel

766444221 $ f_{1}=-1, f_{2}=-2, f_{3}=-1, f_{4}=-2, $
$ \lambda=4, K=3, K'=0 $
866444221 $ i=1, \lambda*=5 $ never JJJAAABBB
666444221 $ i=1, \lambda*=5 $ never AAAAAAAAA
776444221 $ i=2, 3, \lambda*=5 $ never JJJAAABBB
765444221 $ i=2, 3, \lambda*=5 $ never AAAAAAAAA
766544221$ ^{b} $ $ i=4, 5, 6, \lambda*=5 $ for $ m=5 $ up AAAAAAAAA
766443221$ ^{a} $ $ i=4, 5, 6, \lambda*=5 $ never AAAAAAAAA
766444321 $ i=7, 8, \lambda*=5 $ never AAAAAAAAA
766444211 $ i=7, 8, \lambda*=5 $ never JJJAAABBB
766444222 $ i=9, \lambda*=5 $ never AAAAAAAAA
766444220 $ i=9, \lambda*=5 $ never JJJAAABBB
Table 3.  Frequencies of stable cycles resulting from 2, 000 simulations starting from randomly generated initial choice graphs
Cycle-length 6 10 12 14 16 18 20 22 24 26 28 30
Frequency 358 436 735 319 96 29 17 7 3 0 0 0
Table Options

Download as excel

Cycle-length 6 10 12 14 16 18 20 22 24 26 28 30
Frequency 358 436 735 319 96 29 17 7 3 0 0 0
[1]

Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020386
[2]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

 Impact Factor: 

Tools

Metrics

  • PDF downloads (146)
  • HTML views (257)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences