IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1702.01017.html
   My bibliography  Save this paper

Emergence of Distributed Coordination in the Kolkata Paise Restaurant Problem with Finite Information

Author

Listed:
  • Diptesh Ghosh
  • Anindya S. Chakrabarti

Abstract

In this paper, we study a large-scale distributed coordination problem and propose efficient adaptive strategies to solve the problem. The basic problem is to allocate finite number of resources to individual agents such that there is as little congestion as possible and the fraction of unutilized resources is reduced as far as possible. In the absence of a central planner and global information, agents can employ adaptive strategies that uses only finite knowledge about the competitors. In this paper, we show that a combination of finite information sets and reinforcement learning can increase the utilization rate of resources substantially.

Suggested Citation

  • Diptesh Ghosh & Anindya S. Chakrabarti, 2017. "Emergence of Distributed Coordination in the Kolkata Paise Restaurant Problem with Finite Information," Papers 1702.01017, arXiv.org.
    • Handle: RePEc:arx:papers:1702.01017
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1702.01017
    File Function: Latest version
    Download Restriction: no
    ---><---

    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. Chakrabarti, Anindya Sundar & Chakrabarti, Bikas K. & Chatterjee, Arnab & Mitra, Manipushpak, 2009. "The Kolkata Paise Restaurant problem and resource utilization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(12), pages 2420-2426.
    3. Kalinowski, Thomas & Schulz, Hans-Jörg & Briese, Michael, 2000. "Cooperation in the Minority Game with local information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 277(3), pages 502-508.
    4. Challet, Damien & Marsili, Matteo & Zhang, Yi-Cheng, 2013. "Minority Games: Interacting agents in financial markets," OUP Catalogue, Oxford University Press, number 9780199686698.
    5. 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.
    6. Arthur, W Brian, 1994. "Inductive Reasoning and Bounded Rationality," American Economic Review, American Economic Association, vol. 84(2), pages 406-411, May.
    7. W. Brian Arthur, 1994. "Inductive Reasoning, Bounded Rationality and the Bar Problem," Working Papers 94-03-014, Santa Fe Institute.
    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. 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. Kiran Sharma & Anamika & Anindya S. Chakrabarti & Anirban Chakraborti & Sujoy Chakravarty, 2017. "The Saga of KPR: Theoretical and Experimental developments," Papers 1712.06358, arXiv.org.
    3. Kalliopi Kastampolidou & Christos Papalitsas & Theodore Andronikos, 2022. "The Distributed Kolkata Paise Restaurant Game," Games, MDPI, vol. 13(3), pages 1-21, April.
    4. Kejriwal, Saransh & Sheth, Sarjan & Silpa, P.S. & Sarkar, Sumit & Guha, Apratim, 2022. "Attaining herd immunity to a new infectious disease through multi-stage policies incentivising voluntary vaccination," Chaos, Solitons & Fractals, Elsevier, vol. 154(C).
    5. Kalliopi Kastampolidou & Christos Papalitsas & Theodore Andronikos, 2021. "DKPRG or how to succeed in the Kolkata Paise Restaurant gamevia TSP," Papers 2101.07760, arXiv.org.

    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. 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.
    3. Kiran Sharma & Anamika & Anindya S. Chakrabarti & Anirban Chakraborti & Sujoy Chakravarty, 2017. "The Saga of KPR: Theoretical and Experimental developments," Papers 1712.06358, arXiv.org.
    4. Priel, Avner & Tamir, Boaz, 2018. "Econophysics of a ranked demand and supply resource allocation problem," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 745-753.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Lustosa, Bernardo C. & Cajueiro, Daniel O., 2010. "Constrained information minority game: How was the night at El Farol?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(6), pages 1230-1238.
    10. 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.
    11. 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.
    12. 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.
    13. Kets, W. & Voorneveld, M., 2007. "Congestion, Equilibrium and Learning : The Minority Game," Other publications TiSEM 49539a1f-2921-4dd9-83a0-4, Tilburg University, School of Economics and Management.
    14. Amaral, Marco A. & Oliveira, Marcelo M. de & Javarone, Marco A., 2021. "An epidemiological model with voluntary quarantine strategies governed by evolutionary game dynamics," Chaos, Solitons & Fractals, Elsevier, vol. 143(C).
    15. Guglielmo Maria Caporale & Antoaneta Serguieva & Hao Wu, 2009. "Financial contagion: evolutionary optimization of a multinational agent‐based model," Intelligent Systems in Accounting, Finance and Management, John Wiley & Sons, Ltd., vol. 16(1‐2), pages 111-125, January.
    16. 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.
    17. Jean Philippe Bouchaud & Matteo Marsili & Jean-Pierre Nadal, 2023. "Application of spin glass ideas in social sciences, economics and finance," Post-Print hal-04145594, HAL.
    18. 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).
    19. Benjamin Patrick Evans & Mikhail Prokopenko, 2024. "Bounded rationality for relaxing best response and mutual consistency: the quantal hierarchy model of decision making," Theory and Decision, Springer, vol. 96(1), pages 71-111, February.
    20. 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.

    More about this item

    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:arx:papers:1702.01017. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.