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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
    11. 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.
    12. Piccione, Michele, 1992. "Finite automata equilibria with discounting," Journal of Economic Theory, Elsevier, vol. 56(1), pages 180-193, February.
    13. 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.
    14. Fernando Oliveira, 2010. "Bottom-up design of strategic options as finite automata," Computational Management Science, Springer, vol. 7(4), pages 355-375, October.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    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. 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.
    4. 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.
    5. Compte, Olivier & Postlewaite, Andrew, 2015. "Plausible cooperation," Games and Economic Behavior, Elsevier, vol. 91(C), pages 45-59.
    6. 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.
    7. Hernández, Penélope & Solan, Eilon, 2016. "Bounded computational capacity equilibrium," Journal of Economic Theory, Elsevier, vol. 163(C), pages 342-364.
    8. 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.
    9. 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.
    10. 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.
    11. Gilboa Itzhak & Schmeidler David, 1994. "Infinite Histories and Steady Orbits in Repeated Games," Games and Economic Behavior, Elsevier, vol. 6(3), pages 370-399, May.
    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. Gülpınar, N. & Oliveira, F.S., 2012. "Robust trading in spot and forward oligopolistic markets," International Journal of Production Economics, Elsevier, vol. 138(1), pages 35-45.
    15. 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.
    16. Hamid Sabourian & Jihong Lee, 2004. "Complexity and Efficiency in Repeated Games with Negotiation," Econometric Society 2004 Far Eastern Meetings 401, Econometric Society.
    17. Daijiro Okada & Abraham Neyman, 2004. "Growing Strategy Sets in Repeated Games," Econometric Society 2004 North American Summer Meetings 625, Econometric Society.
    18. Abderezak Touzene, 2008. "A Tensor Sum Preconditioner for Stochastic Automata Networks," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 234-242, May.
    19. 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.
    20. Nachbar, John H & Zame, William R, 1996. "Non-computable Strategies and Discounted Repeated Games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(1), pages 103-122, June.

    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.