IDEAS home Printed from https://ideas.repec.org/p/ivi/wpasad/2005-05.html

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. GOSSNER, Olivier & HERNANDEZ, Pénélope, 2001. "On the complexity of coordination," LIDAM Discussion Papers CORE 2001047, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. 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.
    2. repec:dau:papers:123456789/6127 is not listed on IDEAS
    3. 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.
    4. 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.

    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. 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. 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.
    5. Fernando Oliveira, 2010. "Bottom-up design of strategic options as finite automata," Computational Management Science, Springer, vol. 7(4), pages 355-375, October.
    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. Duffy, John & Ünver, M.Utku, 2008. "Internet auctions with artificial adaptive agents: A study on market design," Journal of Economic Behavior & Organization, Elsevier, vol. 67(2), pages 394-417, August.
    8. 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.
    9. Jean-Luc Gaffard & Mauro Napoletano, 2012. "Agent-based models and economic policy," Post-Print hal-03461120, HAL.
    10. Mark D. Flood & Oliver R. Goodenough, 2015. "Contract as Automaton: The Computational Representation of Financial Agreements," Working Papers 15-04, Office of Financial Research, US Department of the Treasury, revised 27 Mar 2017.
    11. Samahita, Margaret & Holm, Håkan J., 2020. "Mining for Mood Effect in the Field," Working Papers 2020:2, Lund University, Department of Economics.
    12. Jehiel, Philippe, 1998. "Learning to Play Limited Forecast Equilibria," Games and Economic Behavior, Elsevier, vol. 22(2), pages 274-298, February.
    13. 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.
    14. Luca Anderlini (Georgetown University), Dino Gerardi (Yale University), Roger Lagunoff (Georgetown University), 2004. "The Folk Theorem in Dynastic Repeated Games," Working Papers gueconwpa~04-04-09, Georgetown University, Department of Economics.
    15. Van Damme, Eric, 1994. "Evolutionary game theory," European Economic Review, Elsevier, vol. 38(3-4), pages 847-858, April.
    16. EL-Seidy, Essam, 2015. "The effect of noise and average relatedness between players in iterated games," Applied Mathematics and Computation, Elsevier, vol. 269(C), pages 343-350.
    17. 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.
    18. Rubinstein, A. & Wolnsky, A., 1992. "A Rermark on Infinitely Repeated Extensive Games," Papers 4-92, Tel Aviv - the Sackler Institute of Economic Studies.
    19. 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.
    20. Misha Gavrilovich & Victoria Kreps, 2018. "Games with Symmetric Incomplete Information and Asymmetric Computational Resources," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 20(02), pages 1-16, June.
    21. Lee, Jihong & Sabourian, Hamid, 2015. "Complexity and repeated implementation," Journal of Economic Theory, Elsevier, vol. 158(PA), pages 259-292.

    More about this item

    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.