\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Game theoretical modelling of a dynamically evolving network Ⅰ: General target sequences

  • * Corresponding author: Mark Broom

    * Corresponding author: Mark Broom 
Abstract Full Text(HTML) Figure(2) / Table(8) Related Papers Cited by
  • Animal (and human) populations contain a finite number of individuals with social and geographical relationships which evolve over time, at least in part dependent upon the actions of members of the population. These actions are often not random, but chosen strategically. In this paper we introduce a game-theoretical model of a population where the individuals have an optimal level of social engagement, and form or break social relationships strategically to obtain the correct level. This builds on previous work where individuals tried to optimise their number of connections by forming or breaking random links; the difference being that here we introduce a truly game-theoretic version where they can choose which specific links to form/break. This is more realistic and makes a significant difference to the model, one consequence of which is that the analysis is much more complicated. We prove some general results and then consider a single example in depth.

    Mathematics Subject Classification: Primary: 05C57, 91A43; Secondary: 05C81.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  1A: Possible sequences of set membership. 1B: Schematic of the transition graph for the minimal graphs for target $43210$. For each graph, the top symbol represents the vertex with target 2, which is always a neutral vertex. The vertices with targets 0, 1, 3, 4 are represented by the symbols in the bottom left, bottom right, middle right and middle left positions, respectively. Each graph contains a specific set of links between the symbols, and the corresponding breaker or joiner status is given by the appropriate symbol. Possible transitions are shown by the arrows between the graphs

    Figure 2.  The transitions starting from matrices $4$ and $8$ on the $5$-cube. The indices of the vertices and of the edges have two numbers, corresponding to the matrix reached from matrix $4$ and $8$ respectively. For example matrices 22 can be reached from matrix 4 by 16 then 2 (see Table 5). From 22 one can reach 18, 23 and 54, and 22 can be reached from 6, 20 and 30. The possible transitions from 26 are 18, 23 and 58 and can be reached from 10, 24 and 30. Stable matrices are highlighted. 2A: cost=0, 2B: cost=0.1.

    Table 1.  The set membership of vertices for targets with $n=3$ and $n=4$, and number of graphs in the minimal set. The omitted sequences are all duals of those included.

    TargetSetsMin. scoreNumber of states
    2 2 2d d d01
    2 2 1b b c13
    2 2 0b b c24
    2 1 1d d d01
    2 1 0b d c12
    1 1 1a a a16
    3 3 3 3d d d d01
    3 3 3 2b b b c14
    3 3 3 1b b b c27
    3 3 3 0b b b c38
    3 3 2 2d d d d01
    3 3 2 1b b d c13
    3 3 2 0b b d c24
    3 3 1 1b b c c29
    3 3 1 0b b c c312
    3 3 0 0b b c c416
    3 2 2 2b a a a19
    3 2 2 1d d d d01
    3 2 2 0b d d c12
    3 2 1 1b b c c15
    3 2 1 0b b c c28
    3 1 1 1d d d d01
    2 2 2 2d d d d01
    2 2 2 1a a a a113
    2 2 1 1d d d d01
     | Show Table
    DownLoad: CSV

    Table 2.  The stationary distributions over the eight graphs $G_{1}-G_{8}$ for the 64 matrices denoted by 0-63

    vector codesofmatrices
    (2, 3, 1, 4, 0, 0, 0, 0) 08162432404856
    (0, 0, 0, 0, 4, 1, 3, 2)01234567
    (0, 0, 0, 0, 4, 3, 1, 2)89101112131415
    (2, 1, 3, 4, 0, 0, 0, 0)412202836445260
    (3, 3, 0, 3, 1, 1, 3, 2)17
    (4, 3, 2, 2, 2, 2, 3, 4)18
    (6, 3, 0, 0, 4, 4, 9, 8)1923
    (6, 3, 3, 6, 2, 2, 6, 4)21
    (6, 3, 6, 6, 2, 2, 3, 4)22
    (1, 1, 0, 1, 1, 1, 1, 1)25
    (4, 3, 2, 2, 6, 6, 3, 6)26
    (2, 1, 0, 0, 4, 4, 3, 4)2731
    (2, 1, 1, 2, 2, 2, 2, 2)29
    (2, 1, 2, 2, 2, 2, 1, 2)30
    (1, 2, 0, 2, 2, 0, 2, 1)33
    (2, 3, 1, 1, 3, 0, 3, 3)34
    (1, 2, 0, 0, 4, 0, 4, 3)3539
    (1, 1, 1, 2, 2, 0, 2, 1)37
    (1, 1, 1, 1, 1, 0, 1, 1)38
    (1, 2, 0, 2, 2, 1, 1, 1)41
    (4, 6, 2, 2, 6, 3, 3, 6)42
    (1, 2, 0, 0, 4, 2, 2, 3)4347
    (1, 1, 1, 2, 2, 1, 1, 1)45
    (2, 2, 2, 2, 2, 1, 1, 2)46
    (3, 4, 0, 4, 0, 0, 2, 1)4957
    (8, 9, 4, 4, 0, 0, 3, 6)5058
    (1, 1, 0, 0, 0, 0, 1, 1)51555963
    (3, 2, 2, 4, 0, 0, 2, 1)5361
    (4, 3, 4, 4, 0, 0, 1, 2)5462
     | Show Table
    DownLoad: CSV

    Table 3.  Possible moves and outcomes for matrix 5. The first column gives the possible stationary distribution switched to, the other columns the corresponding costs for each vertex. The important cost (underlined) is that to the vertex that can make the switch. A switch can occur in the three cases highlighted by *s.

    index $c_4$ $c_3$ $c_1$ $c_0$
    $5$ $.3$ $.5$ $0$ $1.2$
    $4^L$ $1.2$ $0$ $\underline{.3}$ $.5$
    $4^R$ $.3$ $.5$ $\underline{0}$ $1.2$
    $7$ $.3$ $.5$ $\underline{0}$ $1.2$
    $1$ $\underline{.3}$ $.5$ $0$ $1.2$
    $13$ $.5$ $.3$ $0$ $\underline{1.2}$
    $21$ $.75$*$\underline{.3125}$* $.28125$ $.65625$
    $37$ $.7$*$\underline{.3}$* $.2$ $.8$
    $6$ $.3$ $.5$ $\underline{0}$ $1.2$
    $53$ $.929$*$\underline{.214}$* $.357$ $.5$
     | Show Table
    DownLoad: CSV

    Table 4.  The costs for each of the individuals $t_{0}-t_{4}$, where the cost for $t_{i}$ is denoted by $c_{i}$

    code c4 c3 c1 c0
    0L 1.200000 0.000000 0.500000 0.300000
    0R 0.30000 0.500000 0.000000 1.200000
    1 0.300000 0.500000 0.000000 1.200000
    2 0.300000 0.500000 0.000000 1.200000
    3 0.300000 0.500000 0.000000 1.200000
    4L 1.200000 0.000000 0.300000 0.500000
    4R 0.300000 0.500000 0.00000 1.200000
    5 0.300000 0.500000 0.000000 1.200000
    6 0.300000 0.500000 0.000000 1.200000
    7 0.300000 0.500000 0.000000 1.200000
    8L 1.200000 0.000000 0.500000 0.300000
    8R 0.500000 0.300000 0.000000 1.200000
    9 0.500000 0.300000 0.000000 1.200000
    10 0.500000 0.300000 0.000000 1.200000
    11 0.500000 0.300000 0.000000 1.200000
    12L 1.200000 0.000000 0.300000 0.500000
    12R 0.500000 0.300000 0.000000 1.200000
    13 0.500000 0.300000 0.000000 1.200000
    14 0.500000 0.300000 0.000000 1.200000
    15 0.500000 0.300000 0.000000 1.200000
    16 1.200000 0.000000 0.500000 0.300000
    17 0.750000 0.312500 0.375000 0.562500
    18 0.681818 0.318182 0.318182 0.681818
    19 0.441176 0.500000 0.264706 0.794118
    20 1.200000 0.000000 0.300000 0.500000
    21 0.750000 0.312500 0.281250 0.656250
    22 0.843750 0.218750 0.281250 0.656250
    23 0.441176 0.500000 0.264706 0.794118
    24 1.200000 0.000000 0.500000 0.300000
    25 0.714286 0.285714 0.285714 0.714286
    26 0.656250 0.281250 0.218750 0.843750
    27 0.500000 0.388889 0.166667 0.944444
    28 1.200000 0.000000 0.300000 0.500000
    29 0.714286 0.285714 0.214286 0.785714
    30 0.785714 0.214286 0.214286 0.785714
    31 0.500000 0.388889 0.166667 0.944444
    32 1.200000 0.000000 0.500000 0.300000
    33 0.700000 0.300000 0.300000 0.700000
    34 0.562500 0.375000 0.312500 0.750000
    35 0.357143 0.500000 0.214286 0.928571
    36 1.200000 0.000000 0.300000 0.500000
    37 0.700000 0.300000 0.200000 0.800000
    38 0.714286 0.285714 0.285714 0.714286
    39 0.357143 0.500000 0.214286 0.928571
    40 1.200000 0.000000 0.500000 0.300000
    41 0.800000 0.200000 0.300000 0.700000
    42 0.656250 0.281250 0.312500 0.750000
    43 0.500000 0.357143 0.214286 0.928571
    44 1.200000 0.000000 0.300000 0.500000
    45 0.800000 0.200000 0.200000 0.800000
    46 0.785714 0.214286 0.285714 0.714286
    47 0.500000 0.357143 0.214286 0.928571
    48 1.200000 0.000000 0.500000 0.300000
    49 0.928571 0.214286 0.500000 0.357143
    50 0.794118 0.264706 0.500000 0.441176
    51 0.500000 0.500000 0.500000 0.500000
    52 1.200000 0.000000 0.300000 0.500000
    53 0.928571 0.214286 0.357143 0.500000
    54 0.944444 0.166667 0.388889 0.500000
    55 0.500000 0.500000 0.500000 0.500000
    56 1.200000 0.000000 0.500000 0.300000
    57 0.928571 0.214286 0.500000 0.357143
    58 0.794118 0.264706 0.500000 0.441176
    59 0.500000 0.500000 0.500000 0.500000
    60 1.200000 0.000000 0.300000 0.500000
    61 0.928571 0.214286 0.357143 0.500000
    62 0.944444 0.166667 0.388889 0.500000
    63 0.500000 0.500000 0.500000 0.500000
     | Show Table
    DownLoad: CSV

    Table 5.  The optimal moves from matrices 0 to 31 (first nine columns) and matrices 32-63 (final nine columns) for cases 1a and 1b (results are identical for the two cases). The first column indicates the starting matrix, the next six the moves from the six graphs where changes can be made (listed in increasing numerical order), and the last two columns possible moves for $t_{4}$ and $t_{0}$ when both changes are allowed. We note that only one change is possible at each point, and if making no change is optimal, we simply write the starting matrix index.

    012001632348323334323232323532
    111111733149333335333349333333
    222221834250343534343450343318
    333333333353535353535353535
    456442036752363738363636363936
    555552137553373737373753373737
    666662238654383938343854383722
    777777777393937393939393939
    89108824401156404142404040404340
    999992541957414143414141414141
    101010101026421058424342424258424142
    111111111111111111434343434343114343
    121314121228441560444546444444444744
    131313131329451361454545454545454545
    141414141430461462464746424662464546
    151515151515151515474745474747154747
    161718161616161916484848484848484848
    171719171717491833494949494949494949
    181918181818501818505050505050505050
    191919191919191919515151515151515151
    202122202020202320525252525252525252
    212123212121532137535253535353535353
    222322182222542222545452505454545354
    232323232323232323555453555555555255
    242526242424242724565656565656565656
    252527251725572641575757575741575757
    262726261826582626585858585858585858
    272727271911272743595959595943275911
    282930282828283128606060606060606060
    292931292129612945616061616145616161
    303130262230623030626260586262626162
    313131312315313147636261636347316015
     | Show Table
    DownLoad: CSV

    Table 6.  The optimal moves from matrices 0 to 31 (first nine columns) and matrices 32-63 (final nine columns) for cases 2a and 2b (results are identical for the two cases). The first column indicates the starting matrix, the next six the moves from the six graphs where changes can be made (listed in increasing numerical order), and the last two columns possible moves for $t_{4}$ and $t_{0}$ when two changes are allowed

    01248163234832333436404803516
    103591733249333335374149333333
    2306101834150343534344250343318
    321711193505135353539435133519
    456012203675236373832445243920
    5471132137653373737334553373737
    6742142238554383938344654383722
    765315233945539393735475573923
    89101202440115640414244325684324
    981113125411057414143453341414141
    101181422642958424342423458424126
    111091531111811434343473543114343
    1213148428441560444546403660124728
    1312159529451461454545413745454545
    14151210630461362464746423862464530
    15141311715151215474745433947154747
    1617182024048193248495052563216510
    171719211717491833494851535749495049
    181918181818501818505148505850504950
    1919192319351193551504955593519483
    2021221628452233652525248603620524
    212123172121532237535253496153535353
    222322182222542122545452506254545354
    2323231923755233955545351633923527
    2425262816856274056575860484024598
    252527291725572641575659614941575857
    262726261826582642585956585058585758
    272727311911272743595857635143275611
    282930242012603144606060565244286012
    292931252129613045616061575345616161
    303130262230622946626260585462626162
    313131272315313147636261595547316015
     | Show Table
    DownLoad: CSV

    Table 7.  The possible PNEs for model $1a$ for various costs of changing. For zero cost the PNEs are those in the bottom row. As the cost increases there are critical points when additional matrices become PNEs, until at the highest threshold of 0.5, all 63 matrices are PNEs.

    FeeNewPNEs
    .5048**
    .312****
    .28125624***
    .2153240*
    .181818216***
    .1619322226***
    .1517862538***
    .15032627315462*
    .142857555963**
    .129464293046**
    .1102941734***
    .19133644*
    .0982142142***
    .0857141428333741
    .05714343475361*
    .05346718****
    .018751020***
    .0142863957***
    0371115*
    19233545*
    48495051*
    52565860*
     | Show Table
    DownLoad: CSV

    Table 8.  The space of PNEs. For any point the PNEs are all those included below and to the left of that point. Set $S_1=\{8, 9, 10, 11, 12, 13, 14, 15, 20, 32, 36, 44, 52, 60\}$ and $S_2=\{0, 1, 2, 3, 4, 5, 6, 7, 16, 24, 28, 40, 48, 56\}$.

    $t_{04} \backslash t_{13}$ $.2$ $.214$ $.281$ $.285$ $.300$ $.3125$ $.318$ $.375$ $.388$ $.5$
    $1.2$**** $S_1$**** $S_2$
    .9414********(27, 31, 54, 62)*
    ********* $[.7\dot{2}, .3\dot{7}]]$*
    .9285*********(35, 39, 49, 57)
    ********** $[.357, .643]$
    .8437**(22, 26)*******
    *** $[.75, .25]$*******
    .8(45)***(37, 41)*****
    * $[.8, .2]$*** $[.75, .25]$*****
    .794*********(19, 23, 50, 58)
    .**********$[.618, .382]$
    .785*(30)*(29, 46)******
    ** $[.786.214]$* $[.75, .25]$******
    .75*****(21, 42)*(17, 34)**
    ****** $[.703, .297]$* $[.65\dot{6}, .34\dot{3}]$**
    .714***(25, 38)******
    **** $[.714, .286]$******
    .7****(33)*****
    *****$[.7, .3]$*****
    .68******(18)***
    ******* $[.682, .318]$***
    .5*********(51, 55, 59, 63)
    ********** $[.5, .5]$
     | Show Table
    DownLoad: CSV
  • [1] B. Allen and M. A. Nowak, Games on graphs, EMS Surveys in Mathematical Sciences, 1 (2014), 113-151.  doi: 10.4171/EMSS/3.
    [2] T. Antal, S. Redner and V. Sood, Evolutionary dynamics on degree -heterogeneous graphs, Phys Rev Lett, 96 (2006), 188014.
    [3] A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509-512.  doi: 10.1126/science.286.5439.509.
    [4] B. Bollobás, Random Graphs, Academic Press, London, 1985.
    [5] B. BollobásO. RiordanJ. Spenser and G. Tusnády, The degree sequence of a scale-free random graph process, Random Struct.Alg, 18 (2001), 279-290.  doi: 10.1002/rsa.1009.
    [6] 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.
    [7] M. Broom and C. Cannings, Graphic Deviation, Discrete Mathematics, 338 (2015), 701-711.  doi: 10.1016/j.disc.2014.12.011.
    [8] M. Broom and C. Cannings, Games on dynamically evolving networks: Game theoretical modelling of a dynamically evolving network Ⅱ: special target sequences, In preparation.
    [9] M. Broom and J. Rychtář, An analysis of the fixation probability of a mutant on special classes of non-directed graphs, Proc R Soc A, 464 (2008), 2609-2627.  doi: 10.1098/rspa.2008.0058.
    [10] C. Cannings, The latent roots of certain markov chans arising in genetics: A new approach Ⅱ. Further haploid models, Adv.Appl.Prob., 7 (1975), 264-282.  doi: 10.1017/S0001867800045985.
    [11] C. Capitanio, Sociability and response to video playback in adult male rhesus monkeys (macac mulatta), Primates, 43 (2002), 169-177. 
    [12] M. CavaliereS. SedwardsC. E. TarnitaM. A. Nowak and A. Csikász-Nagy, Prosperity is associated with instability in dynamical networks, J. Theor. Biol., 299 (2012), 126-138.  doi: 10.1016/j.jtbi.2011.09.005.
    [13] R. C. ConnorM. R. Helthaus and L. M. Barre, Superalliances of bottlenose dolphins, Nature, 397 (1999), 571-572. 
    [14] P. I. M. Dunbar, Neocortex size as a constraint on group size in primates, J.Human Evoluion, 22 (1992), 468-493. 
    [15] C. S. Elton, Animal Ecology, Sidgwick & Jackson, London, 1927.
    [16] R. A. Fisher, The Genetical Theory of Natural Selection, Clarendon Press, Oxford, 1999.
    [17] F. Fu, C. Hauert, M. A. Nowak and L. Wang, Reputation-based partner choice promotes cooperation in social networks, Phys. Rev. E, 78 (2008), 026117.
    [18] S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, SIAM J. Appl.Math., 10 (1960), 496-506.  doi: 10.1137/0110037.
    [19] W. Hamilton, The genetical evolution of social behaviour, Ⅰ, Journal of Theoretical Biology, 7 (1964a), 16pp.
    [20] W. Hamilton, The genetical evolution of social behaviour, Ⅱ, Journal of Theoretical Biology, 7 (1964b), 52pp.
    [21] W. D. Hamilton, Extraordinary sex ratios, Science, 156 (1967), 477-488. 
    [22] W. Hässelbarth, Die Verzweightheit von Graphen, Comm. in Math. and Computer Chem. (MATCH), 16 (1984), 3-17. 
    [23] V. Havel, A remark on the existence of finite graphs, Časopis Pěst. Mat., 80 (1955), 477-480. 
    [24] R. A. Hill and R. I. M. Dunbar, Social network size in humans, Human Nature, 1 (2003), 53-72. 
    [25] J. Hofbauer and K. Sigmund, The Theory of Evolution and Dynamical Systems, Cambridge University Press, 1988.
    [26] J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, 1998. doi: 10.1017/CBO9781139173179.
    [27] M. Kimura, "Stepping stone" model of population, Ann. Rep. Nat. Ist. Genet. Mishima, 3 (1953), 63-65. 
    [28] E. LiebermanC. Hauert and M. A. Nowak, Evolutionary dynamics on graphs, Nature, 433 (2005), 312-316. 
    [29] J. Maynard Smith and G. R. Price, The logic of animal conflict, Nature, 246 (1973), 15-18. 
    [30] J. Maynard Smith, Evolution and the Theory of Games, Cambridge University Press, 1982.
    [31] B. D. McKay and N. C. Wormald, Uniform generation of random regular graphs of moderate degree, J. Algorithms, 11 (1990), 52-67.  doi: 10.1016/0196-6774(90)90029-E.
    [32] R. Merris and T. Roby, The lattice of threshold graphs, J. Inequal. Pure and Appl. Math., 6 (2005), Article 2, 21pp.
    [33] P. A. P. Moran, The theory of some genetical effects of population subdivision, Aust. J. biol. Sci., 12 (1959), 109-116. 
    [34] R. Noë, Biological markets: Partner choice as the driving force behind the evolution of cooperation. In: Economics in Nature. Social Dilemmas, Mate Choice and Biological Markets, (Ed. by Noë, R., van Hooff, J. A. R. A. M. and Hammerstein, P. ), (2001), 93-118. Cambridge: Cambridge University Press.
    [35] 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. 
    [36] J. M. PachecoA. 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.
    [37] 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.
    [38] J. PepperJ. Mitani and D. Watts, General gregariousness and specific social preferences among wild chimpanzees, Int. J. Primatol., 20 (1999), 613-632. 
    [39] M. Perc and A. Szolnoki, Coevolutionarygames -a mini review, BioSystems, 99 (2010), 109-125. 
    [40] H. Richter, Dynamic landscape models of coevolutionary games, 2016, arXiv: 1611.09149v1 [q-bio.PE]
    [41] E. Ruch and I. Gutman, The branching extent of graphs, J. Combin. Inform. Systems Sci., 4 (1979), 285-295. 
    [42] 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. 
    [43] B. Skyrms and R. Pemantle, A dynamic modeloof social network formation, Proc. Naatl. Acad. Sci. USA, 97 (2000), 9340-9346. 
    [44] R. Southwell and C. Cannings, Some models of reproducing graphs: Ⅰ pure reproduction, Applied Mathematics, 1 (2010), 137-145. 
    [45] R. Southwell and C. Cannings, Some models of reproducing graphs: Ⅱ age capped, Reproduction Applied Mathematics, 1 (2010), 251-259. 
    [46] R. Southwell and C. Cannings, Some models of reproducing graphs: Ⅲ game based reproduction, Applied Mathematics, 1 (2010), 335-343. 
    [47] G. Szabo and G. Fath, Evolutionary games on graphs, Phys. Rep., 446 (2007), 97-216.  doi: 10.1016/j.physrep.2007.04.004.
    [48] C. TaylorD. FudenbergA. Sasaki and M. A. Nowak, Evolutionary game dynamics in finite populations, Bulletin of Mathematical Biology, 66 (2004), 1621-1644.  doi: 10.1016/j.bulm.2004.03.004.
    [49] B. Voelkl and C. Kasper, Social structure of primate interaction networks facilitates the emergence of cooperation, Biology Letters, 5 (2009), 462-464. 
    [50] 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, Journal of Theoretical Biology, 252 (2008), 77-86. 
    [51] J. WiszniewskiC. Brown and L. M. Moller, Complex patterns of male alliance formation in dolphin social networks, Journal of Mammalogy, 93 (2012), 239-250. 
    [52] S. Wright, Evolution in Mendelian populations, Genetics, 16 (1931), 97-159. 
    [53] S. Wright, Breeding structure of populations in relation to speciation, Am. Naturalist, 74 (1940), 232-248. 
  • 加载中

Figures(2)

Tables(8)

SHARE

Article Metrics

HTML views(1443) PDF downloads(144) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return