Game Theory
The El Farol Bar Problem
“Oh that place. It’s so crowded nobody goes there anymore.” — Yogi Berra
The El Farol Bar Problem, sometimes known as the “Santa Fe Bar problem” (SFBP) is a constrained resource allocation problem for non-cooperating agents defined by economist William Brian Arthur (1945-) in 1994. The problem deals with ways of achieving an optimal collective resource allocation in situations where, if everyone uses the same pure strategy that strategy is guaranteed to fail no matter what it is.
Definition
The problem begins with explaining that on Thursday night every week 100 people decide independently whether or not to go to a bar in El Farol, Santa Fe that offers live Irish music. Each person knows that they will only have fun if a certain number of people show up. Namely:
- If less than 60 people go to the bar, they’ll all have more fun than if they stayed at home;
- If more than 60 people go to the bar, they’ll all have less fun than if they stayed at home;
Based on the definition of the problem by its originator W. Brian Arthur in his paper “Inductive Reasoning and Bounded Rationality” in The American Economic Review, we can summarize the problem in the following way:
The El Farol Bar Problem (Arthur, 1994)Agents: The number of people who are deciding whether or not to go is N = 100Limitation: Space in the bar is limited. There is no way of knowing how many people will show up in advanceCondition: The evening is considered enjoyable if less than 60% of the 100 agents show upDynamics: Guests deem it worthwhile going if they expect fewer than 60 guests to show up. There is no communication between guests ahead of timeInformation: The only information available is the numbers of people who came in the previous weeks
To study the problem, Arthur proposes a dynamic model which accounts for 100 agents who individually form predictors or hypotheses in the form of functions that map the past d weeks’ level of attendance onto the next. Thus, if in the last fourteen weeks the number of Thursday attendees at the bar was
…., 44, 78, 56, 15, 23, 67, 84, 34, 45, 76, 40, 56, 22, 35,
A potential attendee might reason to form hypotheses about the coming Thursday’s attendance, in ways such as:
- Attendance will be the same as last week [35]
- Attendance will mirror around 50 from last week [(50–35) + 50 = 65]
- Attendance will be the average of the last four weeks [(40+56+22+35)/4 ≈ 38]
- Attendance follows a 2-period cycle and so will be the same as two weeks ago [22]
- Attendance follows a monthly cycle and so will be the same as four weeks ago [40]
and so on.
Findings
To investigate which hypotheses and predictors work better, Arthur set up computer simulations in which he let each of the 100 agents pick between several dozen potential hypotheses, allowing each agent to change their strategy from week to week by varying amounts. Each agent hence possessed k hypotheses to draw from and measured their performance from week to week, forming a subjective reasoning for why he/her should or shouldn’t go. The results of the simulation are shown below:
The key dynamic to notice is how the pattern of attendance will change from week to week, but mean attendance will converge to 60. If in one week, everyone believes few will show up, everyone shows up — which invalidates the hypothesis that few will show up and visa versa. As such, although cycle-detector predictors are present, they are quickly “arbitraged” away so there are no persistent cycles (Arthur, 1996). The convergence to an attendance of 60 is the result of the “self-organization” of the predictors, which ensure that on average 40% of agents are forecasting attendance above 60 and 60% of agents are forecasting attendance below 60. As he writes,
“This emergent ecology is almost organic in nature”
This because, although the population of predictors split into the 60/40 average ratio (ensuring convergence around 60) “it keeps changing in membership forever”:
“This is something like a forest whose contours do not change, but whose individual trees do.”
Indeed, if viewed as a pure game of prediction (akin to a game such as “rock-paper-scissors”), “a mixed strategy of forecasting above 60 with probability 0.4 and below 60 with probability 0.6 is a Nash equilibrium.” However, given that each agent is equipped with different and varying hypotheses in each time period (and so pursue different strategies based on their own subjective reasoning) this does not explain how attendance converges to 60.
Relevance
Arthur’s paper is interesting in that it shows how a result which is predicted given perfect rationality can also emerge without perfect rationality, as the consequence of agents’ trial and error over time. As he writes:
Economists have long been uneasy with the assumption of perfect, deductive rationality in decision contexts that are complicated and potentially ill-defined. The level at which humans can apply perfect rationality is surprisingly modest.
From the reasoning given above, I believe that as humans in these contexts we use inductive reasoning: we induce a variety of working hypotheses, act upon the most credible and replace hypotheses with new ones if they cease to work.
Arthur’s conclusion to the study is hence the assertion that researching into inductive rather than deductive reasoning can lead to a “rich psychological world in which agents’ ideas or mental models compete for survival against other agents’ ideas or mental models — a world that is both evolutionary and complex”.
History
The El Farol Bar Problem was first presented at an American Economic Association meeting in 1994. However, the same problem under at different name, had previously been formulated and solved dynamically in 1988 by B.A. Huberman and T. Hogg in the book chapter:
- Huberman, B.A. and Hogg, T. (1988). ‘The Ecology of Computation’ in Studies in Computer Science and Artificial Intelligence, North Holland publisher, pp. 99.
On his website, Arthur himself describes
"There is a bar in Santa Fe, El Farol on Canyon Road, where a few years ago people could go on a Thursday night to hear Irish music. They would go if they expected few people to be there, but would stay home if they expected it to be crowded. [I] realized this represented a decision problem where forecasts that many would attend would lead to few attending, and forecasts that few would attend would lead to many attending. This gave a logical self-contradiction not unlike the Liar's Paradox: expectations would lead to outcomes that would negate these expectations."- Excerpt, "The El Farol Bar Problem" by W. Brian Arthur
The Liar’s Paradox being the prototypical example of circular-reasoning in logic, employed by Kurt Gödel in his famous 1931 proofs of his incompleteness theorems. Since its popularization by Arthur, the El Farol Bar Problem has spurred many extensions, including:
- Schaerf, A., Shoham, Y., & Tennenholtz, M. (1995). Adaptive Load Balancing: A Study in Multi-Agent Learning. Journal of Artificial Intelligence Research, 2. pp. 475–500.
- Galstyan, A., Kolar, S., & Lerman, K. (2003). Resource Allocation Games with Changing Resource Capacities. Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems.
- Enumula, P.K. & Rao, S. (2010). The Potluck Problem. Economics Letters 107 (1). pp. 10–12.
This essay is part of a series of stories on math-related topics, published in Cantor’s Paradise, a weekly Medium publication. Thank you for reading!
