Jump to content

Draft:Kolkata Paise Restaurant Problem

From Wikipedia, the free encyclopedia

The Kolkata Paise Restaurant Problem (KPR) is named after the old (early nineteen hundred, through seventies) very cheap fixed price (‘Paise’ used to be the lowest denomination of the Indian Rupee) and limited offer 'Paise Restaurants' in Kolkata (see e.g.,[1] for the few still surviving). It is an anti-coordination game model that describes how a large number of individuals (players) compete for limited resources without any mutual consultation or direct coordination. The problem becomes trivial (though gives full utilization of resources and that too from the first day; food for all the customers/players and maximum revenue for all the restaurants in zero learning or convergence time) when a non-playing coordinator or dictator asks every player to form a queue and to go to the restaurant corresponding to the position in the queue on the first day and shift by one restaurant position every successive day (maintaining the periodic boundary condition). The non-triviality of the problem comes when the individuals decide or choose independently (based on their own past experience of success or failure and information about the past crowd sizes in different restaurants) and tries to maximize their own pay-off (which also helps the restaurants to maximize their sales). The El Farol Bar problem corresponds to only two choices for each individual (to go to the bar or remain at home to avoid the over-crowded bar) for each individual. The KPR game[2][3][4][5][6][7] is therefore an extension of the El Farol Bar problem for many choices for each individual. If limited to two players only, it has got structural similarity with the Chicken (game) or Hawk-Dove games,[8] while the matching game-like algorithmic aspect of the full KPR problem can be compared with that of Gale-Shapley algorithm.[9]

Problem Definition

[edit]
  • There are N players (prospective customers) and n restaurants; typically N = n. Both N and n can be arbitrarily large.
  • Each day, customers independently choose a restaurant, based on their past experience of success or failure.
  • At each restaurant only one of the players arriving there (prospective customers) is randomly chosen and served (payoff = 1). The rest leave without food for that day (payoff = 0; no time/money left for another search).
  • Players do not know each other's choices but have access to historical data of past selections.
  • The ideal outcome is perfect coordination, where each player chooses and picks a different restaurant in short convergence time. However this becomes difficult (in absence parallel communication exchanges) in KPR game. This leads to inefficiencies (some restaurants overcrowded, others empty) or partial utilization. The KPR objective is to evolve the collective ‘parallel learning’ algorithms for maximizing the utilization fraction in minimum (preferably less than lnN order) time.

Real-World Applications

[edit]

The KPR model can describe various real-life resource allocation problems, such as:

  • Hospital Resource Allocation – Patients prefer top-rated hospitals, even if local hospitals have available beds. Overcrowding in top hospitals leaves some patients unattended, while other hospitals remain underutilized.[10]
  • Ride-Hailing Services – Passengers compete for taxis, sometimes overwhelming some areas while others remain unpopulated.[11][12]
  • Online Service Access – Users competing for limited online resources (e.g., booking slots, bandwidth allocation, computer job allocation problem in Internet of Things computer.[13]).
  • Dynamics of Dining Clubs in the KPR Problem.[14][8]
  • Designing benchmarking algorithms for AI.[9][15]

Strategies & Optimization

[edit]

Strategies are evaluated based on their aggregate payoff and/or the proportion of attended restaurants (utilization ratio). A leading stochastic strategy, with utilization fraction ~0.79,[10] gives each customer a probability p of choosing the same restaurant as yesterday (p varying inversely with the number of players who chose that restaurant yesterday), while choosing among other restaurants with uniform probability. This is a better result than deterministic algorithms or simple random choice (noise trader), with utilization fraction 1 - 1/e ≈ 0.63.[2][16] Increased utilization fraction for customers, each having a fixed low budget allowance for local search using Traveling Salesman Problem type algorithm, have also been studied.[17] Extensions of KPR for on-call car hire problems (restaurants effectively having also the options for moving to their chosen places) have been explored in[11][12] and see[18] for the mean field solution of a generalized KPR problem in the same resource competition in spatial settings of the vehicle-for-hire market. For application of KPR to optimized job allocation problems in Internet-of-Things, see.[13] Stability of the KPR, induced by the introduction of dining clubs have also studied.[14] One can see[19] for a study on the impact of expert opinions (or even of faiths) on such evolving mutually competing search strategies for the resources. See also[20] for application of KPR model to anthropological and sociological analysis of the models of polytheism.

Extensions to quantum games for three player KPR have been studied;[21][22] see[23] for a recent review. One may see[24] for an early attempt to exploit KPR type strategies for developing Artificial Intelligence or AI models. For a study of KPR-like approaches related to graph partitioning problem, see.[25]Recently the KPR game has been extended (to Musical Chair type games) and exploited,[15] announcing the creation of a new benchmark for evaluating the AI algorithms.

References

[edit]
  1. ^ J. Kishan (2021). "Pice hotels: A lifeline for Kolkata's hungry worker". BBC Travel: Food & Hospitality (June 10 Issue).
  2. ^ a b A. S. Chakrabarti; B. K. Chakrabarti; A. Chatterjee; M. Mitra (2009). "The Kolkata Paise Restaurant problem and resource utilization". Physica A. 388 (12): 2420–2426. arXiv:0711.1639. Bibcode:2009PhyA..388.2420C. doi:10.1016/j.physa.2009.02.039. S2CID 53310941.
  3. ^ Asim Ghosh, Bikas K. Chakrabarti (2011). "Kolkata Paise Restaurant (KPR) Problem". Wolfram Alpha.
  4. ^ A. Ghosh; D. D. Martino; A. Chatterjee; M. Marsili; B. K. Chakrabarti (2012). "Phase transition in crowd dynamics of resource allocation". Physical Review E. 85 (2): 021116. arXiv:1109.2541. Bibcode:2012PhRvE..85b1116G. doi:10.1103/physreve.85.021116. PMID 22463162. S2CID 26159915.
  5. ^ Frédéric Abergel; Bikas K. Chakrabarti; Anirban Chakraborti; Asim Ghosh (2013). Econophysics of Systemic Risk and Network Dynamics (PDF). New Economic Windows. Bibcode:2013esrn.book.....A. doi:10.1007/978-88-470-2553-0. ISBN 978-88-470-2552-3.
  6. ^ A. Chakraborti; D. Challet; A. Chatterjee; M. Marsili; Y.-C. Zhang; B. K. Chakrabartpi (2015). "Statistical Mechanics of Competitive Resource Allocation using Agent-Based Models". Physics Reports. 552: 1–25. arXiv:1305.2121. Bibcode:2015PhR...552....1C. doi:10.1016/j.physrep.2014.09.006. S2CID 42076636.
  7. ^ Bikas K Chakrabarti; Arnab Chatterjee; Asim Ghosh; Sudip Mukherjee; Boaz Tamir (27 July 2017). Econophysics of the Kolkata Restaurant Problem and Related Games: Classical and Quantum Strategies for Multi-agent, Multi-choice Repetitive Games. Springer. ISBN 978-3-319-61351-2.
  8. ^ a b A. Harlalka; C. Griffin (2025). "Multi-group dynamics with tolerant switching in the Kolkata Paise Restaurant problem with dining clubs". J. Phys. Complex. doi:10.1088/2632-072X/adc52e.
  9. ^ a b B. Picano; R. Fantacci (2024). "Efficient task offloading and resource allocation in an intelligent UAV-MEC system". IEEE Xplore.
  10. ^ a b A. Ghosh; A. Chatterjee; M. Mitra; B. K. Chakrabarti (2010). "Statistics of the Kolkata Paise Restaurant problem". New Journal of Physics. 12 (7): 075033. arXiv:1003.2103. Bibcode:2010NJPh...12g5033G. doi:10.1088/1367-2630/12/7/075033.
  11. ^ a b L. Martin (2017). "Extending Kolkata Paise Restaurant problem to dynamic matching in mobility markets". Junior Manag. Sci. 4: 1–34. doi:10.5282/jums/v4i1pp1-34.
  12. ^ a b L. Martin; P. Karaenke (2017). The vehicle for hire problem: a generalized Kolkata Paise Restaurant problem; Proc. Workshop on Information Technology and Systems (PDF).
  13. ^ a b T. Park; W. Saad (2017). "Kolkata paise restaurant game for resource allocation in the Internet of Things (51st Asilomar Conference on Signals, Systems & Computers)". IEEE Xplore. doi:10.1109/ACSSC.2017.8335666.
  14. ^ a b A. Harlalka; A. Belmonte; C. Griffin (2023). "Stability of dining clubs in the Kolkata Paise Restaurant Problem with and without cheating". Physica A. 620: 128767. arXiv:2302.14142. Bibcode:2023PhyA..62028767H. doi:10.1016/j.physa.2023.128767.
  15. ^ a b C. Santos-Lang; C. M. Homan (2025). "Musical Chairs: A new benchmark to evaluate AI (Blue Sky ideas)". arXiv:2503.20986 [cs.CY].
  16. ^ A. Sinha; B. K. Chakrabarti (2020). "Phase transition in the Kolkata Paise Restaurant problem". Chaos. 30 (8): 083116. arXiv:1905.13206. Bibcode:2020Chaos..30h3116S. doi:10.1063/5.0004816. PMID 32872841.
  17. ^ K. Kastampolidou; C. Papalitsas; T. Andronikos (2022). "The Distributed Kolkata Paise Restaurant Game". Games. 13 (3): 33. doi:10.3390/g13030033.
  18. ^ P. Yang; K. Iyer; P. Frazier (2018). "Mean Field Equilibria for Resource Competition in Spatial Settings". Stochastic Systems. 8 (4): 307–334. doi:10.1287/stsy.2018.0018.
  19. ^ C. Xu; G.-Q. Gu; P.M. Hui (2024). "Impacts of an expert's opinion on the collective performance of a competing population for limited resources". Chaos, Solitons & Fractals. 183: 114905. Bibcode:2024CSF...18314905X. doi:10.1016/j.chaos.2024.114905.
  20. ^ L. Gauthie (2024). "A strategic model of polytheism". Rationality and Society. 36 (4): 480–501. doi:10.1177/10434631241269525.
  21. ^ P. Sharif; H. Heydari (2012). "Strategies in a symmetric quantum Kolkata restaurant problem". AIP Conference Proceedings. 1508 (1): 492–496. arXiv:1212.6727. Bibcode:2012AIPC.1508..492S. doi:10.1063/1.4773171.
  22. ^ M. Ramzan (2013). "Three-player quantum Kolkata restaurant problem under decoherence". Quantum Inform. Process. 12 (1): 577. arXiv:1111.3913. Bibcode:2013QuIP...12..577R. doi:10.1007/s11128-012-0405-8.
  23. ^ B. K. Chakrabarti; A. Rajak; A. Sinha (2022). "Stochastic Learning in Kolkata Paise Restaurant Problem: Classical and Quantum Strategies". Front. Artif. Intell. 5: 874061. doi:10.3389/frai.2022.874061. PMC 9181993. PMID 35692940.
  24. ^ N. Alon; R. Meir; M. Tennenholtz (2013). "The Value of Ignorance about the Number of Players" (PDF). Proc. Twenty-Seventh AAAI Conference on Artificial Intelligence.
  25. ^ M. Anastos; O. Cooley; M. Kang; M. Kwan (2024). "Partitioning problems via random processes". Journal of the London Mathematical Society. 110 (6). doi:10.1112/jlms.70010.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Draft:Kolkata_Paise_Restaurant_Problem&oldid=1284186343"