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

DKPRG or how to succeed in the Kolkata Paise Restaurant gamevia TSP

Author

Listed:
  • Kalliopi Kastampolidou
  • Christos Papalitsas
  • Theodore Andronikos

Abstract

The Kolkata Paise Restaurant Problem is a challenging game, in which $n$ agents must decide where to have lunch during their lunch break. The game is very interesting because there are exactly $n$ restaurants and each restaurant can accommodate only one agent. If two or more agents happen to choose the same restaurant, only one gets served and the others have to return back to work hungry. In this paper we tackle this problem from an entirely new angle. We abolish certain implicit assumptions, which allows us to propose a novel strategy that results in greater utilization for the restaurants. We emphasize the spatially distributed nature of our approach, which, for the first time, perceives the locations of the restaurants as uniformly distributed in the entire city area. This critical change in perspective has profound ramifications in the topological layout of the restaurants, which now makes it completely realistic to assume that every agent has a second chance. Every agent now may visit, in case of failure, more than one restaurants, within the predefined time constraints.

Suggested Citation

  • Kalliopi Kastampolidou & Christos Papalitsas & Theodore Andronikos, 2021. "DKPRG or how to succeed in the Kolkata Paise Restaurant gamevia TSP," Papers 2101.07760, arXiv.org.
    • Handle: RePEc:arx:papers:2101.07760
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. 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.
    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. Rego, César & Gamboa, Dorabela & Glover, Fred & Osterman, Colin, 2011. "Traveling salesman problem heuristics: Leading methods, implementations and latest advances," European Journal of Operational Research, Elsevier, vol. 211(3), pages 427-441, June.
    4. Bikas K. Chakrabarti, 2007. "Kolkata Restaurant Problem as a generalised El Farol Bar Problem," Papers 0705.2098, arXiv.org.
    5. 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.
    6. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    7. Kiran Sharma & Anamika & Anindya S. Chakrabarti & Anirban Chakraborti & Sujoy Chakravarty, 2017. "The Saga of KPR: Theoretical and Experimental developments," Papers 1712.06358, arXiv.org.
    8. Frédéric Abergel & Anirban Chakraborti & B.K. Chakrabarti & Asim Ghosh, 2013. "Econophysics of systemic risk and network dynamics," Post-Print hal-00872397, HAL.
    9. Milchtaich, Igal, 1996. "Congestion Games with Player-Specific Payoff Functions," Games and Economic Behavior, Elsevier, vol. 13(1), pages 111-124, March.
    10. Arthur, W Brian, 1994. "Inductive Reasoning and Bounded Rationality," American Economic Review, American Economic Association, vol. 84(2), pages 406-411, May.
    11. 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.
    Full references (including those not matched with items on IDEAS)

    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. Kalliopi Kastampolidou & Christos Papalitsas & Theodore Andronikos, 2022. "The Distributed Kolkata Paise Restaurant Game," Games, MDPI, vol. 13(3), pages 1-21, April.
    2. 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.
    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. 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.
    5. 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.
    6. Kiran Sharma & Anamika & Anindya S. Chakrabarti & Anirban Chakraborti & Sujoy Chakravarty, 2017. "The Saga of KPR: Theoretical and Experimental developments," Papers 1712.06358, arXiv.org.
    7. Wawrzyniak, Karol & Wiślicki, Wojciech, 2012. "Mesoscopic approach to minority games in herd regime," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(5), pages 2056-2082.
    8. 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.
    9. Gu, Gao-Feng & Chen, Wei & Zhou, Wei-Xing, 2008. "Empirical regularities of order placement in the Chinese stock market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(13), pages 3173-3182.
    10. Francis Bismans & Olivier Damette, 2012. "La taxe Tobin : une synthèse des travaux basés sur la théorie des jeux et l’économétrie," Working Papers of BETA 2012-09, Bureau d'Economie Théorique et Appliquée, UDS, Strasbourg.
    11. Linde, Jona & Sonnemans, Joep & Tuinstra, Jan, 2014. "Strategies and evolution in the minority game: A multi-round strategy experiment," Games and Economic Behavior, Elsevier, vol. 86(C), pages 77-95.
    12. Mello, Bernardo A. & Cajueiro, Daniel O., 2008. "Minority games, diversity, cooperativity and the concept of intelligence," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(2), pages 557-566.
    13. Giovanna Devetag & Francesca Pancotto & Thomas Brenner, 2011. "The Minority Game Unpacked: Coordination and Competition in a Team-based Experiment," LEM Papers Series 2011/18, Laboratory of Economics and Management (LEM), Sant'Anna School of Advanced Studies, Pisa, Italy.
    14. Cherkashin, Dmitriy & Farmer, J. Doyne & Lloyd, Seth, 2009. "The reality game," Journal of Economic Dynamics and Control, Elsevier, vol. 33(5), pages 1091-1105, May.
      • Dmitriy Cherkashin & J. Doyne Farmer & Seth Lloyd, 2009. "The Reality Game," Papers 0902.0100, arXiv.org, revised Feb 2009.
    15. 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.
    16. Chenge Zhu & Guang Yang & Kenan An & Jiping Huang, 2014. "The Leverage Effect on Wealth Distribution in a Controllable Laboratory Stock Market," PLOS ONE, Public Library of Science, vol. 9(6), pages 1-10, June.
    17. Pietro Dindo & Jan Tuinstra, 2011. "A Class of Evolutionary Models for Participation Games with Negative Feedback," Computational Economics, Springer;Society for Computational Economics, vol. 37(3), pages 267-300, March.
    18. Giorgio Fagiolo & Marco Valente, 2005. "Minority Games, Local Interactions, and Endogenous Networks," Computational Economics, Springer;Society for Computational Economics, vol. 25(1), pages 41-57, February.
    19. Shu-Heng Chen & Umberto Gostoli, 2017. "Coordination in the El Farol Bar problem: The role of social preferences and social networks," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 12(1), pages 59-93, April.
    20. 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).

    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:2101.07760. 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.