# American Institute of Mathematical Sciences

doi: 10.3934/jdg.2020003

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

 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.

Citation: Chris Cannings, Mark Broom. Game theoretical modelling of a dynamically evolving network Ⅱ: Target sequences of score 1. Journal of Dynamics & Games, doi: 10.3934/jdg.2020003
##### References:

show all references

##### References:
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
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
The Petersen triangle with associated sets. Vertices are joined if the set-intersection is empty
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
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
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)
Two intersecting 14-cycles with 9 common vertices
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
 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
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
 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
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
 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] Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091 [2] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51 [3] Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics & Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1 [4] 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 [5] 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 & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2019060 [6] Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123 [7] Yair Daon. Bernoullicity of equilibrium measures on countable Markov shifts. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 4003-4015. doi: 10.3934/dcds.2013.33.4003 [8] Peiyu Li. Solving normalized stationary points of a class of equilibrium problem with equilibrium constraints. Journal of Industrial & Management Optimization, 2018, 14 (2) : 637-646. doi: 10.3934/jimo.2017065 [9] Daoyi Xu, Yumei Huang, Zhiguo Yang. Existence theorems for periodic Markov process and stochastic functional differential equations. Discrete & Continuous Dynamical Systems - A, 2009, 24 (3) : 1005-1023. doi: 10.3934/dcds.2009.24.1005 [10] Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121 [11] Yanan Zhao, Yuguo Lin, Daqing Jiang, Xuerong Mao, Yong Li. Stationary distribution of stochastic SIRS epidemic model with standard incidence. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2363-2378. doi: 10.3934/dcdsb.2016051 [12] Xiaoling Zou, Dejun Fan, Ke Wang. Stationary distribution and stochastic Hopf bifurcation for a predator-prey system with noises. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1507-1519. doi: 10.3934/dcdsb.2013.18.1507 [13] Xiaolin Xu, Xiaoqiang Cai. Price and delivery-time competition of perishable products: Existence and uniqueness of Nash equilibrium. Journal of Industrial & Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843 [14] Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control & Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010 [15] Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1 [16] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 [17] Kazuhiko Kuraya, Hiroyuki Masuyama, Shoji Kasahara. Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 593-610. doi: 10.3934/naco.2011.1.593 [18] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036 [19] Li Zu, Daqing Jiang, Donal O'Regan. Persistence and stationary distribution of a stochastic predator-prey model under regime switching. Discrete & Continuous Dynamical Systems - A, 2017, 37 (5) : 2881-2897. doi: 10.3934/dcds.2017124 [20] Janos Kollar. The Nash conjecture for threefolds. Electronic Research Announcements, 1998, 4: 63-73.

Impact Factor: