Jump to content

Draft:Kolkata Paise Restaurant Problem 2

From Wikipedia, the free encyclopedia

Another variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem (KPR),[1][2][3][4][5][6] named for the many cheap restaurants where laborers can grab a quick lunch, but may have to return to work hungry if their chosen restaurant is too crowded. Formally, a large number N of players each choose one of a large number n of restaurants, typically N = n (while in the El Farol Bar Problem, n = 2, including the stay-home option). At each restaurant, one customer at random is served lunch (payoff = 1) while all others lose (payoff = 0). The players do not know each others' choices on a given day, but the game is repeated daily, and the history of all players' choices is available to everyone. Optimally, each player chooses a different restaurant, but this is practically impossible without coordination, resulting in both hungry customers and unattended restaurants wasting capacity.[citation needed]

In a similar problem, there are hospital beds in every locality, but patients are tempted to go to prestigious hospitals out of their district. However, if too many patients go to a prestige hospital, some get no hospital bed at all, while additionally wasting the unused beds at their local hospitals.[7] Strategies are evaluated based on their aggregate payoff and/or the proportion of attended restaurants (utilization ratio). A leading stochastic strategy, with utilization ~0.79, 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.[8] Increased utilization for customers having allowance for local optimization search using Traveling Salesman Problem type algorithms have also been studied.[9] Extensions of KPR for on-call car hire problems have been explored in.[10][11] Stability of the KPR, induced by the introduction of dining clubs have also studied.[12]

Extensions to quantum games for three player KPR have been studied;[13][14] see[15] for a recent review.

References

[edit]
  1. ^ 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.
  2. ^ Asim Ghosh, Bikas K. Chakrabarti. "Kolkata Paise Restaurant (KPR) Problem". Wolfram Alpha.
  3. ^ 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.
  4. ^ 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.
  5. ^ A. Chakraborti; D. Challet; A. Chatterjee; M. Marsili; Y.-C. Zhang; B. K. Chakrabarti (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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ K. Kastampolidou; C. Papalitsas; T. Andronikos (2022). "The Distributed Kolkata Paise Restaurant Game". Games. 13 (3): 33. doi:10.3390/g13030033.
  10. ^ 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.
  11. ^ L. Martin; P. Karaenke (2017). The vehicle for hire problem: a generalized Kolkata Paise Restaurant problem; Proc. Workshop on Information Technology and Systems (PDF).
  12. ^ 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.
  13. ^ 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.
  14. ^ 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.
  15. ^ 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Draft:Kolkata_Paise_Restaurant_Problem_2&oldid=1299759222"