IDEAS home Printed from https://ideas.repec.org/p/ivi/wpasad/2005-05.html
   My bibliography  Save this paper

Coordination Through De Bruijn Sequences

Author

Listed:
  • Olivier Gossner

    (Paris-Jourdan Sciences Économiques)

  • Penélope Hernández

    (Universidad de Alicante)

Abstract

Let µ be a rational distribution over a finite alphabet, and ( ) be a n-periodic sequences which first n elements are drawn i.i.d. according to µ. We consider automata of bounded size that input and output at stage t. We prove the existence of a constant C such that, whenever , with probability close to 1 there exists an automaton of size m such that the empirical frequency of stages such that is close to 1. In particular, one can take , where and .

Suggested Citation

  • Olivier Gossner & Penélope Hernández, 2005. "Coordination Through De Bruijn Sequences," Working Papers. Serie AD 2005-05, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    • Handle: RePEc:ivi:wpasad:2005-05
    as

    Download full text from publisher

    File URL: http://www.ivie.es/downloads/docs/wpasad/wpasad-2005-05.pdf
    File Function: Fisrt version / Primera version, 2005
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Abreu, Dilip & Rubinstein, Ariel, 1988. "The Structure of Nash Equilibrium in Repeated Games with Finite Automata," Econometrica, Econometric Society, vol. 56(6), pages 1259-1281, November.
    2. O. Gossner & P. Hernandez, 2001. "On the complexity of coordination," THEMA Working Papers 2001-21, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    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. repec:dau:papers:123456789/6127 is not listed on IDEAS
    2. Renault, Jérôme & Scarsini, Marco & Tomala, Tristan, 2008. "Playing off-line games with bounded rationality," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 207-223, September.
    3. Olivier Gossner & Penélope Hernández & Ron Peretz, 2016. "The complexity of interacting automata," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 461-496, March.
    4. Jérôme Renault & Marco Scarsini & Tristan Tomala, 2007. "A Minority Game with Bounded Recall," Mathematics of Operations Research, INFORMS, vol. 32(4), pages 873-889, November.

    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. repec:dau:papers:123456789/6127 is not listed on IDEAS
    2. Hernández, Penélope & Urbano, Amparo, 2008. "Codification schemes and finite automata," Mathematical Social Sciences, Elsevier, vol. 56(3), pages 395-409, November.
    3. Fernando Oliveira, 2010. "Bottom-up design of strategic options as finite automata," Computational Management Science, Springer, vol. 7(4), pages 355-375, October.
    4. Olivier Gossner & Penélope Hernández & Ron Peretz, 2016. "The complexity of interacting automata," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 461-496, March.
    5. Renault, Jérôme & Scarsini, Marco & Tomala, Tristan, 2008. "Playing off-line games with bounded rationality," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 207-223, September.
    6. David Baron & Ehud Kalai, 1990. "Dividing a Cake by Majority: The Simplest Equilibria," Discussion Papers 919, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    7. Tracy Xiao Liu & Jenna Bednar & Yan Chen & Scott Page, 2019. "Directional behavioral spillover and cognitive load effects in multiple repeated games," Experimental Economics, Springer;Economic Science Association, vol. 22(3), pages 705-734, September.
    8. Jean-Luc Gaffard & Mauro Napoletano, 2012. "Agent-based models and economic policy," Sciences Po publications info:hdl:2441/53r60a8s3ku, Sciences Po.
    9. Samahita, Margaret & Holm, Håkan J., 2020. "Mining for Mood Effect in the Field," Working Papers 2020:2, Lund University, Department of Economics.
    10. Jehiel, Philippe, 1998. "Learning to Play Limited Forecast Equilibria," Games and Economic Behavior, Elsevier, vol. 22(2), pages 274-298, February.
    11. Prajit K. Dutta & Paolo Siconolfi, 2010. "Mixed strategy equilibria in repeated games with one‐period memory," International Journal of Economic Theory, The International Society for Economic Theory, vol. 6(1), pages 167-187, March.
    12. Samuelson, Larry & Swinkels, Jeroen M., 2003. "Evolutionary stability and lexicographic preferences," Games and Economic Behavior, Elsevier, vol. 44(2), pages 332-342, August.
    13. Van Damme, Eric, 1994. "Evolutionary game theory," European Economic Review, Elsevier, vol. 38(3-4), pages 847-858, April.
    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. Rubinstein, A. & Wolnsky, A., 1992. "A Rermark on Infinitely Repeated Extensive Games," Papers 4-92, Tel Aviv - the Sackler Institute of Economic Studies.
    16. van Damme, E.E.C., 1995. "Game theory : The next stage," Other publications TiSEM 7779b0f9-bef5-45c7-ae6b-7, Tilburg University, School of Economics and Management.
    17. Hamid Sabourian & Jihong Lee, 2004. "Complexity and Efficiency in Repeated Games with Negotiation," Econometric Society 2004 Far Eastern Meetings 401, Econometric Society.
    18. Daijiro Okada & Abraham Neyman, 2004. "Growing Strategy Sets in Repeated Games," Econometric Society 2004 North American Summer Meetings 625, Econometric Society.
    19. Jehiel, Philippe, 2005. "Analogy-based expectation equilibrium," Journal of Economic Theory, Elsevier, vol. 123(2), pages 81-104, August.
    20. 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.
    21. Christos A. Ioannou & Julian Romero, 2012. "Strategic Learning With Finite Automata Via The EWA-Lite Model," Purdue University Economics Working Papers 1269, Purdue University, Department of Economics.

    More about this item

    Keywords

    Coordination; complexity; De Bruijn sequences; automata;
    All these keywords.

    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:ivi:wpasad:2005-05. 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: Departamento de Edición (email available below). General contact details of provider: https://edirc.repec.org/data/ievages.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.