El Farol Bar problem

Image:El Farol Restaurant and Cantina, Santa Fe NM.jpg}}]]

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.

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.{{cite web

| url=https://www.pure.ed.ac.uk/ws/portalfiles/portal/20037196/The_El_Farol_Bar_Problem_Revisited.pdf

| title=The El Farol Bar Problem Revisited: Reinforcement Learning in a Potential Game

| first=Duncan

| last=Whitehead

| date=2008-09-17

| publisher=University of Edinburgh School of Economics

| access-date=2014-12-13}} Several variants are considered in Game Theory Evolving by Herbert Gintis.{{cite book

| title=Game Theory Evolving

| first=Herbert

| last=Gintis

| publisher=Princeton University Press

| volume=6

| issue=24

| page=134

| date=2009

| isbn=978-0-691-14051-3}}

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."The Ecology of Computation", Studies in Computer Science and Artificial Intelligence, North Holland publisher, page 99. 1988.

Minority game

A variant is the Minority Game proposed by Yi-Cheng Zhang and Damien Challet from the University of Fribourg.D. Challet, M. Marsili, Y.-C. Zhang, Minority Games: Interacting Agents in Financial Markets, Oxford University Press, Oxford (2005) 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|date=May 2021}}

Kolkata Paise Restaurant Problem

Another variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem (KPR),{{cite journal

| title=The Kolkata Paise Restaurant problem and resource utilization

|author=A. S. Chakrabarti |author2=B. K. Chakrabarti |author3=A. Chatterjee |author4=M. Mitra

| journal=Physica A

| volume=388

| issue=12

| pages=2420–2426

| date=2009

| doi=10.1016/j.physa.2009.02.039| arxiv=0711.1639| bibcode=2009PhyA..388.2420C| s2cid=53310941

}}{{cite web

| url=http://demonstrations.wolfram.com/KolkataPaiseRestaurantKPRProblem

| title=Kolkata Paise Restaurant (KPR) Problem

| author=Asim Ghosh, Bikas K. Chakrabarti

| publisher=Wolfram Alpha}}{{cite journal

| title=Phase transition in crowd dynamics of resource allocation

| journal=Physical Review E

| volume=85| issue=2

|page= 021116

| doi=10.1103/physreve.85.021116

| date=2012| pmid=22463162

| arxiv=1109.2541| bibcode=2012PhRvE..85b1116G| s2cid=26159915

}}{{cite book

| url=http://www.saha.ac.in/cmp/camcs/combined.pdf

| title=Econophysics of Systemic Risk and Network Dynamics

|author=Frédéric Abergel |author2=Bikas K. Chakrabarti |author3=Anirban Chakraborti |author4=Asim Ghosh

| doi=10.1007/978-88-470-2553-0

| isbn=978-88-470-2552-3| series=New Economic Windows

| year=2013

| bibcode=2013esrn.book.....A

}}{{cite journal

| title=Statistical Mechanics of Competitive Resource Allocation using Agent-Based Models

| journal=Physics Reports

| volume=552

| pages= 1–25

| date=2015

| doi = 10.1016/j.physrep.2014.09.006 | arxiv=1305.2121

| bibcode=2015PhR...552....1C

| s2cid=42076636

}}{{cite book

| url=https://www.springer.com/in/book/9783319613512

| title=Econophysics of the Kolkata Restaurant Problem and Related Games: Classical and Quantum Strategies for Multi-agent, Multi-choice Repetitive Games

| date=27 July 2017

| publisher=Springer

| isbn=978-3-319-61351-2}} 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|date=May 2021}}

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.{{cite journal| title= Statistics of the Kolkata Paise Restaurant problem |author=A. Ghosh |author2=A. Chatterjee |author3=M. Mitra |author4=B. K. Chakrabarti | journal=New Journal of Physics | volume=12 | page=075033 | date=2010 |issue=7 | doi=10.1088/1367-2630/12/7/075033| doi-access=free | arxiv=1003.2103 }} 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 - ¹/_e ≈ 0.63.{{cite journal | title= Phase transition in the Kolkata Paise Restaurant problem |author=A. Sinha |author2=B. K. Chakrabarti |journal= Chaos | volume=30 | page=083116 | date=2020 |issue=8 | doi=10.1063/5.0004816| arxiv=1905.13206 }} Increased utilization for customers having allowance for local optimization search using Traveling Salesman Problem type algorithms have also been studied.{{cite journal | title= The Distributed Kolkata Paise Restaurant Game |author=K. Kastampolidou |author2=C. Papalitsas |author3=T. Andronikos |journal= Games | volume=13 | page=33 | date=2022 |issue=3 | doi=10.3390/g13030033 |doi-access=free }} Extensions of KPR for on-call car hire problems have been explored in.{{cite journal | title= Extending Kolkata Paise Restaurant problem to dynamic matching in mobility markets |author=L. Martin | journal= Junior Manag. Sci. | volume=4 | pages=1–34 | date=2017 | doi=10.5282/jums/v4i1pp1-34}}{{cite book | url= https://mediatum.ub.tum.de/doc/1437330/1437330.pdf | title= The vehicle for hire problem: a generalized Kolkata Paise Restaurant problem; Proc. Workshop on Information Technology and Systems |author=L. Martin |author2=P. Karaenke | date=2017}} Stability of the KPR, induced by the introduction of dining clubs have also studied.{{cite journal | title= Stability of dining clubs in the Kolkata Paise Restaurant Problem with and without cheating |author=A. Harlalka |author2=A. Belmonte |author3=C. Griffin | journal= Physica A | volume=620 | page=128767 | date=2023 | doi=10.1016/j.physa.2023.128767| arxiv=2302.14142 }}

Extensions to quantum games for three player KPR have been studied;{{cite journal | title= Strategies in a symmetric quantum Kolkata restaurant problem |author=P. Sharif |author2=H. Heydari | journal= AIP Conference Proceedings | volume=1508 | pages=492–496 | date=2012 | doi=10.1063/1.4773171| arxiv=1212.6727}}{{cite journal| title= Three-player quantum Kolkata restaurant problem under decoherence |author=M. Ramzan | journal= Quantum Inform. Process. | volume=12 | page=577 | date=2013 | doi=10.1007/s11128-012-0405-8| arxiv=1111.3913 }} see {{cite journal| title= Stochastic Learning in Kolkata Paise Restaurant Problem: Classical and Quantum Strategies |author=B. K. Chakrabarti |author2=A. Rajak |author3=A. Sinha | journal= Front. Artif. Intell. | volume=5 | pages=874061 | date=2022 | doi= 10.3389/frai.2022.874061 |doi-access=free | pmc=9181993 }} for a recent review.

References

External links

[http://estebanmoro.org/post/2004-08-31-the-minority-game-an-introductory-guide/ An Introductory Guide to the Minority Game]
[http://news.softpedia.com/news/Minority-Games-38625.shtml Minority Games] (a popularization account)
[http://xstructure.inr.ac.ru/x-bin/theme3.py?level=1&index1=117820 Minority game on arxiv.org]
[http://elfarolsantafe.com El Farol bar in Santa Fe, New Mexico]
[http://jabm.sourceforge.net/doc/easss2013/EASSS_lab_elfarolbar.pdf The El Farol Bar problem in Java] using [http://jabm.sourceforge.net/ The Java Agent-Based Modelling Toolkit (JABM)]
[http://demonstrations.wolfram.com/KolkataPaiseRestaurantKPRProblem/ Kolkata Paise Restaurant (KPR) Problem: Wolfram Demonstrations]

Category:Non-cooperative games

El Farol Bar problem

Minority game

Kolkata Paise Restaurant Problem

References

Further reading

External links