American Institute of Mathematical Sciences

Advanced
October  2017, 4(4): 285-318. doi: 10.3934/jdg.2017016

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

Mark Broom 1,, and  Chris Cannings 2,

1. 

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

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

* Corresponding author: Mark Broom

Received  December 2016 Revised  May 2017 Published  September 2017

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.

Keywords: Degree preferences, graphic sequences, Markov process, stationary distribution, Nash equilibrium.
Mathematics Subject Classification: Primary: 05C57, 91A43; Secondary: 05C81.
Citation: Mark Broom, Chris Cannings. Game theoretical modelling of a dynamically evolving network Ⅰ: General target sequences. Journal of Dynamics and Games, 2017, 4 (4) : 285-318. doi: 10.3934/jdg.2017016
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.

[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ás, O. Riordan, J. 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. Cavaliere, S. Sedwards, C. E. Tarnita, M. 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. Connor, M. 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. Lieberman, C. 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. 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.

[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. Pepper, J. 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. Taylor, D. Fudenberg, A. 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. Wiszniewski, C. 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. 

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.

[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ás, O. Riordan, J. 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. Cavaliere, S. Sedwards, C. E. Tarnita, M. 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. Connor, M. 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. Lieberman, C. 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. 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.

[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. Pepper, J. 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. Taylor, D. Fudenberg, A. 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. Wiszniewski, C. 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. 

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 Options

Download full-size image

Download as PowerPoint slide

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.
Figure Options

Download full-size image

Download as PowerPoint slide

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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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$
Table Options

Download as excel

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$
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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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*
Table Options

Download as excel

FeeNewPNEs
.5048**
.312****
.28125624***
.2153240*
.181818216***
.1619322226***
.1517862538***
.15032627315462*
.142857555963**
.129464293046**
.1102941734***
.19133644*
.0982142142***
.0857141428333741
.05714343475361*
.05346718****
.018751020***
.0142863957***
0371115*
19233545*
48495051*
52565860*
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]$
Table Options

Download as excel

$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]$
[1]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics and Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[2]

Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091
[3]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51
[4]

Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics and Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1
[5]

Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153
[6]

Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[7]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[8]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[9]

Yair Daon. Bernoullicity of equilibrium measures on countable Markov shifts. Discrete and Continuous Dynamical Systems, 2013, 33 (9) : 4003-4015. doi: 10.3934/dcds.2013.33.4003
[10]

Peiyu Li. Solving normalized stationary points of a class of equilibrium problem with equilibrium constraints. Journal of Industrial and Management Optimization, 2018, 14 (2) : 637-646. doi: 10.3934/jimo.2017065
[11]

Ferruh Özbudak, Eda Tekin. Correlation distribution of a sequence family generalizing some sequences of Trachtenberg. Advances in Mathematics of Communications, 2021, 15 (4) : 647-662. doi: 10.3934/amc.2020087
[12]

Daoyi Xu, Yumei Huang, Zhiguo Yang. Existence theorems for periodic Markov process and stochastic functional differential equations. Discrete and Continuous Dynamical Systems, 2009, 24 (3) : 1005-1023. doi: 10.3934/dcds.2009.24.1005
[13]

Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121
[14]

Yanan Zhao, Yuguo Lin, Daqing Jiang, Xuerong Mao, Yong Li. Stationary distribution of stochastic SIRS epidemic model with standard incidence. Discrete and Continuous Dynamical Systems - B, 2016, 21 (7) : 2363-2378. doi: 10.3934/dcdsb.2016051
[15]

Xiaoling Zou, Dejun Fan, Ke Wang. Stationary distribution and stochastic Hopf bifurcation for a predator-prey system with noises. Discrete and Continuous Dynamical Systems - B, 2013, 18 (5) : 1507-1519. doi: 10.3934/dcdsb.2013.18.1507
[16]

Xiaolin Xu, Xiaoqiang Cai. Price and delivery-time competition of perishable products: Existence and uniqueness of Nash equilibrium. Journal of Industrial and Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843
[17]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control and Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010
[18]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1
[19]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[20]

Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049

 Impact Factor: 

Tools

Metrics

  • PDF downloads (135)
  • HTML views (318)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy