El Farol bar problem
Encyclopedia
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 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:
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 symmetricSeveral variants are considered in .
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.
. In the minority game, an odd number of players each must choose one of two choices independently at each turn.
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.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
. Based on a bar in Santa Fe, New Mexico
Santa Fe, New Mexico
Santa Fe is the capital of the U.S. state of New Mexico. It is the fourth-largest city in the state and is the seat of . Santa Fe had a population of 67,947 in the 2010 census...
, it was created in 1994 by W. Brian Arthur
W. Brian Arthur
William Brian Arthur is an economist credited with influencing and describing the modern theory of increasing returns. He has lived and worked in Northern California for many years. He is an authority on economics in relation to complexity theory, technology and financial markets...
.
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
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
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 symmetricSeveral variants are considered in .
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 FribourgUniversity of Fribourg
The University of Fribourg is a university in the city of Fribourg, Switzerland.The roots of the University can be traced back to 1582, when the notable Jesuit Peter Canisius founded the Collège Saint-Michel in the City of Fribourg. In 1763, an Academy of law was founded by the state of Frobourg...
. In the minority game, an odd number of players each must choose one of two choices independently at each turn.
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
Liar Game
is a Japanese manga series originally written and illustrated by Shinobu Kaitani. The manga was first serialized in 2005 in the Japanese manga magazine Weekly Young Jump, published by Shueisha...
. 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.