| Game Theory
Game Theory is a brand of Economics (and decision mathematics) that looks at the different strategies a player (a person making a decision) can make. The main pioneer of Game Theory was John von Neumann whose book and work published in 1928 created the sub-field of Game Theory. John Nash also created the theory of a Nash equilibrium, a point were both players have no incentive to adopt another decision.
The different decisions a player can make are given in a pay-off matrix. Usually convention dictates that the player listed in the row has his outcomes stated first. For example:
| |
B Plays 1 |
B Plays 2 |
| A Plays 1 |
(2,7) |
(4,9) |
| A Plays 2 |
(3,1) |
(5,5) |
If A plays 1 and B plays 1 then the outcome is 2 units for player A and 7 units for player B. Pay-off matrices may also be zero-sum, this means that one players gain is another's loss. An example of a zero-sum pay-off matrix:
| |
B Plays 1 |
B Plays 2 |
| A Plays 1 |
5 |
-7 |
| A Plays 2 |
-3 |
4 |
For a zero-sum game, the pay-off matrix usually only gives the pay-offs for one player (as for the other player the pay-off will be the value*-1), conventionally this is normally Player A (the player represented by the rows) unless otherwise stated. Below is the same pay-off matrix as above, but the pay-offs are for player B; note, to find this we have simply multiplied each cell by -1.
| |
B Plays 1
|
B Plays 2
|
A Plays 1
|
-5 |
7 |
A Plays 2
|
3 |
-4 |
Keywords
Nash Equilibrium - A situation where no player has a reason to change their strategy.
Zero-Sum Game - A zero-sum game is one in which one players gain is the other players loss. The pay-off matrix is usually given in terms of Player A, to find out Player B's pay-off matrix multiply each cell by -1.
Play - The choice or decision made by a player.
Saddle Point - A point where it isn't advantageous to adopt a different strategy, this will only occur if the row maximin = column minimax.
Maximin - The Maximum value of the Minimum outcomes from choosing a play. The maximin is usually found for the rows.
Minimax - The Minimum value of the Maximum outcomes from choosing a play, this would be used to find the best choice for a Player B (column player) in a zero-sum game.
Dominate - A row or column dominates another row or column if every single cell has a better pay-off.
Play Safe Strategy - A strategy where a player plays the choice that results in him losing the least. This can be obtained by calculated the worst outcome in each row/column and then selecting the maximum value of these worst outcomes.
Pay-Off Matrix - A matrix representing the pay-offs to the players for playing a certain decision.
Stable Solution - See Saddle Point
Prisoners Dilemma is an example of a 2 person game. A 2 person game is one in which only 2 parties can play. 2 men are caught spending forged money and are arrested by the police. The detective believes these 2 men not only spent the forged money but counterfeited it also. However he has no evidence of this and so puts the men in different rooms and interrogates them separately.
He tells them that if neither of them confess to being a counterfeiter, then they will be charged with attempting to spend forged money for which they would be sentenced to 1 year in prison. If they both confess to being forgers then they would get a lenient sentence of only 4 years. If only one of them confesses to forgery they will get off, but the other prisoner will be get 10 years.
This information can be summarised into a pay-off matrix. The outcomes are ordered as pairs (A,B).
|
|
B confesses |
B does not confess |
|
A confesses |
(-4,-4) |
(0,-10) |
|
A does not confess |
(-10,0) |
(-1,-1) |
In the payoff matrix above the results are negative as they have something to lose, if they were positive it means they would be gaining something. The worst outcome for A if he confesses is 4 years, and if he doesn’t confess it is 10 years. Therefore he will confess. Similarly for B if he confesses the worst outcome is that he gets 4 years were as if he didn’t confess he might get 10 years. Therefore he also looks to confess. Both A and B confess hence they both get 4 years in prison.
Play Safe Strategy
When playing safe each player looks for the worst outcomethat could happen and then picks the choice that results in the least worstoption. The option one chooses is known as a play.
|
|
B plays 1 |
B plays 2 |
B plays 3 |
Worstoutcome for A |
|
A plays 1 |
(8,2) |
(0,9) |
(7,3) |
0 |
|
A plays 2 |
(3,6) |
(9,0) |
(2,7) |
2 |
|
A plays 3 |
(1,7) |
(6,4) |
(8,1) |
1 |
|
A plays 4 |
(4,2) |
(4,6) |
(5,1) |
4 |
|
Worstoutcome for B |
2 |
0 |
1 |
|
Looking at the worst outcomes for A we can see that thehighest number is 4. Therefore A should play 4 and regardless of what B decidesto play A would be guaranteed a value of 4 units. Looking at B’s worst outcomewe can see that the highest number is 2 so B should play 1.
Therefore if A plays 4 and B plays 1 the play safe strategygained A 4 units and B 2 units.
In the above example both A and B would benefit if theycollaborated, if they had conferred between them, they may have decided for Ato play 3 and B to play 2 therefore the result is (6,4) and both playersincrease their winnings. This is because the above example is a non-zero sumgame.
In real life however most games are zero-sum. If I win youloose and vice versa. This can be shown if in each cell the values equal zero.In a zero-sum game you only need to write A’s winnings as this also representsthe negative of B’s winnings.
A pay-off matrix is always written from the row player’s(usually A) point of view unless stated.
The play safe strategies (in a zero-sum game) are for playerA (row) the row maximin. This is the maximum of the minimum values. For playerB (column) it is the column minimax. This is the minimum of the maximum values(as shown below this is because the values are from A’s point of view and so shouldbe negated).
|
3 |
-4 |
2 |
-4 |
|
-1 |
4 |
-2 |
-2 |
|
-3 |
1 |
4 |
-3 |
|
1 |
-1 |
1 |
-1 |
|
3 |
4 |
4 |
|
Above is a pay-off matrix (from A’s perspective) if A were toplay 1 and B were to play 2 then B would win 4. If A were to play 1 and B wereto play 1 A would win 3.
The values to the right of the table show the row minimum(the worst that can happen) and the values beneath the table show the columnmaximum (the worst that can happen for B, these are the highest positivenumbers as they have to be negated to get B’s result).
The row maximin (maximum of the minimum) is row 4; with apay-off of -1. Therefore A would play 4. The column minimax (the minimum of themaximum) is column 1 = 3; hence B would play 1.
Usually we are given the pay-off matrix in terms of player Aif you are told to use this pay-off matrix to determine the pay-off matrix for B then you would transpose the matrix and then multiply each term by -1 of Player A’s matrix.
Below is a pay-off matrix from A’s perspective; find B’spay-off matrix:
B’s pay off-matrix therefore is:
Another example (note the transposition; the values in thecolumn switch to become the values in the rows. Therefore one can only findanother perspective of a matrix if the matrix contains the same number ofoptions, e.g. A can play up to 5 and so can B).
|
|
B plays 1 |
B plays 2 |
B plays 3 |
B plays 4 |
|
A plays 1 |
7 |
2 |
-3 |
5 |
|
A plays 2 |
4 |
-1 |
1 |
3 |
|
A plays 3 |
-2 |
5 |
2 |
-1 |
|
A plays 4 |
3 |
-3 |
-4 |
2 |
From B’s perspective the matrix would look like:
|
|
A plays 1 |
A plays 2 |
A plays 3 |
A plays 4 |
|
B plays 1 |
-7 |
-4 |
2 |
-3 |
|
B plays 2 |
-2 |
1 |
-5 |
-3 |
|
B plays 3 |
3 |
-1 |
-2 |
4 |
|
B plays 4 |
-5 |
-3 |
1 |
-2 |
Note: you also have to multiply the cells by -1.
Stable Solution (Saddle Point)
A game is said to have a stable solution if playing safe results in an equilibrium where it isn’t advantageous for the players to change their strategy. In a zero sum game there will only be a stable solution if the row maximin equals the column minimax.
|
4 |
-1 |
2 |
3 |
-1 |
|
4 |
6 |
3 |
7 |
3 |
|
1 |
2 |
-2 |
4 |
-2 |
|
4 |
6 |
3 |
7 |
|
As we can see in the example above A would play row 2 (as this is the maximin) and win 3 and B would play column 3 (as this is the minimax) and would result in a loss of 3. In this case the row maximin = the column minimax hence there is equilibrium.
If there isn’t a stable solution then it A or B could profit by playing a different strategy (i.e. not play a safe strategy).
Reducing a pay-off matrix
A pay-off matrix can be made smaller by eliminating certain options if a row or column is better (if it dominates).
This can only be done if the row/column is ALWAYS better than another row/column.
|
|
B plays 1 |
B plays 2 |
|
A plays 1 |
7 |
1 |
|
A plays 2 |
-3 |
6 |
|
A plays 3 |
4 |
0 |
The 3x2 matrix above can be reduced to a 2x2 matrix.
We can see from the matrix that row 1 dominates row 3; 7 is bigger than 4 and 1 is bigger than 0. This means that for A no matter what B does, row 1 is always a better option to play than row 3 hence row 3 can be eliminated as A would never rationally select it.
Therefore the new deduced matrix would look like:
|
|
B plays 1 |
B plays 2 |
|
A plays 1 |
7 |
1 |
|
A plays 2 |
-3 |
6 |
The same deduction can be done to a column if another column dominates.
Page last updated on 03/08/15
|
