IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v203y2010i3p684-691.html
   My bibliography  Save this article

Limitations of learning in automata-based systems

Author

Listed:
  • Oliveira, Fernando S.

Abstract

In this article, we aim to analyze the limitations of learning in automata-based systems by introducing the L+ algorithm to replicate quasi-perfect learning, i.e., a situation in which the learner can get the correct answer to any of his queries. This extreme assumption allows the generalization of any limitations of the learning algorithm to less sophisticated learning systems. We analyze the conditions under which the L+ infers the correct automaton and when it fails to do so. In the context of the repeated prisoners' dilemma, we exemplify how the L+ may fail to learn the correct automaton. We prove that a sufficient condition for the L+ algorithm to learn the correct automaton is to use a large number of look-ahead steps. Finally, we show empirically, in the product differentiation problem, that the computational time of the L+ algorithm is polynomial on the number of states but exponential on the number of agents.

Suggested Citation

  • Oliveira, Fernando S., 2010. "Limitations of learning in automata-based systems," European Journal of Operational Research, Elsevier, vol. 203(3), pages 684-691, June.
    • Handle: RePEc:eee:ejores:v:203:y:2010:i:3:p:684-691
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00560-8
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Mallik, Suman & Chhajed, Dilip, 2006. "Optimal temporal product introduction strategies under valuation changes and learning," European Journal of Operational Research, Elsevier, vol. 172(2), pages 430-452, July.
    2. Bunn, Derek W. & Oliveira, Fernando S., 2007. "Agent-based analysis of technological diversification and specialization in electricity markets," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1265-1278, September.
    3. Ben-porath, Elchanan, 1990. "The complexity of computing a best response automaton in repeated games with mixed strategies," Games and Economic Behavior, Elsevier, vol. 2(1), pages 1-12, March.
    4. Hsu, Hsi-Mei & Wang, Wen-Pai, 2004. "Dynamic programming for delayed product differentiation," European Journal of Operational Research, Elsevier, vol. 156(1), pages 183-193, July.
    5. Piccione, Michele, 1992. "Finite automata equilibria with discounting," Journal of Economic Theory, Elsevier, vol. 56(1), pages 180-193, February.
    6. Cai, Gangshu & Kock, Ned, 2009. "An evolutionary game theoretic perspective on e-collaboration: The collaboration effort and media relativeness," European Journal of Operational Research, Elsevier, vol. 194(3), pages 821-833, May.
    7. Fernando Oliveira, 2010. "Bottom-up design of strategic options as finite automata," Computational Management Science, Springer, vol. 7(4), pages 355-375, October.
    8. Banks, Jeffrey S. & Sundaram, Rangarajan K., 1990. "Repeated games, finite automata, and complexity," Games and Economic Behavior, Elsevier, vol. 2(2), pages 97-117, June.
    9. Derek W. Bunn & Fernando S. Oliveira, 2008. "Modeling the Impact of Market Interventions on the Strategic Evolution of Electricity Markets," Operations Research, INFORMS, vol. 56(5), pages 1116-1130, October.
    10. Sbeity, I. & Brenner, L. & Plateau, B. & Stewart, W.J., 2008. "Phase-type distributions in stochastic automata networks," European Journal of Operational Research, Elsevier, vol. 186(3), pages 1008-1028, May.
    11. Stewart, William J. & Atif, Karim & Plateau, Brigette, 1995. "The numerical solution of stochastic automata networks," European Journal of Operational Research, Elsevier, vol. 86(3), pages 503-525, November.
    12. Gerard, Pierre & Meyer, Jean-Arcady & Sigaud, Olivier, 2005. "Combining latent learning with dynamic programming in the modular anticipatory classifier system," European Journal of Operational Research, Elsevier, vol. 160(3), pages 614-637, February.
    13. van Ackere, Ann & Larsen, Erik R., 2004. "Self-organising behaviour in the presence of negative externalities: A conceptual model of commuter choice," European Journal of Operational Research, Elsevier, vol. 157(2), pages 501-513, September.
    14. Gusak, Oleg & Dayar, Tugrul & Fourneau, Jean-Michel, 2003. "Lumpable continuous-time stochastic automata networks," European Journal of Operational Research, Elsevier, vol. 148(2), pages 436-451, July.
    15. Uysal, Ertugrul & Dayar, Tugrul, 1998. "Iterative methods based on splittings for stochastic automata networks," European Journal of Operational Research, Elsevier, vol. 110(1), pages 166-186, October.
    16. Gilboa, Itzhak, 1988. "The complexity of computing best-response automata in repeated games," Journal of Economic Theory, Elsevier, vol. 45(2), pages 342-352, August.
    17. Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
    18. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    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. Fernando Oliveira, 2010. "Modeling Emotions and Reason in Agent-Based Systems," Computational Economics, Springer;Society for Computational Economics, vol. 35(2), pages 155-164, February.

    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. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    2. Hubie Chen, 2013. "Bounded rationality, strategy simplification, and equilibrium," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 593-611, August.
    3. Dargaj, Jakub & Simonsen, Jakob Grue, 2023. "A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff," Journal of Economic Theory, Elsevier, vol. 213(C).
    4. Spiegler, Ran, 2004. "Simplicity of beliefs and delay tactics in a concession game," Games and Economic Behavior, Elsevier, vol. 47(1), pages 200-220, April.
    5. Hernández, Penélope & Solan, Eilon, 2016. "Bounded computational capacity equilibrium," Journal of Economic Theory, Elsevier, vol. 163(C), pages 342-364.
    6. Binmore, Ken & Piccione, Michele & Samuelson, Larry, 1998. "Evolutionary Stability in Alternating-Offers Bargaining Games," Journal of Economic Theory, Elsevier, vol. 80(2), pages 257-291, June.
    7. Westhoff, Frank H. & Yarbrough, Beth V. & Yarbrough, Robert M., 1996. "Complexity, organization, and Stuart Kauffman's The Origins of Order," Journal of Economic Behavior & Organization, Elsevier, vol. 29(1), pages 1-25, January.
    8. Compte, Olivier & Postlewaite, Andrew, 2015. "Plausible cooperation," Games and Economic Behavior, Elsevier, vol. 91(C), pages 45-59.
    9. Ho, Teck-Hua, 1996. "Finite automata play repeated prisoner's dilemma with information processing costs," Journal of Economic Dynamics and Control, Elsevier, vol. 20(1-3), pages 173-207.
    10. João E. Gata, 2019. "Controlling Algorithmic Collusion: short review of the literature, undecidability, and alternative approaches," Working Papers REM 2019/77, ISEG - Lisbon School of Economics and Management, REM, Universidade de Lisboa.
    11. Jakub Dargaj & Jakob Grue Simonsen, 2020. "A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff," Papers 2005.13921, arXiv.org, revised Jun 2020.
    12. Joshua M. Epstein, 2007. "Agent-Based Computational Models and Generative Social Science," Introductory Chapters, in: Generative Social Science Studies in Agent-Based Computational Modeling, Princeton University Press.
    13. Sung, Shao-Chin & Dimitrov, Dinko, 2010. "Computational complexity in additive hedonic games," European Journal of Operational Research, Elsevier, vol. 203(3), pages 635-639, June.
    14. Olivier Compte & Andrew Postlewaite, 2007. "Effecting Cooperation," PIER Working Paper Archive 09-019, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 29 May 2009.
    15. Luca Anderlini & Leonardo Felli, 1999. "Incomplete Contracts and Complexity Costs," Theory and Decision, Springer, vol. 46(1), pages 23-50, February.
    16. Roman, Mihai Daniel, 2008. "Entreprises behavior in cooperative and punishment‘s repeated negotiations," MPRA Paper 37527, University Library of Munich, Germany, revised 05 Jan 2009.
    17. D. Sgroi & D. J. Zizzo, 2002. "Strategy Learning in 3x3 Games by Neural Networks," Cambridge Working Papers in Economics 0207, Faculty of Economics, University of Cambridge.
    18. Lin-Ju Chen & Lei Zhu & Ying Fan & Sheng-Hua Cai, 2013. "Long-Term Impacts of Carbon Tax and Feed-in Tariff Policies on China's Generating Portfolio and Carbon Emissions: A Multi-Agent-Based Analysis," Energy & Environment, , vol. 24(7-8), pages 1271-1293, December.
    19. Bunn, Derek W. & Oliveira, Fernando S., 2016. "Dynamic capacity planning using strategic slack valuation," European Journal of Operational Research, Elsevier, vol. 253(1), pages 40-50.
    20. Lee, Jihong & Sabourian, Hamid, 2007. "Coase theorem, complexity and transaction costs," Journal of Economic Theory, Elsevier, vol. 135(1), pages 214-235, July.

    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:eee:ejores:v:203:y:2010:i:3:p:684-691. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.