IDEAS home Printed from https://ideas.repec.org/p/ems/eureri/15181.html
   My bibliography  Save this paper

A Mathematical Analysis of the Long-run Behavior of Genetic Algorithms for Social Modeling

Author

Listed:
  • Waltman, L.
  • van Eck, N.J.P.

Abstract

We present a mathematical analysis of the long-run behavior of genetic algorithms that are used for modeling social phenomena. The analysis relies on commonly used mathematical techniques in evolutionary game theory. Assuming a positive but infinitely small mutation rate, we derive results that can be used to calculate the exact long-run behavior of a genetic algorithm. Using these results, the need to rely on computer simulations can be avoided. We also show that if the mutation rate is infinitely small the crossover rate has no effect on the long-run behavior of a genetic algorithm. To demonstrate the usefulness of our mathematical analysis, we replicate a well-known study by Axelrod in which a genetic algorithm is used to model the evolution of strategies in iterated prisoner’s dilemmas. The theoretically predicted long-run behavior of the genetic algorithm turns out to be in perfect agreement with the long-run behavior observed in computer simulations. Also, in line with our theoretically informed expectations, computer simulations indicate that the crossover rate has virtually no long-run effect. Some general new insights into the behavior of genetic algorithms in the prisoner’s dilemma context are provided as well.

Suggested Citation

  • Waltman, L. & van Eck, N.J.P., 2009. "A Mathematical Analysis of the Long-run Behavior of Genetic Algorithms for Social Modeling," ERIM Report Series Research in Management ERS-2009-011-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    • Handle: RePEc:ems:eureri:15181
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/15181/ERS-2009-011-LIS.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    2. van Bragt, David & van Kemenade, Cees & la Poutre, Han, 2001. "The Influence of Evolutionary Selection Schemes on the Iterated Prisoner's Dilemma," Computational Economics, Springer;Society for Computational Economics, vol. 17(2-3), pages 253-263, June.
    3. Arifovic, Jasmina, 1994. "Genetic algorithm learning and the cobweb model," Journal of Economic Dynamics and Control, Elsevier, vol. 18(1), pages 3-28, January.
    4. Haruvy, Ernan & Roth, Alvin E. & Unver, M. Utku, 2006. "The dynamics of law clerk matching: An experimental and computational investigation of proposals for reform of the market," Journal of Economic Dynamics and Control, Elsevier, vol. 30(3), pages 457-486, March.
    5. Ashlock, Dan & Smucker, Mark & Stanley, E. Ann & Tesfatsion, Leigh, 1994. "Preferential Partner Selection in an Evolutionary Study of Prisoner's Dilemma," ISU General Staff Papers 199409010700001033, Iowa State University, Department of Economics.
    6. Tesfatsion, Leigh & Judd, Kenneth L., 2006. "Handbook of Computational Economics, Vol. 2: Agent-Based Computational Economics," Staff General Research Papers Archive 10368, Iowa State University, Department of Economics.
    7. Tesfatsion, Leigh, 2006. "Agent-Based Computational Economics: A Constructive Approach to Economic Theory," Handbook of Computational Economics, in: Leigh Tesfatsion & Kenneth L. Judd (ed.), Handbook of Computational Economics, edition 1, volume 2, chapter 16, pages 831-880, Elsevier.
    8. Lux, Thomas & Schornstein, Sascha, 2005. "Genetic learning as an explanation of stylized facts of foreign exchange markets," Journal of Mathematical Economics, Elsevier, vol. 41(1-2), pages 169-196, February.
    9. Kandori, Michihiro & Mailath, George J & Rob, Rafael, 1993. "Learning, Mutation, and Long Run Equilibria in Games," Econometrica, Econometric Society, vol. 61(1), pages 29-56, January.
    10. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, December.
    11. Fernando Vega-Redondo, 1997. "The Evolution of Walrasian Behavior," Econometrica, Econometric Society, vol. 65(2), pages 375-384, March.
    12. Vega-Redondo, Fernando (ed.), 1996. "Evolution, Games, and Economic Behaviour," OUP Catalogue, Oxford University Press, number 9780198774723.
    13. Brenner, Thomas, 2006. "Agent Learning Representation: Advice on Modelling Economic Learning," Handbook of Computational Economics, in: Leigh Tesfatsion & Kenneth L. Judd (ed.), Handbook of Computational Economics, edition 1, volume 2, chapter 18, pages 895-947, Elsevier.
    14. Leigh Tesfatsion & Kenneth L. Judd (ed.), 2006. "Handbook of Computational Economics," Handbook of Computational Economics, Elsevier, edition 1, volume 2, number 2.
    15. Ludo Waltman & Nees Eck, 2009. "Robust Evolutionary Algorithm Design for Socio-Economic Simulation: Some Comments," Computational Economics, Springer;Society for Computational Economics, vol. 33(1), pages 103-105, February.
    16. Georges, Christophre, 2006. "Learning with misspecification in an artificial currency market," Journal of Economic Behavior & Organization, Elsevier, vol. 60(1), pages 70-84, May.
    17. Marks, R E, 1992. "Breeding Hybrid Strategies: Optimal Behaviour for Oligopolists," Journal of Evolutionary Economics, Springer, vol. 2(1), pages 17-38, March.
    18. Vriend, Nicolaas J., 2000. "An illustration of the essential difference between individual and social learning, and its consequences for computational analyses," Journal of Economic Dynamics and Control, Elsevier, vol. 24(1), pages 1-19, January.
    19. Floortje Alkemade & Han Poutré & Hans Amman, 2006. "Robust Evolutionary Algorithm Design for Socio-economic Simulation," Computational Economics, Springer;Society for Computational Economics, vol. 28(4), pages 355-370, November.
    20. Arifovic, Jasmina, 1996. "The Behavior of the Exchange Rate in the Genetic Algorithm and Experimental Economies," Journal of Political Economy, University of Chicago Press, vol. 104(3), pages 510-541, June.
    21. Miller, John H., 1996. "The coevolution of automata in the repeated Prisoner's Dilemma," Journal of Economic Behavior & Organization, Elsevier, vol. 29(1), pages 87-112, January.
    22. F. Alkemade & J.A. La Poutre & D.D.B. van Bragt, 2000. "Stabilization Of Tag-Mediated Interaction By Sexual Reproduction In An Evolutionary Agent System," Computing in Economics and Finance 2000 172, Society for Computational Economics.
    23. Floortje Alkemade & Han Poutré & Hans Amman, 2009. "Robust Evolutionary Algorithm Design for Socio-Economic Simulation: A Correction," Computational Economics, Springer;Society for Computational Economics, vol. 33(1), pages 99-101, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ludo Waltman & Nees Eck & Rommert Dekker & Uzay Kaymak, 2011. "Economic modeling using evolutionary algorithms: the effect of a binary encoding of strategies," Journal of Evolutionary Economics, Springer, vol. 21(5), pages 737-756, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ludo Waltman & Nees Eck & Rommert Dekker & Uzay Kaymak, 2011. "Economic modeling using evolutionary algorithms: the effect of a binary encoding of strategies," Journal of Evolutionary Economics, Springer, vol. 21(5), pages 737-756, December.
    2. Chen, Shu-Heng, 2012. "Varieties of agents in agent-based computational economics: A historical and an interdisciplinary perspective," Journal of Economic Dynamics and Control, Elsevier, vol. 36(1), pages 1-25.
    3. Duffy, John, 2006. "Agent-Based Models and Human Subject Experiments," Handbook of Computational Economics, in: Leigh Tesfatsion & Kenneth L. Judd (ed.), Handbook of Computational Economics, edition 1, volume 2, chapter 19, pages 949-1011, Elsevier.
    4. repec:zbw:iamodp:109915 is not listed on IDEAS
    5. Graubner, Marten, 2011. "The Spatial Agent-based Competition Model (SpAbCoM)," IAMO Discussion Papers 109915, Institute of Agricultural Development in Transition Economies (IAMO).
    6. Graupner, Marten, 2011. "The Spatial Agent-based Competition Model (SpAbCoM) [Das räumliche agenten-basierte Wettbewerbsmodell SpAbCoM]," IAMO Discussion Papers 135, Leibniz Institute of Agricultural Development in Transition Economies (IAMO).
    7. Waltman, Ludo & Kaymak, Uzay, 2008. "Q-learning agents in a Cournot oligopoly model," Journal of Economic Dynamics and Control, Elsevier, vol. 32(10), pages 3275-3293, October.
    8. Hommes, Cars & Lux, Thomas, 2013. "Individual Expectations And Aggregate Behavior In Learning-To-Forecast Experiments," Macroeconomic Dynamics, Cambridge University Press, vol. 17(2), pages 373-401, March.
    9. Tesfatsion, Leigh, 1998. "Teaching Agent-Based Computational Economics to Graduate Students," ISU General Staff Papers 199807010700001043, Iowa State University, Department of Economics.
    10. Arifovic, Jasmina & Karaivanov, Alexander, 2010. "Learning by doing vs. learning from others in a principal-agent model," Journal of Economic Dynamics and Control, Elsevier, vol. 34(10), pages 1967-1992, October.
    11. Georges, Christophre, 2006. "Learning with misspecification in an artificial currency market," Journal of Economic Behavior & Organization, Elsevier, vol. 60(1), pages 70-84, May.
    12. LeBaron, Blake, 2006. "Agent-based Computational Finance," Handbook of Computational Economics, in: Leigh Tesfatsion & Kenneth L. Judd (ed.), Handbook of Computational Economics, edition 1, volume 2, chapter 24, pages 1187-1233, Elsevier.
    13. Schipper, Burkhard C., 2009. "Imitators and optimizers in Cournot oligopoly," Journal of Economic Dynamics and Control, Elsevier, vol. 33(12), pages 1981-1990, December.
    14. Troy Tassier, 2013. "Handbook of Research on Complexity, by J. Barkley Rosser, Jr. and Edward Elgar," Eastern Economic Journal, Palgrave Macmillan;Eastern Economic Association, vol. 39(1), pages 132-133.
    15. Alós-Ferrer, Carlos & Buckenmaier, Johannes, 2017. "Cournot vs. Walras: A reappraisal through simulations," Journal of Economic Dynamics and Control, Elsevier, vol. 82(C), pages 257-272.
    16. Georges, Christophre & Wallace, John C., 2009. "Learning Dynamics And Nonlinear Misspecification In An Artificial Financial Market," Macroeconomic Dynamics, Cambridge University Press, vol. 13(5), pages 625-655, November.
    17. Antonio Doria, Francisco, 2011. "J.B. Rosser Jr. , Handbook of Research on Complexity, Edward Elgar, Cheltenham, UK--Northampton, MA, USA (2009) 436 + viii pp., index, ISBN 978 1 84542 089 5 (cased)," Journal of Economic Behavior & Organization, Elsevier, vol. 78(1-2), pages 196-204, April.
    18. Casari, Marco, 2008. "Markets in equilibrium with firms out of equilibrium: A simulation study," Journal of Economic Behavior & Organization, Elsevier, vol. 65(2), pages 261-276, February.
    19. Dawid, Herbert, 2007. "Evolutionary game dynamics and the analysis of agent-based imitation models: The long run, the medium run and the importance of global analysis," Journal of Economic Dynamics and Control, Elsevier, vol. 31(6), pages 2108-2133, June.
    20. Russell Golman, 2011. "Why learning doesn’t add up: equilibrium selection with a composition of learning rules," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(4), pages 719-733, November.
    21. Salle, Isabelle & Seppecher, Pascal, 2016. "Social Learning About Consumption," Macroeconomic Dynamics, Cambridge University Press, vol. 20(7), pages 1795-1825, October.

    More about this item

    Keywords

    economics; evolutionary game theory; genetic algorithm; long-run behavior; social modeling;
    All these keywords.

    JEL classification:

    • C02 - Mathematical and Quantitative Methods - - General - - - Mathematical Economics
    • C52 - Mathematical and Quantitative Methods - - Econometric Modeling - - - Model Evaluation, Validation, and Selection
    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • M - Business Administration and Business Economics; Marketing; Accounting; Personnel Economics
    • M11 - Business Administration and Business Economics; Marketing; Accounting; Personnel Economics - - Business Administration - - - Production Management
    • R4 - Urban, Rural, Regional, Real Estate, and Transportation Economics - - Transportation Economics

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ems:eureri:15181. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/erimanl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.