Nash Equilibrium - El Farol Bar Problem

581 Views Asked by At

Statement of the problem, from Wikipedia:

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.

Is the following solution a Nash Equilibrium?

Each individual rolls a die of 60 faces. If the outcome is 1 they go to the bar, if the outcome is not 1 they stay home.

I am not sure if it can be considered a Nash Equilibrium since I have arguments against it and in favour. This solution does not require cooperation and it is the best way to ensure that they will have fun. On the other hand all the Nash Equilibrium solutions that I have seen so far use utility values to assign probabilities to each action to define the best strategy.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose the number of people in the population is $\ N\ $, and it's not a multiple of $10$ (so you don't have to bother about the payoffs to the participants when exactly $60\%$ of them go to the bar. Let $\ S=\lfloor0.6N\rfloor\ $, so the bar will be too crowded if the number who go to it exceeds $\ S\ $ and won't be too crowded if the number doesn't exceed $\ S\ $. Let $\ u\ $ be the amount of fun clients will have if they go to an uncrowded bar, $\ c\ $ the amount they will have if they go to a crowded bar, and $\ h\ $ be the amount they will have if they stay home. I assume $\ u,c,$ and $\ h\ $ have the same value for everyone in the population. The statement of the problem tells us that $\ u>h>c\ $.

Let $$ p=\sum_{i=0}^{S-1}{N-1\choose i}\frac{59^{N-1-i}}{60^{N-1}}\ . $$ This is the probability that $\ S-1\ $ or fewer of a given subset of the population of size $\ N-1\ $ decide to go to the bar when they're all using the strategy described. Any individual in the population has a probability of $$ \frac{p}{60} $$ of going to the bar and finding it not too crowded, a probability of $$ \frac{1-p}{60} $$ of going to the bar and finding it too crowded, and a probability of $$ \frac{59}{60} $$ of staying home. The expected fun of each individual when they all follow the strategy described is therefore $$ \frac{pu+(1-p)c+59h}{60}\ . $$ The strategy is a Nash equilibrium if no single individual can increase his expected fun by choosing either definitely to stay home or definitely to go to the bar provided everyone else sticks to the described strategy.
The amount of fun an individual will get by staying home is $\ h\ $, while the expected amount of fun he or she will get by going to the bar when everyone else sticks to the strategy described is $\ pu+(1-p)c\ $. Thus the strategy will be a Nash equilibrium if and only if \begin{align} \frac{pu+(1-p)c+59h}{60}&\ge h\hspace{3em}\text{and}\\ \frac{pu+(1-p)c+59h}{60}&\ge pu+(1-p)c\ . \end{align} These inequalities are satisfied if and only if $\ pu+(1-p)c=h\ $, or,equivalently $\ p=\frac{h-c}{u-c}\ $. It's extremely unlikely that this will be the case for any particular given values of $\ N,u,c\ $ and $\ h\ $, and therefore extremely unlikely that the strategy described will be a Nash equilibrium.

However, since $\ 0<\frac{h-c}{u-c}<1\ $, and $\ \mathscr{U}(g)=\sum_\limits{i=0}^{S-1}{N-1\choose i} g^i(1-g)^{N-1-i}\ $ is a strictly decreasing function on $\ [0,1]\ $, with $\ \mathscr{U}(g)=1, \mathscr{U}(1)=0\ $, there is a unique $\ g^*\in(0,1)\ $ such that $\ \mathscr{U}(g*)=\frac{h-c}{u-c}\ $. If everyone in the population independently chooses a random number $\ \rho\ $ uniformly from the unit interval $\ [0,1]\ $, and goes to the bar if $\ \rho<\mathscr{U}(g*)\ $, then that strategy is a Nash equilibrium.

And you can actually implement this strategy with any die. If the die has $\ b\ $ sides, labelled $\ 1,2,\dots,b\ $, let $\ t_i\ $ be the result of the $\ i^\text{th}\ $ toss, and keep tossing until either $$ \mathscr{U}\left(\sum_{i=1}^n\frac{t_i-1}{b^i}\right)<\frac{h-c}{u-c} $$ or $$ \mathscr{U}\left(\frac{t_n}{b^n}+\sum_{i=1}^{n-1}\frac{t_i-1}{b^i}\right)>\frac{h-c}{u-c}\ . $$ One of these events will eventually occur with probability $1$. If it is one of the latter—which it will be with probability $\ \mathscr{U}(g*)\ $—then you go to the bar, whereas if it is one of the former (probability $\ 1-\mathscr{U}(g*)\ $) you stay home.