www.cantorsparadise.com Open in urlscan Pro
162.159.153.4 Public Scan

Back to summary

Submitted URL:
https://www.cantorsparadise.com/the-el-farol-bar-problem-a60205dd3f86
Effective URL:
https://www.cantorsparadise.com/the-el-farol-bar-problem-a60205dd3f86?gi=460ac291e0c5
Submission: On October 25 via manual (October 25th 2021, 10:46:35 am UTC) from ES — Scanned from DE

Form analysis
0 forms found in the DOM

Text Content

* Privatdozent Newsletter

RESPONSES

What are your thoughts?

Cancel
Respond

Also publish to my profile

There are currently no responses for this story.

Be the first to respond.

El Farol on Canyon Road in Santa Fe, New Mexico

GAME THEORY

THE EL FAROL BAR PROBLEM

Jørgen Veisdal
Follow

May 27, 2020 · 6 min read

> “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:

Figure 1. Bar attendance in the first 100 weeks according to Arthur’s computer
experiment

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”.

Left: W. Brian Arthur (Photo: Ian Tuttle, Porcupine Photography). Right:
Arthur’s 1994 paper “Inductive Reasoning and Bounded Rationality” in The
American Economic Review 84 (2) pp. 406–411.

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!

CANTOR’S PARADISE

Medium’s #1 Math Publication!

302

* Economics
* Biology
* Math
* Mathematics
* Science

302 claps

302

Written by

JØRGEN VEISDAL

Author of Privatdozent. Editor-in-Chief at Cantor’s Paradise. Associate
professor.

CANTOR’S PARADISE

Medium’s #1 Math Publication

Written by

JØRGEN VEISDAL

Author of Privatdozent. Editor-in-Chief at Cantor’s Paradise. Associate
professor.

CANTOR’S PARADISE

Medium’s #1 Math Publication

www.cantorsparadise.com Open in urlscan Pro 162.159.153.4 Public Scan

Form analysis 0 forms found in the DOM

Text Content

www.cantorsparadise.com Open in urlscan Pro
162.159.153.4 Public Scan

Form analysis
0 forms found in the DOM