Computation of sparse and dense equilibrium strategies of evolutionary games
type: Item
instance of: scholarly article
title: Computation of sparse and dense equilibrium strategies of evolutionary games
zbMATH Open document ID: 1418.91080
author: Yiping Hao
author: Zhijun Wu
published in: Games
publication date: 2018-12-10T00:00:00Z
review text: Summary: The evolution of social or biological species can be modeled as an evolutionary game with the equilibrium strategies of the game as prediction for the ultimate distributions of species in population, when some species may survive with positive proportions, while others become extinct. We say a strategy is dense if it contains a large and diverse number of positive species, and is sparse if it has only a few dominant ones. Sparse equilibrium strategies can be found relatively easily, while dense ones are more computationally costly. Here we show that by formulating a ``complementary'' problem for the computation of equilibrium strategies, we are able to reduce the cost for computing dense equilibrium strategies much more efficiently. We describe the primary and complementary algorithms for computing dense as well as sparse equilibrium strategies, and present test results on randomly generated games as well as a more biologically related one. In particular, we demonstrate that the complementary algorithm is about an order of magnitude faster than the primary algorithm to obtain the dense equilibrium strategies for all our test cases.
Mathematics Subject Classification ID: 91A22
Mathematics Subject Classification ID: 91-04
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 92D10
zbMATH DE Number: 6991160
zbMATH Keywords: evolutionary games
zbMATH Keywords: Nash equilibrium
zbMATH Keywords: Shapley-Snow algorithm
zbMATH Keywords: dense vs. sparse strategies
zbMATH Keywords: biodiversity
MaRDI profile type: Publication
full work available at URL: g9030046
OpenAlex ID: W2874996774
cites work: The Logic of Animal Conflict
cites work: Q3040961
cites work: Q4885257
cites work: Evolutionary Games and Population Dynamics
cites work: Q3412993
cites work: Equilibrium points in n -person games
cites work: Non-cooperative games
cites work: On oblivious PTAS's for nash equilibrium
cites work: Nash and correlated equilibria: Some complexity considerations
cites work: New complexity results about Nash equilibria
cites work: Maxima for Graphs and a New Proof of a Theorem of Turán
cites work: Algorithms for the solution of quadratic knapsack problems
cites work: Q3145799
cites work: Q5801626
cites work: Equilibrium Points of Bimatrix Games
cites work: Two-person nonzero-sum games and quadratic programming
cites work: Q4864293
cites work: Regularization and Variable Selection Via the Elastic Net
cites work: For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
cites work: Stable signal recovery from incomplete and inaccurate measurements
cites work: Enhancing sparsity by reweighted \(\ell _{1}\) minimization
cites work: Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
cites work: Evolution towards the maximum clique
cites work: Q4484921
cites work: Q4902474
DOI: 10.3390/G9030046
description: scientific article; zbMATH DE number 6991160