IDEAS home Printed from https://ideas.repec.org/a/spr/eurphb/v89y2016i12d10.1140_epjb_e2016-70464-0.html
   My bibliography  Save this article

Self-organization in a distributed coordination game through heuristic rules

Author

Listed:
  • Shubham Agarwal

    (Indian Institute of Technology)

  • Diptesh Ghosh

    (Production & Quantitative Methods Area, Indian Institute of Management)

  • Anindya S. Chakrabarti

    (Economics Area, Indian Institute of Management)

Abstract

In this paper, we consider a distributed coordination game played by a large number of agents with finite information sets, which characterizes emergence of a single dominant attribute out of a large number of competitors. Formally, N agents play a coordination game repeatedly, which has exactly N pure strategy Nash equilibria, and all of the equilibria are equally preferred by the agents. The problem is to select one equilibrium out of N possible equilibria in the least number of attempts. We propose a number of heuristic rules based on reinforcement learning to solve the coordination problem. We see that the agents self-organize into clusters with varying intensities depending on the heuristic rule applied, although all clusters but one are transitory in most cases. Finally, we characterize a trade-off in terms of the time requirement to achieve a degree of stability in strategies versus the efficiency of such a solution.

Suggested Citation

  • Shubham Agarwal & Diptesh Ghosh & Anindya S. Chakrabarti, 2016. "Self-organization in a distributed coordination game through heuristic rules," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 89(12), pages 1-10, December.
  • Handle: RePEc:spr:eurphb:v:89:y:2016:i:12:d:10.1140_epjb_e2016-70464-0
    DOI: 10.1140/epjb/e2016-70464-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1140/epjb/e2016-70464-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1140/epjb/e2016-70464-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

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

    Other versions of this item:

    References listed on IDEAS

    as
    1. Anirban Chakraborti & Damien Challet & Arnab Chatterjee & Matteo Marsili & Yi-Cheng Zhang & Bikas K. Chakrabarti, 2013. "Statistical Mechanics of Competitive Resource Allocation using Agent-based Models," Papers 1305.2121, arXiv.org, revised Sep 2014.
    2. Emanuele Pugliese & Claudio Castellano & Matteo Marsili & Luciano Pietronero, 2009. "Collaborate, compete and share," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 67(3), pages 319-327, February.
    3. Arthur, W Brian, 1994. "Inductive Reasoning and Bounded Rationality," American Economic Review, American Economic Association, vol. 84(2), pages 406-411, May.
    4. Challet, Damien & Marsili, Matteo & Zhang, Yi-Cheng, 2013. "Minority Games: Interacting agents in financial markets," OUP Catalogue, Oxford University Press, number 9780199686698.
    5. W. Brian Arthur, 1994. "Inductive Reasoning, Bounded Rationality and the Bar Problem," Working Papers 94-03-014, Santa Fe Institute.
    6. Challet, Damien, 2008. "Inter-pattern speculation: Beyond minority, majority and $-games," Journal of Economic Dynamics and Control, Elsevier, vol. 32(1), pages 85-100, January.
    7. Challet, D. & Zhang, Y.-C., 1997. "Emergence of cooperation and organization in an evolutionary game," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 246(3), pages 407-418.
    8. Anirban Chakraborti & Damien Challet & Arnab Chatterjee & Matteo Marsili & Yi-Cheng Zhang & Bikas K. Chakrabarti, 2013. "Statistical Mechanics of Competitive Resource Allocation using Agent-based Models," Papers 1305.2121, arXiv.org, revised Sep 2014.
    9. Duncan J. Watts & Peter Sheridan Dodds, 2007. "Influentials, Networks, and Public Opinion Formation," Journal of Consumer Research, Journal of Consumer Research Inc., vol. 34(4), pages 441-458, May.
    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. Kalliopi Kastampolidou & Christos Papalitsas & Theodore Andronikos, 2021. "DKPRG or how to succeed in the Kolkata Paise Restaurant gamevia TSP," Papers 2101.07760, arXiv.org.
    2. Kalliopi Kastampolidou & Christos Papalitsas & Theodore Andronikos, 2022. "The Distributed Kolkata Paise Restaurant Game," Games, MDPI, vol. 13(3), pages 1-21, April.

    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. Anindya S. Chakrabarti & Diptesh Ghosh, 2019. "Emergence of anti-coordination through reinforcement learning in generalized minority games," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 14(2), pages 225-245, June.
    2. Ghosh, Diptesh & Chakrabarti, Anindya S., 2017. "Emergence of distributed coordination in the Kolkata Paise Restaurant problem with finite information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 483(C), pages 16-24.
    3. Vee-Liem Saw & Lock Yue Chew, 2020. "No-boarding buses: Synchronisation for efficiency," PLOS ONE, Public Library of Science, vol. 15(3), pages 1-34, March.
    4. Jovanovic, Franck & Mantegna, Rosario N. & Schinckus, Christophe, 2019. "When financial economics influences physics: The role of Econophysics," International Review of Financial Analysis, Elsevier, vol. 65(C).
    5. Kiran Sharma & Anamika & Anindya S. Chakrabarti & Anirban Chakraborti & Sujoy Chakravarty, 2017. "The Saga of KPR: Theoretical and Experimental developments," Papers 1712.06358, arXiv.org.
    6. Chakrabarti, Anindya S. & Ghosh, Diptesh, 2016. "Improving Server Utilization in a Distributed Computing Set-up with Independent Clients," IIMA Working Papers WP2016-05-02, Indian Institute of Management Ahmedabad, Research and Publication Department.
    7. Ren, F. & Zhang, Y.C., 2008. "Trading model with pair pattern strategies," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(22), pages 5523-5534.
    8. Hosseiny, Ali & Gallegati, Mauro, 2017. "Role of intensive and extensive variables in a soup of firms in economy to address long run prices and aggregate data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 470(C), pages 51-59.
    9. Kets, W., 2007. "The Minority Game : An Economics Perspective," Other publications TiSEM 65d52a6a-b27d-45a9-93a7-e, Tilburg University, School of Economics and Management.
    10. Olivier Tercieux & Mark Voorneveld, 2010. "The cutting power of preparation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 71(1), pages 85-101, February.
    11. Kets, W., 2008. "Networks and learning in game theory," Other publications TiSEM 7713fce1-3131-498c-8c6f-3, Tilburg University, School of Economics and Management.
    12. Xin-Jie Zhang & Yong Tang & Jason Xiong & Wei-Jia Wang & Yi-Cheng Zhang, 2018. "Dynamics of Cooperation in Minority Games in Alliance Networks," Sustainability, MDPI, vol. 10(12), pages 1-17, December.
    13. Tercieux, O.R.C. & Voorneveld, M., 2005. "The Cutting Power of Preparation," Other publications TiSEM 75173341-627f-4eb2-91f1-0, Tilburg University, School of Economics and Management.
    14. Linde, Jona & Gietl, Daniel & Sonnemans, Joep & Tuinstra, Jan, 2023. "The effect of quantity and quality of information in strategy tournaments," Journal of Economic Behavior & Organization, Elsevier, vol. 211(C), pages 305-323.
    15. Jean-Philippe Bouchaud & Matteo Marsili & Jean-Pierre Nadal, 2023. "Application of spin glass ideas in social sciences, economics and finance," Papers 2306.16165, arXiv.org.
    16. Katahira, Kei & Chen, Yu & Hashimoto, Gaku & Okuda, Hiroshi, 2019. "Development of an agent-based speculation game for higher reproducibility of financial stylized facts," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 524(C), pages 503-518.
    17. Challet, Damien & Zhang, Yi-Cheng, 1998. "On the minority game: Analytical and numerical studies," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 256(3), pages 514-532.
    18. Benjamin Patrick Evans & Mikhail Prokopenko, 2021. "Bounded rationality for relaxing best response and mutual consistency: The Quantal Hierarchy model of decision-making," Papers 2106.15844, arXiv.org, revised Mar 2023.
    19. Chmura, Thorsten & Pitz, Thomas, 2004. "Minority Game: Experiments and Simulations of Traffic Scenarios," Bonn Econ Discussion Papers 23/2004, University of Bonn, Bonn Graduate School of Economics (BGSE).
    20. Rothenstein, R & Pawelzik, K, 2003. "Evolution and anti-evolution in a minimal stock market model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 326(3), pages 534-543.

    More about this item

    Keywords

    Statistical and Nonlinear Physics;

    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:spr:eurphb:v:89:y:2016:i:12:d:10.1140_epjb_e2016-70464-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.