fbpx
Wikipedia

El Farol Bar problem

January 01, 1970

The El Farol bar problem is a problem in game theory. Every Thursday night, a fixed population want to go have fun at the El Farol Bar, unless it's too crowded.

  • If less than 60% of the population go to the bar, they'll all have more fun than if they stayed home.
  • If more than 60% of the population go to the bar, they'll all have less fun than if they stayed home.
El Farol located on Canyon Road, Santa Fe, New Mexico

Everyone must decide at the same time whether to go or not, with no knowledge of others' choices.

Paradoxically, if everyone uses a deterministic pure strategy which is symmetric (same strategy for all players), it is guaranteed to fail no matter what it is. If the strategy suggests it will not be crowded, everyone will go, and thus it will be crowded; but if the strategy suggests it will be crowded, nobody will go, and thus it will not be crowded, but again no one will have fun. Better success is possible with a probabilistic mixed strategy. For the single-stage El Farol Bar problem, there exists a unique symmetric Nash equilibrium mixed strategy where all players choose to go to the bar with a certain probability, determined according to the number of players, the threshold for crowdedness, and the relative utility of going to a crowded or uncrowded bar compared to staying home. There are also multiple Nash equilibria in which one or more players use a pure strategy, but these equilibria are not symmetric.[1] Several variants are considered in Game Theory Evolving by Herbert Gintis.[2]

In some variants of the problem, the players are allowed to communicate before deciding to go to the bar. However, they are not required to tell the truth.

Named after a bar in Santa Fe, New Mexico, the problem was created in 1994 by W. Brian Arthur. However, under another name, the problem was formulated and solved dynamically six years earlier by B. A. Huberman and T. Hogg.[3]

Minority game edit

A variant is the Minority Game proposed by Yi-Cheng Zhang and Damien Challet from the University of Fribourg.[4] An odd number of players each must make a binary choice independently at each turn, and the winners are those players who end up on the minority side. As in the El Farol Bar problem, no single (symmetric) deterministic strategy can give an equilibrium, but for mixed strategies, there is a unique symmetric Nash equilibrium (each player chooses with 50% probability), as well as multiple asymmetric equilibria.

A multi-stage, cooperative Minority Game was featured in the manga Liar Game, in which the majority was repeatedly eliminated until only one player was left.[citation needed]

Kolkata Paise Restaurant Problem edit

Another variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem (KPR),[5][6][7][8][9][10] 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.[11] 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.[12] Increased utilization for customers having allowance for local optimization search using Traveling Salesman Problem type algorithms have also been studied.[13] Extensions of KPR for on-call car hire problems have been explored in.[14][15] Stability of the KPR, induced by the introduction of dining clubs have also studied.[16]

Extensions to quantum games for three player KPR have been studied;[17][18] see [19] for a recent review.

References edit

  1. ^ Whitehead, Duncan (2008-09-17). "The El Farol Bar Problem Revisited: Reinforcement Learning in a Potential Game" (PDF). University of Edinburgh School of Economics. Retrieved 2014-12-13.
  2. ^ Gintis, Herbert (2009). Game Theory Evolving. Vol. 6. Princeton University Press. p. 134. ISBN 978-0-691-14051-3.
  3. ^ "The Ecology of Computation", Studies in Computer Science and Artificial Intelligence, North Holland publisher, page 99. 1988.
  4. ^ D. Challet, M. Marsili, Y.-C. Zhang, Minority Games: Interacting Agents in Financial Markets, Oxford University Press, Oxford (2005)
  5. ^ 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.
  6. ^ Asim Ghosh, Bikas K. Chakrabarti. "Kolkata Paise Restaurant (KPR) Problem". Wolfram Alpha.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ 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. doi:10.1088/1367-2630/12/7/075033.
  12. ^ A. Sinha; B. K. Chakrabarti (2020). "Phase transition in the Kolkata Paise Restaurant problem". Chaos. 30 (8): 083116. arXiv:1905.13206. doi:10.1063/5.0004816.
  13. ^ K. Kastampolidou; C. Papalitsas; T. Andronikos (2022). "The Distributed Kolkata Paise Restaurant Game". Games. 13 (3): 33. doi:10.3390/g13030033.
  14. ^ 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.
  15. ^ L. Martin; P. Karaenke (2017). The vehicle for hire problem: a generalized Kolkata Paise Restaurant problem; Proc. Workshop on Information Technology and Systems (PDF).
  16. ^ 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. doi:10.1016/j.physa.2023.128767.
  17. ^ P. Sharif; H. Heydari (2012). "Strategies in a symmetric quantum Kolkata restaurant problem". AIP Conference Proceedings. 1508: 492–496. arXiv:1212.6727. doi:10.1063/1.4773171.
  18. ^ M. Ramzan (2013). "Three-player quantum Kolkata restaurant problem under decoherence". Quantum Inform. Process. 12: 577. arXiv:1111.3913. doi:10.1007/s11128-012-0405-8.
  19. ^ 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.

Further reading edit

  • Arthur, W. Brian (1994). (PDF). American Economic Review: Papers and Proceedings. 84: 406–411. Archived from the original (PDF) on 2015-02-20. Retrieved 2014-12-13.

External links edit

  • An Introductory Guide to the Minority Game
  • Minority Games (a popularization account)
  • Minority game on arxiv.org
  • El Farol bar in Santa Fe, New Mexico
  • The El Farol Bar problem in Java using The Java Agent-Based Modelling Toolkit (JABM)
  • Kolkata Paise Restaurant (KPR) Problem: Wolfram Demonstrations

January 01, 1970
farol, problem, farol, problem, problem, game, theory, every, thursday, night, fixed, population, want, have, farol, unless, crowded, less, than, population, they, have, more, than, they, stayed, home, more, than, population, they, have, less, than, they, stay. The El Farol bar problem is a problem in game theory Every Thursday night a fixed population want to go have fun at the El Farol Bar unless it s too crowded If less than 60 of the population go to the bar they ll all have more fun than if they stayed home If more than 60 of the population go to the bar they ll all have less fun than if they stayed home El Farol located on Canyon Road Santa Fe New Mexico Everyone must decide at the same time whether to go or not with no knowledge of others choices Paradoxically if everyone uses a deterministic pure strategy which is symmetric same strategy for all players it is guaranteed to fail no matter what it is If the strategy suggests it will not be crowded everyone will go and thus it will be crowded but if the strategy suggests it will be crowded nobody will go and thus it will not be crowded but again no one will have fun Better success is possible with a probabilistic mixed strategy For the single stage El Farol Bar problem there exists a unique symmetric Nash equilibrium mixed strategy where all players choose to go to the bar with a certain probability determined according to the number of players the threshold for crowdedness and the relative utility of going to a crowded or uncrowded bar compared to staying home There are also multiple Nash equilibria in which one or more players use a pure strategy but these equilibria are not symmetric 1 Several variants are considered in Game Theory Evolving by Herbert Gintis 2 In some variants of the problem the players are allowed to communicate before deciding to go to the bar However they are not required to tell the truth Named after a bar in Santa Fe New Mexico the problem was created in 1994 by W Brian Arthur However under another name the problem was formulated and solved dynamically six years earlier by B A Huberman and T Hogg 3 Contents 1 Minority game 2 Kolkata Paise Restaurant Problem 3 References 4 Further reading 5 External linksMinority game editA variant is the Minority Game proposed by Yi Cheng Zhang and Damien Challet from the University of Fribourg 4 An odd number of players each must make a binary choice independently at each turn and the winners are those players who end up on the minority side As in the El Farol Bar problem no single symmetric deterministic strategy can give an equilibrium but for mixed strategies there is a unique symmetric Nash equilibrium each player chooses with 50 probability as well as multiple asymmetric equilibria A multi stage cooperative Minority Game was featured in the manga Liar Game in which the majority was repeatedly eliminated until only one player was left citation needed Kolkata Paise Restaurant Problem editAnother variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem KPR 5 6 7 8 9 10 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 11 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 12 Increased utilization for customers having allowance for local optimization search using Traveling Salesman Problem type algorithms have also been studied 13 Extensions of KPR for on call car hire problems have been explored in 14 15 Stability of the KPR induced by the introduction of dining clubs have also studied 16 Extensions to quantum games for three player KPR have been studied 17 18 see 19 for a recent review References edit Whitehead Duncan 2008 09 17 The El Farol Bar Problem Revisited Reinforcement Learning in a Potential Game PDF University of Edinburgh School of Economics Retrieved 2014 12 13 Gintis Herbert 2009 Game Theory Evolving Vol 6 Princeton University Press p 134 ISBN 978 0 691 14051 3 The Ecology of Computation Studies in Computer Science and Artificial Intelligence North Holland publisher page 99 1988 D Challet M Marsili Y C Zhang Minority Games Interacting Agents in Financial Markets Oxford University Press Oxford 2005 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 Asim Ghosh Bikas K Chakrabarti Kolkata Paise Restaurant KPR Problem Wolfram Alpha 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 Frederic 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 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 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 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 doi 10 1088 1367 2630 12 7 075033 A Sinha B K Chakrabarti 2020 Phase transition in the Kolkata Paise Restaurant problem Chaos 30 8 083116 arXiv 1905 13206 doi 10 1063 5 0004816 K Kastampolidou C Papalitsas T Andronikos 2022 The Distributed Kolkata Paise Restaurant Game Games 13 3 33 doi 10 3390 g13030033 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 L Martin P Karaenke 2017 The vehicle for hire problem a generalized Kolkata Paise Restaurant problem Proc Workshop on Information Technology and Systems PDF 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 doi 10 1016 j physa 2023 128767 P Sharif H Heydari 2012 Strategies in a symmetric quantum Kolkata restaurant problem AIP Conference Proceedings 1508 492 496 arXiv 1212 6727 doi 10 1063 1 4773171 M Ramzan 2013 Three player quantum Kolkata restaurant problem under decoherence Quantum Inform Process 12 577 arXiv 1111 3913 doi 10 1007 s11128 012 0405 8 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 Further reading editArthur W Brian 1994 Inductive Reasoning and Bounded Rationality PDF American Economic Review Papers and Proceedings 84 406 411 Archived from the original PDF on 2015 02 20 Retrieved 2014 12 13 External links editAn Introductory Guide to the Minority Game Minority Games a popularization account Minority game on arxiv org El Farol bar in Santa Fe New Mexico The El Farol Bar problem in Java using The Java Agent Based Modelling Toolkit JABM Kolkata Paise Restaurant KPR Problem Wolfram Demonstrations Retrieved from https en wikipedia org w index php title El Farol Bar problem amp oldid 1211021045, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.