{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T03:02:52Z","timestamp":1760151772796,"version":"build-2065373602"},"reference-count":51,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,4,20]],"date-time":"2022-04-20T00:00:00Z","timestamp":1650412800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>The Kolkata Paise Restaurant Problem is a challenging game in which n agents decide where to have lunch during their break. The game is not trivial because there are exactly n restaurants, and each restaurant can accommodate only one agent. We study this problem from a new angle and propose a novel strategy that results in greater utilization. Adopting a spatially distributed approach where the restaurants are uniformly distributed in the entire city area makes it possible for every agent to visit multiple restaurants. For each agent, the situation resembles that of the iconic traveling salesman, who must compute an optimal route through n cities. We rigorously prove probabilistic formulas that confirm the advantages of this policy and the increase in utilization. The derived equations generalize formulas that were previously known in the literature, which can be seen as special cases of our results.<\/jats:p>","DOI":"10.3390\/g13030033","type":"journal-article","created":{"date-parts":[[2022,4,20]],"date-time":"2022-04-20T02:04:22Z","timestamp":1650420262000},"page":"33","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Distributed Kolkata Paise Restaurant Game"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3607-9569","authenticated-orcid":false,"given":"Kalliopi","family":"Kastampolidou","sequence":"first","affiliation":[{"name":"Department of Informatics, Ionian University, 49100 Corfu, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0467-796X","authenticated-orcid":false,"given":"Christos","family":"Papalitsas","sequence":"additional","affiliation":[{"name":"Department of Informatics, Ionian University, 49100 Corfu, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3741-1271","authenticated-orcid":false,"given":"Theodore","family":"Andronikos","sequence":"additional","affiliation":[{"name":"Department of Informatics, Ionian University, 49100 Corfu, Greece"}]}],"member":"1968","published-online":{"date-parts":[[2022,4,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1287\/trsc.1030.0079","article-title":"Traveling Salesman Problems with Profits","volume":"39","author":"Feillet","year":"2005","journal-title":"Transp. Sci."},{"doi-asserted-by":"crossref","unstructured":"Chakrabarti, B.K. (2007). Kolkata restaurant problem as a generalised el farol bar problem. Econophysics of Markets and Business Networks, Springer.","key":"ref_2","DOI":"10.1007\/978-88-470-0665-2_18"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2420","DOI":"10.1016\/j.physa.2009.02.039","article-title":"The Kolkata Paise Restaurant problem and resource utilization","volume":"388","author":"Chakrabarti","year":"2009","journal-title":"Phys. A Stat. Mech. Appl."},{"doi-asserted-by":"crossref","unstructured":"Ghosh, A., Chakrabarti, A.S., and Chakrabarti, B.K. (2010). Kolkata Paise Restaurant problem in some uniform learning strategy limits. Econophysics and Economics of Games, Social Choices and Quantitative Techniques, Springer.","key":"ref_4","DOI":"10.1007\/978-88-470-1501-2_1"},{"doi-asserted-by":"crossref","unstructured":"Chakrabarti, B.K., Chatterjee, A., Ghosh, A., Mukherjee, S., and Tamir, B. (2017). Econophysics of the Kolkata Restaurant Problem and Related Games, Springer International Publishing.","key":"ref_5","DOI":"10.1007\/978-3-319-61352-9"},{"doi-asserted-by":"crossref","unstructured":"Banerjee, P., Mitra, M., and Mukherjee, C. (2013). Kolkata paise restaurant problem and the cyclically fair norm. Econophysics of Systemic Risk and Network Dynamics, Springer.","key":"ref_6","DOI":"10.1007\/978-88-470-2553-0_13"},{"doi-asserted-by":"crossref","unstructured":"Ghosh, A., Biswas, S., Chatterjee, A., Chakrabarti, A.S., Naskar, T., Mitra, M., and Chakrabarti, B.K. (2013). Kolkata paise restaurant problem: An introduction. Econophysics of Systemic Risk and Network Dynamics, Springer.","key":"ref_7","DOI":"10.1007\/978-88-470-2553-0_12"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.physa.2017.04.171","article-title":"Emergence of distributed coordination in the Kolkata paise restaurant problem with finite information","volume":"483","author":"Ghosh","year":"2017","journal-title":"Phys. A Stat. Mech. Appl."},{"doi-asserted-by":"crossref","unstructured":"Yang, P., Iyer, K., and Frazier, P.I. (2016, January 11\u201315). Mean field equilibria for competitive exploration in resource sharing settings. Proceedings of the 25th International Conference on World Wide Web, Montreal, QC, Canada.","key":"ref_9","DOI":"10.1145\/2872427.2883011"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1140\/epjb\/e2016-70464-0","article-title":"Self-organization in a distributed coordination game through heuristic rules","volume":"89","author":"Agarwal","year":"2016","journal-title":"Eur. Phys. J. B"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/game.1996.0027","article-title":"Congestion games with player-specific payoff functions","volume":"13","author":"Milchtaich","year":"1996","journal-title":"Games Econ. Behav."},{"key":"ref_12","first-page":"1","article-title":"Extending Kolkata Paise Restaurant Problem to Dynamic Matching in Mobility Markets","volume":"4","author":"Martin","year":"2019","journal-title":"Jr. Manag. Sci."},{"doi-asserted-by":"crossref","unstructured":"Abergel, F., Chakrabarti, B.K., Chakraborti, A., and Ghosh, A. (2012). Econophysics of Systemic Risk and Network Dynamics, Springer.","key":"ref_13","DOI":"10.1007\/978-88-470-2553-0"},{"unstructured":"Park, T., and Saad, W. (November, January 29). Kolkata paise restaurant game for resource allocation in the internet of things. Proceedings of the 51st Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA.","key":"ref_14"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"083116","DOI":"10.1063\/5.0004816","article-title":"Phase transition in the Kolkata Paise Restaurant problem","volume":"30","author":"Sinha","year":"2020","journal-title":"Chaos Interdiscip. J. Nonlinear Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1052","DOI":"10.1103\/PhysRevLett.82.1052","article-title":"Quantum strategies","volume":"82","author":"Meyer","year":"1999","journal-title":"Phys. Rev. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3077","DOI":"10.1103\/PhysRevLett.83.3077","article-title":"Quantum games and quantum strategies","volume":"83","author":"Eisert","year":"1999","journal-title":"Phys. Rev. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"6286","DOI":"10.1038\/srep06286","article-title":"Entanglement Guarantees Emergence of Cooperation in Quantum Prisoner\u2019s Dilemma Games on Networks","volume":"4","author":"Li","year":"2014","journal-title":"Sci. Rep."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"23024","DOI":"10.1038\/srep23024","article-title":"A novel framework of classical and quantum prisoner\u2019s dilemma games on coupled networks","volume":"6","author":"Deng","year":"2016","journal-title":"Sci. Rep."},{"doi-asserted-by":"crossref","unstructured":"Giannakis, K., Theocharopoulou, G., Papalitsas, C., Fanarioti, S., and Andronikos, T. (2019). Quantum Conditional Strategies and Automata for Prisoners\u2019 Dilemmata under the EWL Scheme. Appl. Sci., 9.","key":"ref_20","DOI":"10.20944\/preprints201905.0366.v1"},{"doi-asserted-by":"crossref","unstructured":"Andronikos, T., Sirokofskich, A., Kastampolidou, K., Varvouzou, M., Giannakis, K., and Singh, A. (2018). Finite Automata Capturing Winning Sequences for All Possible Variants of the PQ Penny Flip Game. Mathematics, 6.","key":"ref_21","DOI":"10.3390\/math6020020"},{"doi-asserted-by":"crossref","unstructured":"Andronikos, T., and Sirokofskich, A. (2021). The connection between the PQ penny flip game and the dihedral groups. Mathematics, 9.","key":"ref_22","DOI":"10.3390\/math9101115"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"586","DOI":"10.3390\/computation3040586","article-title":"Dominant Strategies of Quantum Games on Quantum Periodic Automata","volume":"3","author":"Giannakis","year":"2015","journal-title":"Computation"},{"doi-asserted-by":"crossref","unstructured":"Andronikos, T., and Stefanidakis, M. (2022). A two-party quantum parliament. Algorithms, 15.","key":"ref_24","DOI":"10.3390\/a15020062"},{"doi-asserted-by":"crossref","unstructured":"Kastampolidou, K., Nikiforos, M.N., and Andronikos, T. (2020). A Brief Survey of the Prisoners\u2019 Dilemma Game and Its Potential Use in Biology. Advances in Experimental Medicine and Biology, Springer International Publishing.","key":"ref_25","DOI":"10.1007\/978-3-030-32622-7_29"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1063\/1.4773171","article-title":"Strategies in a symmetric quantum Kolkata restaurant problem","volume":"1508","author":"Sharif","year":"2012","journal-title":"AIP Conf. Proc."},{"doi-asserted-by":"crossref","unstructured":"Sharif, P., and Heydari, H. (2013). An introduction to multi-player, multi-choice quantum games: Quantum minority games & kolkata restaurant problems. Econophysics of Systemic Risk and Network Dynamics, Springer.","key":"ref_27","DOI":"10.1007\/978-88-470-2553-0_14"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s11128-012-0405-8","article-title":"Three-player quantum Kolkata restaurant problem under decoherence","volume":"12","author":"Ramzan","year":"2013","journal-title":"Quantum Inf. Process."},{"unstructured":"Voigt, B.F. (1981). Der Handlungsreisende, wie er sein soll und was er zu thun hat, um Auftr\u00e4ge zu erhalten und eines gl\u00fccklichen\nErfolgs in seinen Gesch\u00e4ften gewiss zu zu sein. Commis-Voageur, Ilmenau, Verlag Schramm.","key":"ref_29"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/PL00011432","article-title":"Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut","volume":"90","author":"Ascheuer","year":"2001","journal-title":"Math. Program."},{"doi-asserted-by":"crossref","unstructured":"Gutin, G., and Punnen, A.P. (2006). The Traveling Salesman Problem and Its Variations, Springer Science & Business Media.","key":"ref_31","DOI":"10.1007\/b101971"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s11047-008-9098-4","article-title":"A survey on metaheuristics for stochastic combinatorial optimization","volume":"8","author":"Bianchi","year":"2009","journal-title":"Nat. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/937503.937505","article-title":"Metaheuristics in combinatorial optimization: Overview and conceptual comparison","volume":"35","author":"Blum","year":"2003","journal-title":"ACM Comput. Surv. (CSUR)"},{"doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Giannakis, K., Andronikos, T., Theotokis, D., and Sifaleras, A. (2015, January 6\u20138). Initialization methods for the TSP with Time Windows using Variable Neighborhood Search. Proceedings of the 6th International Conference on Information, Intelligence, Systems and Applications (IISA 2015), Corfu, Greece.","key":"ref_34","DOI":"10.1109\/IISA.2015.7388106"},{"doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Karakostas, P., and Kastampolidou, K. (2017). A Quantum Inspired GVNS: Some Preliminary Results. Advances in Experimental Medicine and Biology, Springer International Publishing.","key":"ref_35","DOI":"10.1007\/978-3-319-56246-9_23"},{"doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Karakostas, P., Andronikos, T., Sioutas, S., and Giannakis, K. (2018). Combinatorial GVNS (General Variable Neighborhood Search) Optimization for Dynamic Garbage Collection. Algorithms, 11.","key":"ref_36","DOI":"10.3390\/a11040038"},{"unstructured":"Papalitsas, C., Karakostas, P., Giannakis, K., Sifaleras, A., and Andronikos, T. (2017, January 8\u201310). Initialization methods for the TSP with Time Windows using qGVNS. Proceedings of the 6th International Symposium on Operational Research, OR in the Digital Era\u2014ICT Challenges, Thessaloniki, Greece.","key":"ref_37"},{"doi-asserted-by":"crossref","unstructured":"Papalitsas, C., and Andronikos, T. (2019). Unconventional GVNS for Solving the Garbage Collection Problem with Time Windows. Technologies, 7.","key":"ref_38","DOI":"10.3390\/technologies7030061"},{"doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Andronikos, T., and Karakostas, P. (2019). Studying the Impact of Perturbation Methods on the Efficiency of GVNS for the ATSP. Variable Neighborhood Search, Springer International Publishing.","key":"ref_39","DOI":"10.1007\/978-3-030-15843-9_22"},{"doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Karakostas, P., and Andronikos, T. (2019). A Performance Study of the Impact of Different Perturbation Methods on the Efficiency of GVNS for Solving TSP. Appl. Syst. Innov., 2.","key":"ref_40","DOI":"10.3390\/asi2040031"},{"doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Andronikos, T., Giannakis, K., Theocharopoulou, G., and Fanarioti, S. (2019). A QUBO Model for the Traveling Salesman Problem with Time Windows. Algorithms, 12.","key":"ref_41","DOI":"10.20944\/preprints201909.0154.v1"},{"doi-asserted-by":"crossref","unstructured":"Mertens, J.F. (1989). Supergames. Game Theory, Springer.","key":"ref_42","DOI":"10.1007\/978-1-349-20181-5_29"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.ejor.2010.09.010","article-title":"Traveling salesman problem heuristics: Leading methods, implementations and latest advances","volume":"211","author":"Rego","year":"2011","journal-title":"Eur. J. Oper. Res."},{"unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. (1985). The Traveling Salesman Problem, John Wiley & Sons.","key":"ref_44"},{"doi-asserted-by":"crossref","unstructured":"Pitman, J. (1993). Probability, Springer.","key":"ref_45","DOI":"10.1007\/978-1-4612-4374-8"},{"doi-asserted-by":"crossref","unstructured":"Klenke, A. (2014). Probability Theory, Springer.","key":"ref_46","DOI":"10.1007\/978-1-4471-5361-0"},{"unstructured":"Munkres, J. (2000). Topology, Prentice Hall, Inc.","key":"ref_47"},{"doi-asserted-by":"crossref","unstructured":"DasGupta, A. (2010). Fundamentals of Probability: A First Course, Springer.","key":"ref_48","DOI":"10.1007\/978-1-4419-5780-1"},{"unstructured":"Kobusingye, O.C., Hyder, A.A., Bishai, D., Joshipura, M., Hicks, E.R., and Mock, C. (2006). Emergency medical services. Disease Control Priorities in Developing Countries, World Bank Publications. [2nd ed.].","key":"ref_49"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.trc.2018.11.007","article-title":"A cost-minimization model for bus fleet allocation featuring the tactical generation of short-turning and interlining options","volume":"98","author":"Gkiotsalitis","year":"2019","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1016\/j.ejor.2013.02.025","article-title":"A metaheuristic for the school bus routing problem with bus stop selection","volume":"229","author":"Schittekat","year":"2013","journal-title":"Eur. J. Oper. Res."}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/13\/3\/33\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:57:10Z","timestamp":1760137030000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/13\/3\/33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,20]]},"references-count":51,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["g13030033"],"URL":"https:\/\/doi.org\/10.3390\/g13030033","relation":{},"ISSN":["2073-4336"],"issn-type":[{"type":"electronic","value":"2073-4336"}],"subject":[],"published":{"date-parts":[[2022,4,20]]}}}