BLOCK 7: Introduction to Game Theory
Class 1: Games and their representation
Game Theory has been designed to try to understand the interactions of the human being. That is, to try to predict how an individual will behave, interacting with his environment, under certain assumptions.
In this introduction we will assume, as the most important assumption, that the individual is rational. Being rational implies, in this context, that the individual has all the information available and that she knows how to use it for his own benefit. But, in addition, than the rest of individuals with whom it interacts does the same. If this is assumable, then we can propose a game. But… what is a game?
One game:
A game, in principle, is a mathematical model to specify interaction between individuals and has, among others, these ingredients
- players or agents (in our case, it’s going to be a finite set. In fact, we will only work with 2 players)
- strategies: are the description of the possible movements that will compose the game. In our case, at most each player you will have 4 possible strategies
- payouts: it is the profit or loss that will be made to a player carry out each strategy. We, as we will have 2 players and finite strategies, we can put them in a matrix.
Now, let’s look at an example and its specification
Two students have copied in an exam and the teacher knows it. But they need they to confess. To do this, teachers develop a mechanism of incentives. They bring the two students together in two different classrooms, without the possibility for them to communicate with each other. And they tell the students: “if you both confess, we will give you a 4 to each and you will go to the extraordinary. If one confesses, but the other does not, the one who confesses will be given a 7 as a prize but, to the one who does not confess, you will be expelled. If the two do not confess, you will be left with a 5, because the exam is passed, since you have copied from someone who knows.” If we represent strategies and payments in a table, we will have something like this:
| \(A 1 \ A2\) | Confess | Do not confess | |
| Confess | 4, 4 | 7, Exp | |
| Do not confess | Exp,7 | 5.5 |
- What would you do if you were one of them? Usually, we’d think “we don’t confess.” If we do not confess, they will be forced to approve us because they have no proof that we have copied. See that, in reality, as the game is configured, the prediction what we will get is different. But let’s not get ahead in the explanation.
Dominated strategies
To try to see how to predict what players (or agents) will do in a game, let’s start defining dominated strategies. It is a very simple concept: we will say that a strategy for one player it will be dominated by another if their payouts are less than those of the dominant player, regardless of the other player’s payouts. Instead, we say that a strategy is weakly dominated if there are equal payments and worse than those of the strategy dominant. If that happens, that strategy is eliminated because the player, by being rational and having all the information, you will never want it play.
for example be the following game
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | 1.-1 | 2, -2 | 4,-4 | |
| Player 1 | \(Y\) | 1.-1 | 0.0 | 5.-5 |
| \(Z\) | 0.0 | 1, -1 | -1.1 |
To analyze whether or not any strategy is mastered, we can start with the player we want: in this case, let’s start with rows. We forget, for a moment, player payments 2
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | \(\color{green}{4},\color{grey}{-4}\) | |
| Player 1 | \(Y\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{0},\color{grey}{0}\) | \(\color{green}{5},\color{grey}{-5}\) |
| \(Z\) | \(\color{green}{0},\color{grey}{0}\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{-1},\color{grey}{1}\) |
And, now, we look row by row if any is as good or better than other. If we analyze, the strategy \(X\) of player 1, we see that it is not always preferred to the \(Y\), so there is no domination between the two. On the other hand, between \(Y\) and \(Z\), either. But – if you look – between the \(X\) and the \(Z\) of player 1, the \(X\) dominates the \(Z\), so we can eliminate it: player 1 will never want to play that strategy
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | \(\color{green}{4},\color{grey}{-4}\) | |
| Player 1 | \(Y\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{0},\color{grey}{0}\) | \(\color{green}{5},\color{grey}{-5}\) |
Now, we keep looking. As in player 1 we do not find more dominated strategies, we change players: we analyze by columns. We “forgot” then, the payments of player 1:
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{2},\color{green}{-2}\) | \(\color{grey}{4},\color{green}{-4}\) | |
| Player 1 | \(Y\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{0},\color{green}{0}\) | \(\color{grey}{5},\color{green}{-5}\) |
As we can see, the strategy \(Z\) is dominated for player 2 by both strategies. We eliminated it.
| Player 2 | ||||
| \(X\) | \(Y\) | |||
| \(X\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{2},\color{green}{-2}\) | ||
| Player 1 | \(Y\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{0},\color{green}{0}\) |
We return now again to analyze the player in rows (you have to iterate in this way until it can no longer be followed)
| Player 2 | ||||
| \(X\) | \(Y\) | |||
| \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | ||
| Player 1 | \(Y\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{0},\color{grey}{0}\) |
As we can see, for player 1, the strategy \(Y\) is dominated, so finally, we arrive at
| Player 2 | ||||
| \(X\) | \(Y\) | |||
| Player 1 | \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | |
In this case, it is easy to see that the prediction of the game is that both play the strategy \(\left\{ X,X\right\}\). There is no other that encourages both players to get out of this strategy without lose out.
| Player 2 | ||||
| \(X\) | ||||
| Player 1 | \(X\) | \(\color{green}{1},\color{green}{-1}\) | ||
However, can the outcome always be predicted. of a game using that way of “pruning” strategies?
Try doing it in this game
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | 1.-1 | 2, -2 | 4,-4 | |
| Player 1 | \(Y\) | 0.0 | 3.3 | 5.-5 |
| \(Z\) | 4.-4 | 3, -3 | -1.1 |
As you can see, you will not find dominated strategies. So what? Can we predict from this game?
Nash equilibrium
To try to use a solution to the previous game, I came J.F Nash and developed an idea of equilibrium. To write your definition in our own way, let’s define the elements somewhat better of a game between two people:
- We will call \(\mathcal{X},\mathcal{Y}\) to the strategy sets of the first and second players. For short, they are usually called: strategy spaces.
- The payment that each player receives given the strategies of both players will be: \(U_{1}(x,y),U_{2}(x,y)\) where we have the “utility” that reports to each player the strategy taken by the player 1 (\(x\in\mathcal{X},\)\(y\in\mathcal{Y})\).
In this way, Nash defined his equilibrium as:
Nash equilibrium:
Let us define \(x^{*}\in\mathcal{X}\),\(y^{*}\in\mathcal{Y}\) a couple of estategias. They will be Nash Equilibrium if they satisfy:
\[ U_{1}(x^{*},y^{*})\geq U_{1}(x,y^{*})\:p ara\:x\in\mathcal{X} \]
\[ U_{2}(x^{*},y^{*})\geq U_{2}(x^{*},y)\:p ara\:y\in\mathcal{Y}, \]
that is, player 1 will look for his optimum by setting the optimum of player 2 and vice versa. As you can see, they are “coupled” optimization problems: one seeks his optimum thinking that his opponent it also optimizes. That’s another aspect of rationality.
Consequently, each individual player gains nothing by modifying their strategy as long as the others maintain theirs. Thus, each player is executing the best move possible taking into account the best response (movements) of the other players.
In other words, a Nash equilibrium is a situation in the which all the players have put into practice, and they know that the have made, a strategy that maximizes their profits given the strategies of the others. Consequently, no player has any incentive to individually modify your strategy.
It is important to keep in mind that a Nash equilibrium does not imply that the best joint result is achieved for the participants, otherwise only the best result for each of them considered individually. It is perfectly possible that the result would be better for everyone if, somehow, players will coordinate their action.
We are looking for a Nash equilibrium
We return to the problem of those who have caught copying
| \(A 1 \ A2\) | Confess | Do not confess | |
| Confess | 4, 4 | 7, Exp | |
| Do not confess | Exp,7 | 5.5 |
Following the instructions of the definition, we have to think the following:
- "I place myself in the A1 player and I point out, for each strategy of A1, the best A2 strategies (i.e. what would A2 do if he/she was rational)
| \(A 1 \ A2\) | Confess | Do not confess | |
| Confess | \(4,\color{network}{4}\) | 7, Exp | |
| Do Not Confess | \(Exp,\color{network}{7}\) | 5.5 |
As we can see, if player 1 confesses, player 2 prefers to confess. If player 1 does not confess, then player 2 prefers to confess
Now, I do the same with the A2 player.
- I place myself in this and, for each A2 strategy, I look for the best A1 strategies:
| \(A 1 \ A2\) | Confess | Do not confess | |
| Confess | \(\color{green}4,\color{red}{4}\) | \(\color{green}7, Exp\) | |
| Do Not Confess | \(Exp,\color{network}{7}\) | 5.5 |
As we can see, there are a couple of strategies: \(\left\{ C,C\right\}\), which it is chosen by both players, so this will be the equilibrium. See:
- If player 1 or 2 changed not to confess, they would be worse off (the expel)
- The two would be better off if they DID NOT confess. In fact, they would approve. But that’s not going to happen, given the selfish (maximizing) behavior that the players are supposed to have: “If I confess, I will have a 7.”
That is the prediction of the game by Nash equilibrium!
Will there always be Nash equilibrium?
There could even be more than one (which won’t be very informative). Look at this example:
A couple loves each other very much and can only see each other on weekends. They have invented a game to bring fun to the relationship. Every weekend they will choose if they go to the amusement park or to a dodecaphonism concert by Arnold Schoenberg (listen here to his wonderful work “Transfigured Night”: youtube.com/watch?v=Xrmsl2bkvak)
P1 loves amusement parks and P2 loves dodecaphonism. But there’s another thing they like: co-cooking. But the difficulty in agree that on Friday they will make the decision where to go without telling each other. The surprise will be “if are found or not”
We are going to propose a payment matrix that reflects what we intend. For example, this
| \(P 1 \ P2\) | Park | Schonberg | |
| Park | 7, 4 | 0.0 | |
| Schonberg | 0.0 | 4.7 |
(note that the values are arbitrary. What’s important is that if they do not coincide they will be more unhappy than if they coincide). Also, if they end up in the amusement park, P1 will be more happy and, if they end up in the Schonberg concert, it will be P2 who be happier. What’s going to happen?
Let’s look for the Nash equilibrium. Let’s start with P1. What will the P2 player face each P1 strategy?
| \(P 1 \ P2\) | Park | Schonberg | |
| Park | \(7,\color{network}{4}\) | 0.0 | |
| Schonberg | 0.0 | \(4,\color{network}{7}\) |
And now, what will P1 do about each strategy? of P2?
| \(P 1 \ P2\) | Park | Schonberg | |
| Park | \(\color{green}7,\color{red}{4}\) | 0.0 | |
| Schonberg | 0.0 | \(\color{green}4,\color{red}{7}\) |
We have Two Nash equilibria! What do we do?
Actually, having two Nash equilibria is almost the same as not having none. It does not give us great information about the prediction the game. However, Nash proved that games with players and finite strategies had a balance in… mixed strategies.
Well, before we see what a mixed strategy is, we will say that the Strategies we’ve seen so far are called PURE.
Class 2: Equilibria in mixed strategies
The idea of this balance is to think that the game can be repeated. more than once under the same conditions (as in the case of couples). If this is so, and the information that individuals have is always the same (for example, in the couple’s game, if one week we do not cook, it does not mean that the following week we will not coincide: if the instructions are the same, anything could happen. In We’re going to assume that anything could happen, but that it will be driven by a certain randomness. That is, each player, depending on your preferences, you will have a distribution of probabilities for each strategy. For example, P1 will have the following:
\[ P1\begin{cases} P(park) & p\\ P(Schonberg) & 1-p \end{cases} \]
where \(0\leq p\leq1\). On the other hand, P2:
\[ P2\begin{cases} P(park) & q\\ P(Schonberg) & 1-q \end{cases} \]
where \(0\leq q\leq1\).
What strategy to choose if each has a associated probability?
Let’s include the odds in the table:
| P.2 | |||||
| \(q\) | \(1-q\) | ||||
| Parque | Schonberg | ||||
| P.1 | \(p\) | Parque | \(7,4\) | 0,0 | \(7q+0(1-q)\) |
| \(1-p\) | Schonberg | 0,0 | \(4,7\) | \(0q+4(1-q)\) | |
| \(4p+0(1-p)\) | \(0p+7(1-p)\) |
Now, we will calculate what we call “expected utility” which is the payment that each player will receive, before each strategy, having in mind that these payments are random (depend on \(p,q)\). Then for each player/strategy:
| P.1 | |||||
| \(q\) | \(1-q\) | ||||
| Park | Schonberg | ||||
| P.2 | \(p\) | Park | \(7,4\) | 0,0 | \(7q+0(1-q)\) |
| \(1-p\) | Schonberg | 0,0 | \(4,7\) | \(0q+7(1-q)\) | |
| \(4p+0(1-p)\) | \(0p+4(1-p)\) |
As you can see, each player is influenced by the odds of the opponent. For example \(7q+0(1-q)\), means that P1 waits win 7 with probability \(q\) and 0 with probability \(1-q\), if P1 plays Park.
Now, as P1 should remain indifferent to Park, Schonberg, since none is preferable (so will P2) the strategy will consist of resolving:
\[ \begin{cases} 7q+0(1-q)=0q+4(1-q)\\ 4p+0(1-p)=0p+7(1-p) \end{cases} \]
from where \(p=2/3\),\(q=1/3.\) Notice then that the interpretation of the game is as follows:
- Out of every three times, P1 will go 2 times to the amusement park and P2 to the Schonmberg concert
- The value of the game is obtained by substituting for each player in any of utilities. For example \(V_{P1}=7/3,V_{P2}=8/3.\)
- In zero-sum games you will get the same value for both players only than with a changed sign.
Example with a zero-sum game
Consider the following 2x2 null-sum game, where the payment matrix associated with player 1 (in rows):
| P.2 | |||||
| A | S | ||||
| P.1 | A | \(-2\) | \(2\) | ||
| S | \(0\) | \(1\) |
If we write the matrix for the two players, which is more comfortable:
| P.1 | |||||
| A | S | ||||
| P.1 | A | \((-2.2)\) | \((2,-2)\) | ||
| S | \((0.0)\) | \((1,-1)\) |
as you will see, there are no dominated strategies or balances in strategies Pure. That is why we propose the solution in mixed:
| P.2 | |||||
| \(q\) | \(1-q\) | ||||
| A | S | ||||
| P.1 | \(p\) | A | \(-2.2\) | \(2.-2\) | \(-2q+2(1-q)\) |
| \(1-p\) | S | \(0.0\) | \(1.-1\) | \(0q+1(1-q)\) | |
| \(2p+0(1-p)\) | \(2p+1(1-p)\) |
In this way, we will obtain \[ -2q+2-2q=-1-q\Rightarrow q=\frac{3}{5} \]
and, on the other hand: \[ 2p=-2p+1-p\Rightarrow p=\frac{1}{5} \]
So players will follow these strategies: \(\left\{ p,1-p,q,1-q\right\} =\left\{ \frac{1}{5},\frac{4}{5},\frac{3}{5},\frac{2}{5}\right\}\) and the value of the game is (substitutes in any of the expected payouts) \(\left\{ \frac{2}{5},-\frac{2}{5}\right\}\). Is say, on average player 1 will receive \(2/5\) and player 2 will pay \(2/5.\)