So, I got a text out of the blue this morning with my friend asking me to help with my purely academic experience in game theory. I like to help others (and be distracted from real-world responsibilities), so I agreed to help.
The setup
My friend's office was playing a variation of the el Farol Bar problem, a classic problem in game theory. Game Theory is a branch of economics, which tries to explain the behaviour of people (or "rational actors") when they are put in a "game". In game theory, a "game" is any situation where your choices affect the people you are playing the game with, and vice-versa. Basically, they are situtations in which you have to compete or coordinate your actions with others.
In the el Farol Bar problem, players try to coordinate against the group. In the original version, people in a small town love going out to the el Farol Bar, but the bar gets crowded easily. If more than 60% of the town chooses to go to the bar, each person at the bar would rather have stayed home. However, if less than 60% of the town goes, then the people who stayed at home would have rather gone to the bar, and the people who went to the bar are happy with their choice. Obviously, there is no situation where everybody is happy. Less obviously, there is no single decision that an individual can make that will always guarantee they will be happy with their choice. Economists call more general versions of this game "Minority Games", and they come in all sorts of forms.
My friend's workplace was asked the question: "What is your favourite season?" With a couple hours before their answer was due, I decided to go overboard.
The theory
Game theory analyzes games such as these by looking at their Nash Equlibrium. A Nash Equlibrium is a situation where each player is using a strategy that they are not better off deviating from when the other players are playing their own Nash Equilibrium strategy.
Classic games like the Prisoner's Dilemma have simple Nash Equlibria. In the Prisoner's Dilemma, two suspects are being interrogated by the police; they are given the choice to either cooperate with the police and implicate the other prisoner, or stay silent. If both prisoners stay silent, they are each given a light sentence, since there is not enough evidence to implicate them in the more serious crime. If one prisoner stays silent but the other cooperates, then the prisoner who cooperates is freed, while the prisoner who stayed silent is given a very harsh sentence. If they cooperate with the police and implicate one another, they each get a medium sentence. The prisoners essentially have no choice but to implicate one another; if they stay silent, they are at risk of receiving a very harsh sentence. If they implicate the other prisoner, the worst is that they receive a medium sentence, but the best case is that they are set free. The important part is that, when each prisoner is playing the strategy to implicate the other, neither of them wants to stay silent, since they will face the much harsher punishment. Conversely, if the prisoners start off staying silent, each one of them wants to cooperate with the police to change their light sentence to no sentence. There is only one equilibrium: (cooperate, cooperate).
Figure 1: The Prisoner's Dilemma: A game theory classic
Our seasons problem is a little more complicated, for a couple of reasons:
-
We are dealing with real people. The prisoner's dilemma and other Nash Equlibria in competitive games are notorious for not being easy to reproduce in the real world. So, whatever the Nash Equlibrium is, we can't be guaranteed that choosing it will actually give us a good result in the real world.
-
In the minority game, there isn't a single equilibrium strategy that everyone can play and be happy with. Instead, the Nash Equilibrium is a Mixed strategy, where you choose a certain action randomly. Essentially, the Nash Equlibrium strategy is to pick a season completely at random. However, if our opponents are deviating even a little from this strategy, we want to be able to exploit that deviation.
One of the problems with trying to think strategically like this is that there are many ways you can model your opponents. In the Seasons game, we might imagine that none of our opponents actually understand the game, and genuinely answer what their favourite season is. People have done polls on this, and they seem to suggest that ~40% of our opponents would answer Fall, ~10% Winter, and ~25% between Spring and Summer each. So, Winter would be the obvious choice.
Of course, this is a pretty naive way of modeling the players in our game. It is likely that most of these players are not actually playing the equlibrium strategy, but it hard to reason about what their actual strategies might be. So, how do we to try and get an edge on our opponents in a situation like this? My solution to this problem was to take a poll on what the best choice was.
Data!
Here are the results:
| Season | Count | Percentage |
|---|---|---|
| Spring | 5.25 | 25.00% |
| Summer | 3.25 | 15.48% |
| Fall | 6.25 | 29.76% |
| Winter | 6.25 | 29.76% |
Table 1: Results from my survey
(The fraction counts are from a frustrating friend who insisted on the strategy of flipping a coin.)
From this data, we get an idea of the opinions of what the best strategy is. Remember, these people are intended to be a representative sample of my friend's opponents in the real game! If we have any hope of gaining an edge, we want to use this data as a sample run of the real game. Without any solid theory to go on, the best strategy is to run a mock game with representative players and choose the strategy which would win in that game.
In the end, the small sample my friend and I collected pointed (very weakly) to Summer as being the minority choice. With a sample size so small (N = 21), we were skeptical of the results. So, on a whim, we went with Spring.
The result? Summer was the minority. Statisticians everywhere, enjoy your vindication.
| Season | Count | Percentage |
|---|---|---|
| Spring | 39 | 27.85% |
| Summer | 20 | 14.28% |
| Fall | 57 | 40.71% |
| Winter | 24 | 17.14% |
| Table 2: Results from the actual game |
The Important Question: Why is this interesting?
The minority game in particular is pretty relevant to places like finance. Going against the market is usually the path to money, so being able to predict how other people will behave can allow you to "beat the market". But, everyone is trying to behave strategically like this, so in practice, it's almost impossible to beat the market.
I'm not exactly sure why I found this game so interesting. I think part of it is the way it requires some backwards thinking. My friend was asking my opinion to help choose their strategy, but the data-oriented approach would say that my suggestion should be the last answer they should choose!
This kind of reminds me of the rock-paper-scissors bot, which is able to play rock-paper-scissors pretty damn well by exploiting the patterns that we feeble humans fall into when we try to act strategically. You think you're being sneaky when you play a rock three times in a row, but you're almost guaranteed that a hundred other people had that same thought too. Memory of this is what lets the bot absolutely destroy human players. Try playing the bot using your intuition, and see how you do. Then, play using a random number generator to make your choice, and be amazed at winning 1/3 of the time, losing 1/3 of the time, and tieing 1/3 of the time.
As humans, we seem adverse to acting totally randomly. In fact, when economists simulate these games, the players don't behave randomly; they learn very specific rules with the goal of beating the other players. But, the evolution of players' strategies makes their behaviour chaotic, which means that the end result is a situation very close to the behaviour predicted by the mixed (i.e. random) Nash Equlibrium. This is basically what would happen if you got two rock-paper-scissors bots to play against each other. They would settle into something that looks very similar to making random choices.
In the end, we don't know what's behind this result of Summer being the minority choice. The game theory literature says that if the same people played the game over and over again, they'd eventually tend to a strategy equivalent to choosing their season at random. Experiments with simpler versions of the minority game find that this does happen in reality (see a good summary of the general Minority Game here in Softpedia). But Game Theory has a harder time predicting what people will do when playing the game for the first time, so we're not much closer to understanding what's actually going on in the other players' heads.
The goal of data analysis is to try to prevent us from needing to act randomly; in this case, the data-oriented approach would have won us the game. Of course, with a sample size of 21, we're not very sure that data was actually going to give us the "right" answer. But statistics tells us that if we always follow the data, we'll be right more times than if we didn't. Even better, we can be more certain the more data we get!