doi: 10.3934/dcdsb.2022001
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Modelling conflicting individual preference: Target sequences and graph realization

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

Received  September 2020 Revised  July 2021 Early access January 2022

This paper will consider a group of individuals who each have a target number of contacts they would like to have with other group members. We are interested in how close this can be to being realized, considering the group's long-term outcome under reasonable dynamics on the number of contacts. We formulate this as a graph realization problem for undirected graphs, with the individuals as vertices and the number of desired contacts as the vertex degree. It is well known that not all degree sequences can be realized as undirected graphs, and the Havel-Hakimi algorithm characterizes those that can. When we ask how close the degree sequences can be to realization, we ask for graphs that minimize the total deviation between what is desired and possible. The sets of all such graphs and all such associated sequences are termed the minimal sets. Broom and Cannings have previously considered this problem in many papers, and it is hard to tackle for general target sequences. This paper revisited the minimal set in general, investigating two particular classes of sequence in particular. We consider the n-element arithmetic sequence (n-1, n-2, … 1, 0) for general n, including obtaining a formula that generates the size of the minimal set for a given arithmetic sequence, and the all or nothing sequences, where targets are either 0 or n-1, where a recurrence relation for such a formula is found. Further, we consider the question of the size of the minimal set of sequences in general. We consider a strategic version of the model where the individuals are involved in a multiplayer game, each trying to achieve their target, and show that optimal play can lead to the minimal set being left, thus answering an open question from earlier work.

Citation: Raneem Aizouk, Mark Broom. Modelling conflicting individual preference: Target sequences and graph realization. Discrete and Continuous Dynamical Systems - B, doi: 10.3934/dcdsb.2022001
References:
[1]

B. Allen and M. A. Nowak, Games on graphs, EMS Surv. Math. Sci., 1 (2014), 113-151.  doi: 10.4171/EMSS/3.

[2]

T. Antal, S. Redner and V. Sood, Evolutionary dynamics on degree-heterogeneous graphs, Physical Review Letters, 96 (2006), 188104, 2006. doi: 10.1103/PhysRevLett.96.188104.

[3]

V. Bala and S. Goyal, A noncooperative model of network formation, Econometrica, 68 (2000), 1181-1229.  doi: 10.1111/1468-0262.00155.

[4]

S. A. Boorman, A combinatiorial optimization model for transmission of job information through contact networks, The Bell Journal of Economics, 6 (1975), 216-249.  doi: 10.2307/3003223.

[5]

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

[6]

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

[7]

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

[8]

M. Broom and J. Rychtář, An analysis of the fixation probability of a mutant on special classes of non-directed graphs, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 464 (2008), 2609-2627.  doi: 10.1098/rspa.2008.0058.

[9]

M. Broom and J. Rychtár, Game-Theoretical Models in Biology, Chapman & Hall/CRC Mathematical and Computational Biology Series. CRC Press, Boca Raton, FL, 2013.

[10]

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

[11]

C. Cannings and M. Broom, Game theoretical modelling of a dynamically evolving network Ⅱ: Target sequences of score 1, J. Dyn. Games, 7 (2020), 37-64.  doi: 10.3934/jdg.2020003.

[12]

B. Dutta and M. O Jackson, The stability and efficiency of directed communication networks, Review of Economic Design, 5 (2000), 251-272.  doi: 10.1007/PL00013688.

[13]

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.

[14]

W. D. Hamilton, The genetical evolution of social behaviour. ii, Journal of Theoretical Biology, 7 (1964), 17-52.  doi: 10.1016/0022-5193(64)90039-6.

[15]

W. D. Hamilton, Extraordinary sex ratios, Science, 156 (1967), 477-488.  doi: 10.1126/science.156.3774.477.

[16]

W. Hässelbarth, Die Verzweigtheit von Graphen, Match, 16 (1984), 3-17. 

[17]

V. Havel, A remark on the existence of finite graphs, Časopis Pĕst. Mat., 81 (1956), 405-409.  doi: 10.21136/CPM.1956.117224.

[18] J. Hofbauer and K. Sigmund, The theory of Evolution and Dynamical Systems, London Mathematical Society Student Texts, 7, Cambridge University Press, Cambridge, 1988. 
[19]

J. Hofbauer and K. Sigmund, et al, Evolutionary Games and Population Dynamics, Cambridge University Press, Cambridge, 1998. doi: 10.1017/CBO9781139173179.

[20]

M. O Jackson, The stability and efficiency of economic and social networks, In Advances in Economic Design, (2003), 319–361.

[21] M. O. Jackson, Social and Economic Networks, Princeton University Press, Princeton, NJ, 2008. 
[22]

M. O. Jackson, An overview of social networks and economic applications, Handbook of Social Economics, 1 (2011), 511-585. 

[23]

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

[24]

E. LiebermanC. Hauert and M. A. Nowak, Evolutionary dynamics on graphs, Nature, 433 (2005), 312-316.  doi: 10.1038/nature03204.

[25] J. Maynard Smith, Evolution and the Theory of Games, Cambridge university press, 1982. 
[26]

J. Maynard Smith and G. R. Price, The logic of animal conflict, Nature, 246 (1973), 15-18.  doi: 10.1038/246015a0.

[27]

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

[28]

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

[29]

J. M. PachecoA. Traulsen and M. A. Nowak, Coevolution of strategy and structure in complex networks with dynamical linking, Physical Review Letters, 97 (2006), 258103.  doi: 10.1103/PhysRevLett.97.258103.

[30]

M. Perc and A. Szolnoki, Coevolutionary games-A mini review, BioSystems, 99 (2010), 109-125.  doi: 10.1016/j.biosystems.2009.10.003.

[31]

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

[32]

N. J. A. Sloane, The On-Line encyclopedia of integer sequences.,

[33]

R. Southwell and C. Cannings, et al, Some models of reproducing graphs: I pure reproduction, Applied Mathematics, 1 (2010), 137–145. doi: 10.4236/am.2010.13018.

[34]

R. Southwell and C. Cannings, et al, Some models of reproducing graphs: Ⅱ age capped vertices, Applied Mathematics, 1 (2010), 251–2010. doi: 10.4236/am.2010.14031.

[35]

R. Southwell and C. Cannings, et al, Some models of reproducing graphs: Ⅲ game based reproduction, Applied Mathematics, 1 (2010), 335–343. doi: 10.4236/am.2010.15044.

[36]

G. Szabó and G. Fath, Evolutionary games on graphs, Phys. Rep., 446 (2007), 97-216.  doi: 10.1016/j.physrep.2007.04.004.

[37]

C. TaylorD. FudenbergA. Sasaki and M. A. Nowak, Evolutionary game dynamics in finite populations, Bull. Math. Biol., 66 (2004), 1621-1644.  doi: 10.1016/j.bulm.2004.03.004.

[38]

D. B. West, et al, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

show all references

References:
[1]

B. Allen and M. A. Nowak, Games on graphs, EMS Surv. Math. Sci., 1 (2014), 113-151.  doi: 10.4171/EMSS/3.

[2]

T. Antal, S. Redner and V. Sood, Evolutionary dynamics on degree-heterogeneous graphs, Physical Review Letters, 96 (2006), 188104, 2006. doi: 10.1103/PhysRevLett.96.188104.

[3]

V. Bala and S. Goyal, A noncooperative model of network formation, Econometrica, 68 (2000), 1181-1229.  doi: 10.1111/1468-0262.00155.

[4]

S. A. Boorman, A combinatiorial optimization model for transmission of job information through contact networks, The Bell Journal of Economics, 6 (1975), 216-249.  doi: 10.2307/3003223.

[5]

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

[6]

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

[7]

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

[8]

M. Broom and J. Rychtář, An analysis of the fixation probability of a mutant on special classes of non-directed graphs, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 464 (2008), 2609-2627.  doi: 10.1098/rspa.2008.0058.

[9]

M. Broom and J. Rychtár, Game-Theoretical Models in Biology, Chapman & Hall/CRC Mathematical and Computational Biology Series. CRC Press, Boca Raton, FL, 2013.

[10]

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

[11]

C. Cannings and M. Broom, Game theoretical modelling of a dynamically evolving network Ⅱ: Target sequences of score 1, J. Dyn. Games, 7 (2020), 37-64.  doi: 10.3934/jdg.2020003.

[12]

B. Dutta and M. O Jackson, The stability and efficiency of directed communication networks, Review of Economic Design, 5 (2000), 251-272.  doi: 10.1007/PL00013688.

[13]

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.

[14]

W. D. Hamilton, The genetical evolution of social behaviour. ii, Journal of Theoretical Biology, 7 (1964), 17-52.  doi: 10.1016/0022-5193(64)90039-6.

[15]

W. D. Hamilton, Extraordinary sex ratios, Science, 156 (1967), 477-488.  doi: 10.1126/science.156.3774.477.

[16]

W. Hässelbarth, Die Verzweigtheit von Graphen, Match, 16 (1984), 3-17. 

[17]

V. Havel, A remark on the existence of finite graphs, Časopis Pĕst. Mat., 81 (1956), 405-409.  doi: 10.21136/CPM.1956.117224.

[18] J. Hofbauer and K. Sigmund, The theory of Evolution and Dynamical Systems, London Mathematical Society Student Texts, 7, Cambridge University Press, Cambridge, 1988. 
[19]

J. Hofbauer and K. Sigmund, et al, Evolutionary Games and Population Dynamics, Cambridge University Press, Cambridge, 1998. doi: 10.1017/CBO9781139173179.

[20]

M. O Jackson, The stability and efficiency of economic and social networks, In Advances in Economic Design, (2003), 319–361.

[21] M. O. Jackson, Social and Economic Networks, Princeton University Press, Princeton, NJ, 2008. 
[22]

M. O. Jackson, An overview of social networks and economic applications, Handbook of Social Economics, 1 (2011), 511-585. 

[23]

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

[24]

E. LiebermanC. Hauert and M. A. Nowak, Evolutionary dynamics on graphs, Nature, 433 (2005), 312-316.  doi: 10.1038/nature03204.

[25] J. Maynard Smith, Evolution and the Theory of Games, Cambridge university press, 1982. 
[26]

J. Maynard Smith and G. R. Price, The logic of animal conflict, Nature, 246 (1973), 15-18.  doi: 10.1038/246015a0.

[27]

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

[28]

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

[29]

J. M. PachecoA. Traulsen and M. A. Nowak, Coevolution of strategy and structure in complex networks with dynamical linking, Physical Review Letters, 97 (2006), 258103.  doi: 10.1103/PhysRevLett.97.258103.

[30]

M. Perc and A. Szolnoki, Coevolutionary games-A mini review, BioSystems, 99 (2010), 109-125.  doi: 10.1016/j.biosystems.2009.10.003.

[31]

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

[32]

N. J. A. Sloane, The On-Line encyclopedia of integer sequences.,

[33]

R. Southwell and C. Cannings, et al, Some models of reproducing graphs: I pure reproduction, Applied Mathematics, 1 (2010), 137–145. doi: 10.4236/am.2010.13018.

[34]

R. Southwell and C. Cannings, et al, Some models of reproducing graphs: Ⅱ age capped vertices, Applied Mathematics, 1 (2010), 251–2010. doi: 10.4236/am.2010.14031.

[35]

R. Southwell and C. Cannings, et al, Some models of reproducing graphs: Ⅲ game based reproduction, Applied Mathematics, 1 (2010), 335–343. doi: 10.4236/am.2010.15044.

[36]

G. Szabó and G. Fath, Evolutionary games on graphs, Phys. Rep., 446 (2007), 97-216.  doi: 10.1016/j.physrep.2007.04.004.

[37]

C. TaylorD. FudenbergA. Sasaki and M. A. Nowak, Evolutionary game dynamics in finite populations, Bull. Math. Biol., 66 (2004), 1621-1644.  doi: 10.1016/j.bulm.2004.03.004.

[38]

D. B. West, et al, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

Figure 1.  Transitions between the elements of the minimal set of graphs K(min) of the sequence 111 showing every possible move between each of the six elements

————represents a link between the corresponding two nodes.
----represents the absence of such a link

Figure 2.  This figure shows the links between node $ i $ from $ S_1 $ and node $ j $ in $ S_2 $, where $ S_1:1, 2, \ldots, m-1, m. $ and $ S_2:2m, 2m-1 , \ldots, m+2, m+1 $ at the second step of the process in Lemma 3.8 (other links between the two sets are absent). These are in addition to the links between all elements of $ S_{1} $. All elements of $ S_{2} $ are split from each other. We have thus illustrated the situation prior to the third step
Figure 3.  In this figure we considered two types of sequences; the all or nothing and the arithmetic sequences, and fitted two lines for each; one for the even values and the other for the odd terms of the sequence

Line 1:represented by $ \blacksquare $...... refers to the even terms of the all or nothing sequences, $ Y = 0.9875x-2.025. $
Line 2: represented by $ \diamondsuit _{—— \ ——} $ refers to the odd terms of the all or nothing sequences, $ Y = 1.0357x-2.6071 $.
Line 3: represented by $ \blacktriangle \_\;\_\;\_\;\_ $ refers to the even terms of the arithmetic sequences, $ Y = 0.7935x-1.1786 $.
Line 4: represented by $ \bullet _{————} $ refers to the odd terms of the arithmetic sequences, $ Y = 0.7935x -0.3851 $

Table 1.  The sequences with the biggest minimal set size where $ n $ is the number of individuals, |J(min)| size: refers to the minimal set size. We also consider two special classes of sequence, the arithmetic (Ar, the sequence $ ^{+} $ above is an example) and all-or-nothing (AoN, sequences $ ^{*} $ above are examples) sequences discussed later, for comparison
$ n $ score $ |J(min)| $ sequence Ar Ar AoN AoN
$ |J(min)| $ score $ |J(min)| $ score
2 1 2 (1, 0) 2 1 2 1
3 2 3 (2, 2, 0)$ ^{*} $ 2 1 3 2
3 2 3 (2, 0, 0)$ ^{*} $
4 3 7 (3, 2, 0, 0) 7 2 7 4
4 3 7 (3, 3, 1, 0)
4 4 7 (3, 3, 0, 0)$ ^{*} $
4 2 7 (3, 2, 1, 0)$ ^{+} $
5 4 20 (4, 3, 1, 0, 0) 7 2 13 6
5 4 20 (4, 4, 3, 1, 0)
6 7 84 (5, 5, 4, 1, 0, 0) 30 3 34 9
7 9 262 (6, 6, 5, 1, 1, 0, 0) 30 3 76 12
7 9 262 (6, 6, 5, 5, 1, 0, 0)
$ n $ score $ |J(min)| $ sequence Ar Ar AoN AoN
$ |J(min)| $ score $ |J(min)| $ score
2 1 2 (1, 0) 2 1 2 1
3 2 3 (2, 2, 0)$ ^{*} $ 2 1 3 2
3 2 3 (2, 0, 0)$ ^{*} $
4 3 7 (3, 2, 0, 0) 7 2 7 4
4 3 7 (3, 3, 1, 0)
4 4 7 (3, 3, 0, 0)$ ^{*} $
4 2 7 (3, 2, 1, 0)$ ^{+} $
5 4 20 (4, 3, 1, 0, 0) 7 2 13 6
5 4 20 (4, 4, 3, 1, 0)
6 7 84 (5, 5, 4, 1, 0, 0) 30 3 34 9
7 9 262 (6, 6, 5, 1, 1, 0, 0) 30 3 76 12
7 9 262 (6, 6, 5, 5, 1, 0, 0)
Table 2.  In this table we show the size of the minimal set, its logarithm and the corresponding term from the approximation from above. We see here that whilst this approximation is poor as expected for small $ m $, the relative error (third column minus second column, divided by second column) decreases with $ m $, i.e. the larger $ m $, the more accurate value we will get from the approximation formula we gave
$ |J_{2m}|= \binom{3m+1}{m}-2\binom{3m+1}{m-1} $ $ \ln |J_{2m}| $ $ \ln |J_{2m}| \approx 2m \ln (3\sqrt{3}/2) $ $ \% $ error
$ |J_2|=2 $ ln $ |J_2|=0.70 $ ln$ |J_2|\approx1.90 $ 171.4
$ |J_4|=7 $ ln $ |J_4|= 1.95 $ ln $ |J_4|\approx3.82 $ 95.9
$ |J_8|=143 $ ln $ |J_8|=4.96 $ ln $ |J_8|\approx7.64 $ 54.0
$ |J_{14}|=21318 $ ln $ |J_{14}|=9.97 $ ln$ |J_{14}|\approx13.37 $ 34.1
$ |J_{18}|=690690 $ ln $ |J_{18}|=13.45 $ ln $ |J_{18}|\approx17.19 $ 27.8
$ |J_{100}|=5.90065579*10^{38} $ ln$ |J_{100}|=89.27 $ ln$ |J_{100}|\approx95.48 $ 7.0
$ |J_{2m}|= \binom{3m+1}{m}-2\binom{3m+1}{m-1} $ $ \ln |J_{2m}| $ $ \ln |J_{2m}| \approx 2m \ln (3\sqrt{3}/2) $ $ \% $ error
$ |J_2|=2 $ ln $ |J_2|=0.70 $ ln$ |J_2|\approx1.90 $ 171.4
$ |J_4|=7 $ ln $ |J_4|= 1.95 $ ln $ |J_4|\approx3.82 $ 95.9
$ |J_8|=143 $ ln $ |J_8|=4.96 $ ln $ |J_8|\approx7.64 $ 54.0
$ |J_{14}|=21318 $ ln $ |J_{14}|=9.97 $ ln$ |J_{14}|\approx13.37 $ 34.1
$ |J_{18}|=690690 $ ln $ |J_{18}|=13.45 $ ln $ |J_{18}|\approx17.19 $ 27.8
$ |J_{100}|=5.90065579*10^{38} $ ln$ |J_{100}|=89.27 $ ln$ |J_{100}|\approx95.48 $ 7.0
Table 3.  The sequences and minimal set sizes for the maximal score sequences for $ n = 2, \ldots, 9 $
Sequence minimal set size
{1, 0} 2
{2, 2, 0} 3
{3, 3, 0, 0} 7
{4, 4, 4, 0, 0} 13
{5, 5, 5, 0, 0, 0} 34
{6, 6, 6, 6, 0, 0, 0} 76
{7, 7, 7, 7, 0, 0, 0, 0} 221
{8, 8, 8, 8, 8, 0, 0, 0, 0} 557
Sequence minimal set size
{1, 0} 2
{2, 2, 0} 3
{3, 3, 0, 0} 7
{4, 4, 4, 0, 0} 13
{5, 5, 5, 0, 0, 0} 34
{6, 6, 6, 6, 0, 0, 0} 76
{7, 7, 7, 7, 0, 0, 0, 0} 221
{8, 8, 8, 8, 8, 0, 0, 0, 0} 557
Table 4.  The values of the minimal set for the all or nothing sequences with $ m_{1} $ "all" vertices and $ m_{2} $ "nothing" vertices
$ m_{1} $/$ m_{2} $ 0 1 2 3 4 5 6 7 8
0 1 1 1 1 1 1 1 1 1
1 1 2 3 4 5 6 7 9
2 1 3 7 13 22 34 50 70 95
3 1 4 13 34 76 152 280 482 787
4 1 5 22 76 221 557 1264 2630 5108
5 1 6 34 152 557 1736 4766 11812 26930
6 1 7 50 280 1264 4766 15584 45356 119999
7 1 8 70 482 2630 11812 45356 153228 465673
8 1 9 95 787 5108 26930 119999 465673 1611189
9 1 10 125 1230 9362 57270 293089 1294838 5060227
$ m_{1} $/$ m_{2} $ 0 1 2 3 4 5 6 7 8
0 1 1 1 1 1 1 1 1 1
1 1 2 3 4 5 6 7 9
2 1 3 7 13 22 34 50 70 95
3 1 4 13 34 76 152 280 482 787
4 1 5 22 76 221 557 1264 2630 5108
5 1 6 34 152 557 1736 4766 11812 26930
6 1 7 50 280 1264 4766 15584 45356 119999
7 1 8 70 482 2630 11812 45356 153228 465673
8 1 9 95 787 5108 26930 119999 465673 1611189
9 1 10 125 1230 9362 57270 293089 1294838 5060227
Table 5.  Here we show the logarithm of the size of the minimal sets for the all or nothing and arithmetic sequences
ln$ |J_{2m}| $ of the AoN ln$ |J_{2m}| $ of the Ar $ \ln |J_{2m}| \approx 2m \ln (3\sqrt{3}/2) $
ln $ |J_8|=5.4 $ ln $ |J_8|\approx 4.9 $ ln$ |J_8|\approx 7.64 $
ln$ |J_{10}|=7.5 $ ln $ |J_{10}|\approx 6.6 $ ln $ |J_{10}|\approx 9.55 $
ln$ |J_{12}|=9.7 $ ln $ |J_{12}|\approx8.3 $ ln $ |J_{12}|\approx 11.46 $
ln $ |J_{14}|=11.9 $ ln $ |J_{14}|\approx10 $ ln $ |J_{14}|\approx 13.67 $
$ ln|J_{16}|=14.3 $ ln $ |J_{16}|\approx 11.7 $ ln $ |J_{16}|\approx 15.28 $
ln$ |J_{2m}| $ of the AoN ln$ |J_{2m}| $ of the Ar $ \ln |J_{2m}| \approx 2m \ln (3\sqrt{3}/2) $
ln $ |J_8|=5.4 $ ln $ |J_8|\approx 4.9 $ ln$ |J_8|\approx 7.64 $
ln$ |J_{10}|=7.5 $ ln $ |J_{10}|\approx 6.6 $ ln $ |J_{10}|\approx 9.55 $
ln$ |J_{12}|=9.7 $ ln $ |J_{12}|\approx8.3 $ ln $ |J_{12}|\approx 11.46 $
ln $ |J_{14}|=11.9 $ ln $ |J_{14}|\approx10 $ ln $ |J_{14}|\approx 13.67 $
$ ln|J_{16}|=14.3 $ ln $ |J_{16}|\approx 11.7 $ ln $ |J_{16}|\approx 15.28 $
Table 6.  The sizes of the minimal set for the all or nothing sequences with $ m_{1} $ "all" vertices and $ m_{2} $ "nothing" vertices
ln$ |J_{2m}| $ of the AoN sequence ln$ |J_{2m}| $ of the Arithmetic sequence
ln $ |J_2|\approx 0.7 $ ln $ |J_2|\approx 0.7 $
ln $ |J_4|\approx 1.9 $ ln $ |J_4|\approx 1.9 $
ln $ |J_6|\approx 3.5 $ ln $ |J_6|\approx 3.4 $
ln $ |J_8|\approx 5.4 $ ln $ |J_8|\approx 4.9 $
ln$ |J_{10}|\approx 7.5 $ ln $ |J_{10}|\approx 6.6 $
ln$ |J_{12}|\approx 9.7 $ ln $ |J_{12}|\approx8.3 $
ln $ |J_{14}|\approx 11.9 $ ln $ |J_{14}|\approx10 $
$ ln|J_{16}|\approx 14.3 $ ln $ |J_{16}|\approx 11.7 $
ln$ |J_{2m}| $ of the AoN sequence ln$ |J_{2m}| $ of the Arithmetic sequence
ln $ |J_2|\approx 0.7 $ ln $ |J_2|\approx 0.7 $
ln $ |J_4|\approx 1.9 $ ln $ |J_4|\approx 1.9 $
ln $ |J_6|\approx 3.5 $ ln $ |J_6|\approx 3.4 $
ln $ |J_8|\approx 5.4 $ ln $ |J_8|\approx 4.9 $
ln$ |J_{10}|\approx 7.5 $ ln $ |J_{10}|\approx 6.6 $
ln$ |J_{12}|\approx 9.7 $ ln $ |J_{12}|\approx8.3 $
ln $ |J_{14}|\approx 11.9 $ ln $ |J_{14}|\approx10 $
$ ln|J_{16}|\approx 14.3 $ ln $ |J_{16}|\approx 11.7 $
[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

2021 Impact Factor: 1.497

Metrics

  • PDF downloads (283)
  • HTML views (160)
  • Cited by (0)

Other articles
by authors

[Back to Top]