A gentle introduction to Game Theory
Game Theory has always been one of my mathematical interests as a developer. Possible because it provides a mathematical model to the iteration between systems. Perhaps, because I liked the movie A beautiful mind. In this introductory post, I aim to provide a quick introduction to practical game theory.
A bit of history
It was in 1921 when Emile Borel, a French mathematician, publish several papers on the theory of games. These papers presented common strategies such as bluffing and second-guessing in games like Poker. It was Poker that inspired Von Neumann, he realized that someone playing based only on statistical value would not perform very well. As he introduced in an article: On the theory of Parlor Games in 1928. While the theory was initially developed to analyze parlor games, it was always clear from Borel’s work the large number of applications for economical behavior, politics, and warfare.
It was the book Theory of Games and Economic Behaviour, co-written with Oskar Morgenstern, that gave von Neumann the title of father of game theory. But the movie A beautiful mind was not about von Neumann’s life. In effect, to know more about von Neumann we need to read the book Prisoner’s Dilemma by Poundstone.
In 1950, Jon Nash published one of the greatest contributions to Game Theory in a 2-page paper: Equilibrium points in N-person games, introducing a concept later known as Nash Equilibrium, and became the basis of how economists predict the outcome of strategic iterations.
The Prisoner’s Dilemma
The prisoner’s dilemma is the most famous scenario of game theory, which describes the following situation. Two suspects are held in separate rooms of a police station without an option to communicate with each other. The prosecutor offers the following options:
- If one cooperates with the police and agrees to confess while the other does not, the one that cooperates will go free while the other will be prosecuted for a 5 years sentence
- If both cooperate and testify, then both will be charged with 3 years each.
- If none of them cooperate given that the evidence against them is weak both will be prosecuted with one year.
If you find yourself in a similar situation, there is an important piece of information that you will need to know before start reasoning about action. Does the offer been offered to both prisoners or not? if both know this information, then we are under a game of complete information. A game of complete information requires common knowledge among the players of actions, outcomes of the actions, and the preference of each player.
The actions of the game confess or deny may happen to each player in a short period. If someone doesn’t make a fast decision, the decision can be taken from you. So we can assume that both player actions are taken simultaneously.
With those ingredients we can represent the prisoner dilemma in a normal-form game, the game’s matrix representation looks like this:
We can read this matrix easily: for each action and each player, we have a tuple of value where the first value represents the payoff of the action to the first prisoner and the second value the payoff for the second prisoner. We encode the payoffs as negative value as they are, in fact, not a preference, meaning that 0 years in jail is better than 5.
Before starting to discuss how to reason or find out the best strategy for each prisoner, we already have the necessary elements to implement our problem in code. I am going to use the python NashPy library, which can be easily installed because the only dependencies of the library are with two well-known packages NumPy and SciPy.
We divided the payoffs per player, as per the library API, and each player required a matrix of expected payoffs.
Dominant Stategies
If we look back at the game, as we know, each prisoner has full information about the game, and no loyalty to each other, in other words, they are adversaries. Regardless the action that the other prisoner take, each of them get a better payoff by cooperating:
- If prisoner 1 cooperates will get 3 years if prisoner 1 cooperates and 0 if it will defect. While if he decides to defect he will get 5 years if prisoner 2 cooperate and 1 if he defects. That means that whatever the action of the second prisoner, our first prisoner will be always better at cooperating.
- The situation is analog for our second prisoner because the prisoner dilemma is a symmetric game.
In game theory, a dominant strategy is an optimal option for a player where no matter how the other player plays.
Nash equilibrium
In the prisoner’s dilemma, we assume that each of the players is rational, so they can analyze the game, and as a result, they will always be playing the dominant strategies, as this gives the better payoff. So we expect that in our game, as both players play the dominant strategy, it is expected that both convicts will be in jail for 3 years. We can say that this situation is a Nash equilibrium as is a result of all the players playing the dominant strategy.
Hold on a second, our results seem to be counterintuitive. There is a better outcome for both cons and is to defect both so they can be in jail for a single year. This outcome, while desired, is what we call unstable, and it requires some agreement that does not hold in a competitive game.
We can now resolve our Nash equilibrium by code and obtain the payoffs:
I used the support enumeration algorithm to resolve the Nash equilibrium. At the moment, I haven’t shared all basics to discuss the algorithm of the implementation or complexity. I will do that into a new post so I can focus on the core ideas here. So instead, we can use some developer deduction to find out more about the result:
- The method returns a generator of Nash equilibriums that indicates that for a game, they may be multiple strategy sets that provide an equilibrium.
- The values returned are the actions of each convict, so [(1,0), (1,0)] means that each one always defects, but the decimal return shows us that there may be a case of where we would like to randomize the actions and take an action base on a probability, we had only discussed the case of pure strategies, this randomization is cover by nash mixed strategies, that we will discuss in a new post.
Summary
We cover a good amount of ground introducing the story behind Game Theory. We looked at the fascinating example of a prisoner’s dilemma, defining complete information and dominant strategies. And resolve a simple problem using code after doing some reasoning. These should give us solid foundations for work on some game theory real examples.
