The Distributed Kolkata Paise Restaurant Game

Kalliopi Kastampolidou, Christos Papalitsas and Theodore Andronikos
Additional contact information
Kalliopi Kastampolidou: Department of Informatics, Ionian University, 49100 Corfu, Greece
Christos Papalitsas: Department of Informatics, Ionian University, 49100 Corfu, Greece
Theodore Andronikos: Department of Informatics, Ionian University, 49100 Corfu, Greece

Games, 2022, vol. 13, issue 3, 1-21

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

Keywords: Kolkata Paise Restaurant Problem; TSP; optimization; metaheuristics; probabilistic analysis; utilization (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2073-4336/13/3/33/pdf (application/pdf)
https://www.mdpi.com/2073-4336/13/3/33/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:13:y:2022:i:3:p:33-:d:797524

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().