A game-theoretic investigation of selection methods in two-population coevolution

ABSTRACT

We examine the dynamical and game-theoretic properties of several selection methods in the context of two-population coevolution. The methods we examine are fitness-proportional, linear rank, truncation, and (μ,λ)-ES selection. We use simple symmetric variable-sum games in an evolutionary game-theoretic framework. Our results indicate that linear rank, truncation, and (μ,λ)-ES selection are somewhat better-behaved in a two-population setting than in the one-population case analyzed by Ficici et al. [4]. These alternative selection methods maintain the Nash-equilibrium attractors found in proportional selection, but also add non-Nash attractors as well as regions of phase-space that lead to cyclic dynamics. Thus, these alternative selection methods do not properly implement the Nash-equilibrium solution concept.

REFERENCES

• 1: R. Axelrod. The Evolution of Cooperation. Basic Books, 1984.
• 2: Thomas Bäck, Evolution Strategies: An Alternative Evolutionary Algorithm, Selected Papers from the European conference on Artificial Evolution, p.3-20, September 04-06, 1995
• 3: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, 2004
• 4: S. G. Ficici, O. Melnik, and J. B. Pollack. A game-theoretic and dynamical-systems analysis of selection methods in coevolution. IEEE Transactions on Evolutionary Computation, 9(6):580--602, 2005.
• 5: D. B. Fogel. An overview of evolutionary programming. In L. D. Davis, K. De Jong, M. D. Vose, and L. D. Whitley, editors, Evolutionary Algorithms, pages 89--109. Springer, 1997.
• 6: D. B. Fogel and G. B. Fogel. Evolutionary stable strategies are not always stable under evolutionary dynamics. In J. R. McDonnell, R. G. Reynolds, and D. B. Fogel, editors, Evolutionary Programming IV: The Proceedings of Fourth Annual Conference on Evolutionary Programming, pages 565--577. MIT Press, 1995.
• 7: D. Fudenberg and D. K. Levine. The Theory of Learning in Games. MIT Press, 1998.
• 8: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1998.
• 9: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 10: J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998.
• 11: J. Maynard Smith. Evolution and the Theory of Games. Cambridge University Press, 1982.
• 12: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Theory

Keywords:
coevolution, population dynamics, selection method, solution concept