Transcript Chapter 16: Game Theory - MCCC Faculty & Staff Web Pages

Game Theory
Part 2: Zero Sum Games
Zero Sum Games
• The following matrix defines a zero-sum game. Notice the sum of
the payoffs to each player, at every outcome, adds to zero.
Player 2 (Column)
Player 1
( row )
A
B
X
(2,-2)
(2,-2)
Y
(1,-1)
(3,-3)
If both players know all the possible strategies and the resulting payoffs
and play their best possible strategy in terms of their own best interest,
what will happen?
Zero Sum Games
• Each player can reason as follows: Player 2 could do better and will
do no worse by selecting strategy A as compared to B. This is
because the payoffs to player 2 (while still negative) are sometimes
better and never worse for player 2 in column A compared to column
B. Expecting this, player 1 would do better with strategy X.
Player 2 (Column)
Player 1
( row )
A
B
X
(2,-2)
(2,-2)
Y
(1,-1)
(3,-3)
• We are assuming each player expects the other to play the strategy
in their own best interest. Each player asks: What is the best I can do
assuming the other player does the best he can do?
Zero Sum Games
• Of course we don’t know what actual players in this game might do.
But assuming each is trying to achieve the highest payoff, there is no
reason to expect any other outcome.
Player 2 (Column)
Player 1
( row )
A
B
X
(2,-2)
(2,-2)
Y
(1,-1)
(3,-3)
• We say that the strategies X and A form an equilibrium point
because neither player can achieve a better result assuming the other
player doesn’t change strategy. This combination of strategies is also
called a saddle point because it is an equilibrium point where both
players are getting the highest possible payoff assuming the best play
by the opponent.
Battle of the Bismark Sea
• The previous game was actually played out in February 1943 as
the Battle of the Bismark Sea between U.S. and Japanese forces.
We may consider the U.S. commander, General Kenny as player 1,
while his opponent, player 2, is Admiral Imamura.
Battle of the Bismark Sea
• In the middle of World War II, the Japanese Admiral was ordered
to deliver reinforcements to Japanese soldiers fighting in Papua New
Guinea. The Japanese had to choose between two available
routes…
Battle of the Bismark Sea
The Japanese reinforcements
could be sent either by a
northern route, through the
Bismark Sea, or through a
southern route, through the
Solomon sea.
General Kenney expected the
reinforcements to be sent and
knew the supply routes
available to the Japanese.
Both commanders also knew
of the significance of certain
weather conditions. If the
U.S. commander anticipated
his opponent’s move, and sent
his planes toward that route,
he would have more days of
bombing available.
Battle of the Bismark Sea
If the U.S. commander guessed
his opponent’s decision incorrectly,
he would have to redirect his
planes and would lose a day of
bombing.
Let’s say the “payoffs” in this game
are the number of days of
bombing: positive for the U.S.
forces and negative for the
Japanese. The number of days is
the same for each, just positive for
one and negative for the other.
Hence, this is a zero-sum game.
A deciding factor was the bad
weather in the north, limiting the
number of days the Americans
could bomb the Japanese to only
two days in the northern route.
The Battle of the Bismark Sea
• We can put this game into matrix form as follows. The numbers at
each outcome represent number of days of bombing, positive for the
Americans and negative for the Japanese.
Admiral Imamura
General Kenney
Travel
North
Travel
South
Search
North
(2,-2)
(2,-2)
Search
South
(1,-1)
(3,-3)
As the name of the battle suggests, both commanders choose the
northern route, through the Bismark Sea.
In spite of this being an “optimal strategy” for the Japanese, they
suffered heavy losses. However, the loss certainly would have been
greater for the Japanese with another day of bombing.
Zero Sum Games
• Normally, if a matrix game is a zero-sum game, we don’t need to
write the payoffs for both players. Instead we write only one number
in each matrix cell.
Admiral Imamura
General
Kenney
Travel
North
Travel
South
Search
North
(2,-2)
(2,-2)
Search
South
(1,-1)
(3,-3)
Admiral Imamura
General
Kenney
Travel
North
Travel
South
Search
North
2
2
Search
South
1
3
• If only one number is written in each cell of the matrix, then the
game is understood to be a zero-sum game.
Zero Sum Games
• For example, in the matrix below, because only one number is
written in each cell, it is understood that the payoffs are the given
numbers for the row player (General Kenney) and the negative of
each of these values for the column player (Admiral Imamura).
Admiral Imamura
General Kenney
Travel
North
Travel
South
Search
North
2
2
Search
South
1
3
Finding Saddle Points
• For zero-sum games, we can look for saddle points by recognizing the
following two facts:
• The row player will want to the maximum value in the matrix.
• The column player will want the minimum value in the matrix.
Column Player
Row Player
Travel
North
Travel
South
Search
North
2
2
Search
South
1
3
Note that in zero sum games saddle points are the same as equilibrium points. A
saddle point is where both players are getting the best result possible assuming
the opponent is doing their best. An equilibrium point is where neither player has
a reason to change strategies assuming the other player doesn’t change.
Finding Saddle Points
Column Player
Row Player
Travel
North
Travel
South
Search
North
2
2
2
Search
South
1
3
1
• To look for a saddle point in a matrix game, begin by finding the
minimum values of each row. ( These are called the row minima. )
• Then, choose the maximum value of these minima. (This is called the
maximin strategy for the row player. )
• We do this because a rationalization for the row player is to find the
best move possible assuming that the column player chooses his best
strategy. It’s like thinking “what’s the best I can do when he plays his
best.”
Finding Saddle Points
Column Player
Row Player
Travel
North
Travel
South
Search
North
2
2
2
Search
South
1
3
1
2
3
• Now, look for the maximum values for each column. (These are
column maxima.)
• Then, choose the smallest of the column maxima. This is called the
minimax strategy for the column player.
• Here, the column player is thinking: “What is the best I can do when
the row player is playing his best strategy.”
Finding Saddle Points
Column Player
Row Player
Travel
North
Travel
South
Search
North
2
2
2
Search
South
1
3
1
2
3
• Because, in this example, the row maximin and the column minimax
strategies coincide with the same outcome, these strategies are called a
saddle point (or an equilibrium point).
• In some cases, given a 2x2 matrix game, we can find equilibria by
determining if the row maximin and column minimax coincide with one
outcome.
Finding Saddle Points
equilibrium
point
Row Player
Column Player
Travel
North
Travel
South
Search
North
2
2
Search
South
1
3
• The “equilibrium point” or “saddle point” for this game is the
combination of the strategies of traveling and searching north. It is the
best each player can do assuming the other player does their best.
• The outcome associated with the equilibrium point is called the value of
the game. In this case, the value is 2.
• We say a game is fair if it’s value is 0. Thus, this particular game is not
fair.
Saddle Points
• In zero-sum games, the terms saddle point and equilibrium point are
interchangeable.
• These terms refer to the combination of strategies that are in each
player’s best interest assuming all other player’s use the strategy in their
best interest.
• The term saddle point comes from the fact that, in a game with two
players, each with two strategies, it represents at one point a highest
point for the lowest payoff values and also a lowest point for the highest
payoff values.
Row player wants highest value
in matrix
Column player wants lowest
value in matrix
Saddle Points
As the row player,
imagine these lines are
your choices. You want
the highest on the curve.
The saddle point is where
both players get the best
result assuming the other
makes the best choice for
themselves.
As the column player, imagine
these lines as your choices. You
want the lowest on the curve.
Saddle Points
As the row player,
imagine these lines are
your choices. You want
the highest on the curve.
The column player is
picking the line that is a
low as possible and the
row player is picking the
line that is as high as
possible.
As the column player, imagine
these lines as your choices. You
want the lowest on the curve.
Saddle Points
As the row player,
imagine these lines are
your choices. You want
the highest on the curve.
The saddle point is an
equilibrium point because
neither player would have
a reason to make a
different choice assuming
the other player didn’t
make a different choice.
As the column player, imagine
these lines as your choices. You
want the lowest on the curve.