El Farol Bar problem

El Farol located on Canyon Road, Santa Fe, New Mexico

The El Farol bar problem is a problem in game theory. Based on a bar in Santa Fe, New Mexico, it was created in 1994 by W. Brian Arthur.

The problem (without the name of El Farol Bar) was formulated and solved dynamically six years earlier by B. A. Huberman and T. Hogg in "The Ecology of Computation", Studies in Computer Science and Artificial Intelligence, North Holland publisher, page 99. 1988.

The problem is as follows: There is a particular, finite population of people. Every Thursday night, all of these people want to go to the El Farol Bar. However, the El Farol is quite small, and it's no fun to go there if it's too crowded. So much so, in fact, that the preferences of the population can be described as follows:

If less than 60% of the population go to the bar, they'll all have a better time than if they stayed at home.
If more than 60% of the population go to the bar, they'll all have a worse time than if they stayed at home.

Unfortunately, it is necessary for everyone to decide at the same time whether they will go to the bar or not. They cannot wait and see how many others go on a particular Thursday before deciding to go themselves on that Thursday.

One aspect of the problem is that, no matter what method each person uses to decide if they will go to the bar or not, if everyone uses the same pure strategy it is guaranteed to fail. If everyone uses the same deterministic method, then if that method suggests that the bar will not be crowded, everyone will go, and thus it will be crowded; likewise, if that method suggests that the bar will be crowded, nobody will go, and thus it will not be crowded. Often the solution to such problems in game theory is to permit each player to use a mixed strategy, where a choice is made with a particular probability. In the case of 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 that is a function of the number of players, the threshold for crowdedness, and the relative utility of going to a crowded or an uncrowded bar compared to staying home. There are also multiple Nash equilibria where 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 people are allowed to communicate with each other before deciding to go to the bar. However, they are not required to tell the truth.

Minority game

One variant of the El Farol Bar problem is the minority game proposed by Yi-Cheng Zhang and Damien Challet from the University of Fribourg. In the minority game, an odd number of players each must choose one of two choices independently at each turn.^[3]

The players who end up on the minority side win. While the El Farol Bar problem was originally formulated to analyze a decision-making method other than deductive rationality, the minority game examines the characteristic of the game that no single deterministic strategy may be adopted by all participants in equilibrium. Allowing for mixed strategies in the single-stage minority game produces a unique symmetric Nash equilibrium, which is for each player to choose each action with 50% probability, as well as multiple equilibria that are not symmetric.

The minority game was featured in the manga Liar Game. In that multi-stage minority game, the majority was eliminated from the game until only one player was left. Players were shown engaging in cooperative strategies.

Kolkata Paise Restaurant Problem

Another variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem ^[4]^[5] ^[6] ^[7]^[8] ^[9] where the number of choices (n) as well as the number of players (N) are (macroscopically) large; typically n = N (while in the El Farol Bar Problem n = 2, N is macroscopically large). Both are repetitive and information regarding the history of choices made by different players for different restaurants are available to every one. For the choices for a single restaurant on any evening by more than one player, one is randomly selected from them and served food (payoff = 1) while others lose (payoff = 0). Hence, while each player gains a point (payoff) if her choice of the restaurant any evening is unique (not made by other players on the same evening), the resource utilization is maximised when each restaurant is chosen by at least one player.

In Kolkata there were very cheap and fixed rate “Paise Restaurants” that were popular among the daily labourers in the city. During lunch hours, the labourers used to walk (to save the transport costs) to one of these restaurants and would miss lunch if they got to a restaurant where there were too many customers. Walking down to the next restaurant would mean failing to report back to work on time! Paise is the smallest Indian coin and there were indeed some well-known rankings of these restaurants, as some of them would offer tastier items compared to the others. A more general example of such a problem would be when the society provides hospitals (and beds) in every locality but the local patients go to hospitals of better rank (commonly perceived) elsewhere, thereby competing with the local patients of those hospitals. Unavailability of treatment in time may be considered as lack of the service for those people and consequently as (social) wastage of service by those unattended hospitals.

The statistics of individual pay-offs for the adopted strategies and the statistics for the social utilization (ratio of the attended restaurants on any evening and N) of course depends on n/N and has an average value dependent of the strategies adopted by the players. It is seen that a stochastic strategy with probability of choosing the same restaurant(as the one chosen last evening) going inversely with the number of players who made the same choice last evening, and choosing others with equal probability, gives better result (giving utilization fraction about 0.79) than deterministic or simple random choice (noise trader) (with utilization fraction = 1 - exp[-1] ~ 0.63) strategies.

External links

References

Arthur, W. Brian (1994). "Inductive Reasoning and Bounded Rationality" (PDF). American Economic Review (Papers and Proceedings). 84: 406–411. Retrieved 2014-12-13.

↑ 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". 6.24. Princeton University Press: 134.
↑ 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: 2420–2426.
↑ Asim Ghosh, Bikas K. Chakrabarti. "Kolkata Paise Restaurant (KPR) Problem". Wolfram Alpha.
↑ A. Ghosh, A. Chatterjee, M. Mitra, B. K. Chakrabarti (2010). "Statistics of the Kolkata Paise Restaurant Problem". New Journal of Physics. 12: 075033. doi:10.1088/1367-2630/12/7/075033.
↑ 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: 021116. doi:10.1103/physreve.85.021116.
↑ Frédéric Abergel, Bikas K. Chakrabarti, Anirban Chakraborti, Asim Ghosh. "Econophysics of Systemic Risk and Network Dynamics" (PDF). 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. doi:10.1016/j.physrep.2014.09.006.

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game Potential game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the 10/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.