The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem

References

• Bishop DT, Cannings C (1976) Models of animal conflict. Adv. Appl. Probab. 8(4):616–621.Crossref, Google Scholar
• Bomze IM (1992) Detecting all evolutionarily stable strategies. J. Optim. Theory Appl. 75(2):313–329.Crossref, Google Scholar
• Bomze IM (1998) On standard quadratic optimization problems. J. Global Optim. 13(4):369–387.Crossref, Google Scholar
• Bomze IM (2002) Regularity versus degeneracy in dynamics, games, and optimization: A unified approach to different aspects. SIAM Rev. 44(3):394–414.Crossref, Google Scholar
• Bomze IM, De Klerk E (2002) Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24(2):163–185.Crossref, Google Scholar
• Bomze IM, Pötscher BM (1989) Game Theoretical Foundations of Evolutionary Stability, Lecture Notes in Economics and Mathematical Systems, Vol. 324 (Springer, Berlin).Crossref, Google Scholar
• Bomze IM, Schachinger W, Ullrich R (2014) From seven to eleven: Completely positive matrices with high cp-rank. Linear Algebra Appl. 459:208–221.Crossref, Google Scholar
• Bomze IM, Schachinger W, Ullrich R (2015) New lower bounds and asymptotics for the cp-rank. SIAM J. Matrix Anal. Appl. 36(1):20–37.Crossref, Google Scholar
• Broom M, Cannings C, Vickers GT (1993) On the number of local maxima of a constrained quadratic form. Proc. Roy. Soc. London. Ser. A Math. Physical Sci. 443(1919):573–584.Crossref, Google Scholar
• Broom M, Cannings C, Vickers GT (1994) Sequential methods for generating patterns of ESS’s. J. Math. Biol. 32(6):597–615.Crossref, Google Scholar
• Broom M, Cannings C, Vickers GT (1996) ESS patterns: Adding pairs to an ESS. Math. Biosciences 136(1):21–33.Crossref, Google Scholar
• Cannings C, Vickers GT (1988) Patterns of ESS’s II. J. Theoret. Biol. 132(4):409–420.Crossref, Google Scholar
• Chen X, Peng J (2015) New analysis on sparse solutions to random standard quadratic optimization problems and extensions. Math. Oper. Res. 40(3):725–738.Link, Google Scholar
• Chen X, Peng J, Zhang S (2013) Sparse solutions to random standard quadratic optimization problems. Math. Programming 141(1–2):273–293.Crossref, Google Scholar
• De Klerk E (2008) The complexity of optimizing over a simplex, hypercube or sphere: A short survey. Central Eur. J. Oper. Res. 16(2):111–125.Crossref, Google Scholar
• Hofbauer J, Sigmund K (1988) The Theory of Evolution and Dynamical Systems: Mathematical Aspects of Selection (Cambridge University Press, Cambridge, UK).Google Scholar
• Hofbauer J, Sigmund K (1998) Evolutionary Games and Population Dynamics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Kingman JFC (1961) A mathematical problem in population genetics. Math. Proc. Cambridge Philos. Soc. 57(3):574–582.Crossref, Google Scholar
• Kingman JFC (1988) Typical polymorphisms maintained by selection at a single locus. J. Appl. Probab. 25(A):113–125.Crossref, Google Scholar
• Kontogiannis S, Spirakis P (2005) Counting stable strategies in random evolutionary games. Deng X, Du DZ, eds. Algorithms and Computation: Proc. 16th Internat. Sympos. (ISAAC 2005), Lecture Notes in Computer Science, Vol. 3827 (Springer, Berlin), 839–848.Crossref, Google Scholar
• Kontogiannis SC, Spirakis PG (2009) On the support size of stable strategies in random games. Theoret. Computer Sci. 410(8):933–942.Crossref, Google Scholar
• Kontogiannis SC, Spirakis PG (2010) Well supported approximate equilibria in bimatrix games. Algorithmica 57(4):653–667.Crossref, Google Scholar
• Moon JW, Moser L (1965) On cliques in graphs. Israel J. Math. 3(1):23–28.Crossref, Google Scholar
• Pardalos PM, Vavasis SA (1991) Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1):15–22.Crossref, Google Scholar
• Rota Bulò S, Bomze IM (2011) Infection and immunization: A new class of evolutionary game dynamics. Games Econom. Behaviour 71(1):193–211.Crossref, Google Scholar
• Sandholm WH (2010) Population Games and Evolutionary Dynamics (MIT Press, Cambridge, MA).Google Scholar
• Vickers GT, Cannings C (1988) On the number of stable equilibria in a one-locus, multi-allelic system. J. Theoret. Biol. 131(3):273–277.Crossref, Google Scholar
• Vickers GT, Cannings C (1988) Patterns of ESS’s I. J. Theoret. Biol. 132(4):387–408.Crossref, Google Scholar
• Weibull JW (1995) Evolutionary Game Theory (MIT Press, Cambridge, MA).Google Scholar