EC 490 Week 4 lecture
1.
In learning to analyze
games of imperfect information (simultaneous move games), weÕll begin with
games in which all playersÕ strategies are in discrete variables – that is, in which all players choose
strategies from finite lists of possibilities.
2.
We represent games of
this sort using the normal or
strategic form. That is,
for each such game we draw a matrix. In 2-player cases, we list Player IÕs
strategies in rows and Player IIÕs strategies in columns as follows:
Column
|
|
Left |
Right |
|
| Row |
Up |
2, 4 |
1, 0 |
|
Down |
6, 5 |
4, 2 |
3.
The basic solution
concept in game theory is Nash equilibrium. WeÕll introduce it by way of the PrisonerÕs Dilemma.
Here is its matrix:
Confess Refuse
|
Confess
Player I
Refuse |
2,2 |
4,0 |
|
0,4 |
3,3 |
4.
The players, and analysts, can predict the outcome of the PD using a
mechanical procedure known as iterated elimination of strictly dominated
strategies. The husband (Player I) can see by examining the matrix that his
payoffs in each cell of the top row are higher than his payoffs in each
corresponding cell of the bottom row. Therefore, it can never be rational for
him to play his bottom-row strategy, viz., refusing to confess, regardless
of what his wife does. Since his bottom-row strategy will never be played,
we can simply delete the bottom row from the matrix. Now it is obvious
that Player II will not refuse to confess, since her payoff from confessing in
the two cells that remain is higher than her payoff from refusing. So, once
again, we can delete the one-cell column on the right from the game. We now
have only one cell remaining, that corresponding to the outcome brought about
by mutual confession. Since the reasoning that led us to delete all other
possible outcomes depended at each step only on the premise that both players
are economically rational - that is, prefer higher payoffs to lower ones -
there is very strong grounds for viewing joint confession as the solution
to the game, the outcome on which its play must converge. You should
note that the order in which strictly dominated rows and columns are deleted
doesn't matter. Had we begun by deleting the right-hand column and then deleted
the bottom row, we would have arrived at the same solution.
5.
LetÕs do another, in which just one player has a dominant strategy: the Fed
/ Congress game (p. 94).
Fed
|
|
Low i |
High i |
|
| Congress |
Balanced Budget |
3, 4 |
1, 3 |
|
Deficit |
4, 1 |
2, 2 |
6.
What weÕve called the ŌsolutionÕ to these games is the unique Nash equilibrium of the game. (The ŌNashÕ
here refers to John Nash, the Nobel Prize-winning mathematician who in Nash (1950) did most to extend and generalize von Neumann
& Morgenstern's pioneering work.) Nash equilibrium (NE) applies (or fails
to apply, as the case may be) to whole sets of strategies, one for
each player in a game. (Thus, to speak properly, you must say of a game that
itÕs in NE; of a whole set of strategies, one per player, that the set is an NE; and of some one
particular strategy that it is a NE strategy.) A set of strategies is a NE
just in case no player could improve her payoff, given the strategies of all
other players in the game, by changing her strategy. Notice how closely this idea is
related to the idea of strict dominance: no strategy could be a NE strategy if
it is strictly dominated. Therefore, if elimination of strictly dominated strategies
takes us to a unique outcome, we know we have found the game's unique NE. Now,
almost all theorists agree that avoidance of strictly dominated strategies is a
minimum requirement of rationality. This implies that if a
game has an outcome that is a unique NE, as in the case of joint confession in
the PD, that must be its unique solution. When we solve an extensive-form game
by ZermeloÕs algorithm, we get a solution even stronger than a mere NE: we get
the special NE that is the gameÕs subgame-perfect equilibrium, which means that the
strategy set is a NE for the whole game and also for each of its subgames.
Sometimes there might be more than one NE, but there can never be more than one
SPE.
7.
DonÕt think of NE as `goodÕ or `desirableÕ outcomes. Sometimes they are,
but as both the PD and the Fed / Congress game make clear, this isnÕt true in
general. A NE isnÕt necessarily the best state of affairs overall, or even the
best state of affairs for every player. ItÕs the best state of affairs for each
player given what the others are expected to do.
8.
There are different possible ways of thinking about NE philosophically.
ItÕs a bit sloppy to say that each player makes the best response given what
other players `have doneÕ or `will doÕ because this introduces a misleading
temporal dimension into the concept. Think of it this way instead. Player I
makes a conjecture about what another player X might do. Then she checks to
see how the other players, including herself, could all best respond together
to this strategy. Then she looks back at Player X. Does he now have an
alternative strategy that would get him a higher payoff? If the answer is `yesÕ
then Player I shouldnÕt believe her initial conjecture. Only
when Player I has checked every possible conjecture for every player, and
eliminated all the ones she shouldnÕt believe, does she know sheÕs found a NE.
Thus the best definition of NE is this one: A set (vector) of strategies is a
NE iff (1) each player has correct beliefs about the strategies of the others and
(2) the strategy of each is the best for herself, given her beliefs about the
strategies of the others.
9.
The PD is not a typical game in many respects. One of these respects is
that all its rows and columns are either strictly dominated or strictly dominant.
In any strategic-form game where this is true, elimination of strictly
dominated strategies is guaranteed to yield a unique NE. For many games this
condition does not apply, and then our analytic task is less straightforward.
10.
Sometimes games have no
strictly dominant strategies, but have strictly dominated strategies. Then we
can eliminate the latter. When we do that, we get a new matrix. This may cause
strictly dominant strategies to emerge, in which case we can find the NE. WeÕll
take up the example from Dixit and Skeath (p. 88):
Column
|
|
Low |
Medium |
High |
|
|
Top |
3, 1 |
2, 3 |
10, 2 |
|
| Row |
High |
4, 5 |
3, 0 |
6, 4 |
|
Low |
2, 2 |
5, 4 |
12, 3 |
|
|
Bottom |
5, 6 |
4, 5 |
9, 7 |
11.
Unfortunately, this
doesnÕt always work. Some games gave no strictly dominant or dominated
strategies.
12.
However, some games that
have no strictly dominant
or dominated strategies have weakly dominant or dominated ones. A strategy X for a player i
is weakly dominated if i has some other strategy Y such Y always gets i a payoff at least as good as X – that in every cell where i plays X he gets either the same payoff as when he
plays Y, or a worse payoff. We can get an example by slightly changing the
previous game as follows:
Column
|
|
Low |
Medium |
High |
|
|
Top |
3, 1 |
2, 3 |
10, 2 |
|
| Row |
High |
4, 5 |
3, 0 |
6, 4 |
|
Low |
2, 2 |
5, 4 |
12, 7 |
|
|
Bottom |
5, 6 |
5, 5 |
9, 3 |
13.
One must be careful
about eliminating weakly dominated strategies, because in their case the order
in which itÕs done matters. This is because some games have multiple NE. In such cases, elimination of weakly dominated
strategies can accidentally remove some NE, and which NE it removes and which
ones it leaves depends on the order in which the weakly dominated strategies
are eliminated. See p. 97 of Dixit and Skeath for an example. WeÕll come back
to this and other issues raised by games that have multiple NE later in the course.
14.
HereÕs a matrix in which
we can eliminate one row, but then we get stuck:
|
LL
LR
RL
RR |
||||||
|
LL
I RL RR |
3,3 |
3,3 |
0,5 |
0,5 |
||
|
3,3 |
3,3 |
0,5 |
0,5 |
|||
|
-1,0 |
4,5 |
-1,0 |
4,5 |
|||
|
-1,0 |
5,-1 |
-1,0 |
5,-1 |
|||
12.
When you canÕt eliminate
any rows or columns from a matrix, you have to adopt the tedious procedure of
locating each best response one by one. If we find a cell thatÕs a best
response for all players then weÕve found a NE. If we find no such cell, then
we know the gameÕs only NE is in mixed strategies.
13.
In a zero-sum game thereÕs a special
tactic for trying to find NE: the minimax method. ItÕs based on the following logic: you know that for
any strategy you pick, the other playerÕs best response will be the one that
gives you your worst payoff. Therefore, your best response to all her possible strategies must be the one that gives you
the highest among these. Meanwhile, sheÕs trying to pick the strategy that
yields her highest payoff. You want to hold her to the lowest of these. Then if
thereÕs one pair of strategies such that thereÕs nothing she can do to make you
worse off, that must be the best either of you can do, and so it must be a NE. HereÕs an example, with Player
IÕs worst – minimum – payoff for the corresponding row and Player
IIÕs best – maximum – payoff for each column written in at the end:
II
|
|
Left |
Middle |
Right |
Min |
|
|
Left |
20,60 |
40, 40 |
30, 50 |
20 |
|
| I |
Middle |
60,20 |
50, 30 |
80, 10 |
50 |
|
Right |
10,80 |
30, 50 |
10, 80 |
10 |
|
|
Max |
60 |
50 |
80 |
|
14.
To show how to represent
a 3-player game in strategic form, weÕll return to the three selfish neighbors
who want a common garden. But weÕre going to change their utility functions so
that for each player i:
6 =
i does not contribute, j and k do
5 =
i contributes, j and k do
4 =
i does not contribute, only one of
j or k does
3 =
i contributes, only one of j or k does
2 =
i does not contribute, neither of j
or k does
1
= i contributes, neither of j or k does
Now
to build a third dimension into two-dimensional matrices we need to add pages.
WeÕll represent ThaliaÕs strategies by making a separate page for each of her
two strategies. (If she had three possible strategies, weÕd need three pages,
and so on for every n. Note that
we could have chosen any player as the one for whom we add pages.)
Talia Contributes:
Nina
|
|
C |
D |
|
| Emily |
C |
5,5,5 |
3,6,3 |
|
D |
6,3,3 |
4,4,1 |
Talia DoesnÕt Contribute:
Nina
|
|
C |
D |
|
| Emily |
C |
3,3,6 |
1,4,4 |
|
D |
4,1,4 |
2,2,2 |
The
player represented on separate pages is Player III, so her payoffs are listed
third in each outcome.
Now
when we look for dominant strategies, we need to check both pages. Emily is better off not contributing whatever Nina
does on both pages. Therefore EmilyÕs dominant strategy is D, and we can
eliminate her C row on both pages. Nina is also better off not contributing
whatever Emily does on both pages. Therefore we can eliminate her C column on
both pages. For Thalia we compare her payoffs on matching cells across the two
pages. It turns out that Thalia has a dominant strategy D as well; therefore we
can eliminate the page on which
she plays C. And now thereÕs just one cell left: (D, D) on page 2. Thus this is
the NE. (WeÕve discovered that this is a 3-person PD. PDs involving more than 2
players are called tragedies of the commons because they lead to situations in which agents ruin
shared resources. They are much more common in real life than 2-player PDs.)
15.
Consult Dixit &
Skeath p. 105 to see how to solve this game using enumeration of best responses
instead of elimination of dominated strategies.
16.
Some games have multiple NE. If all that players care about is doing the same
thing as one another, or exactly the opposite of one another, then we get a
game with multiple NE called a pure coordination game. In the matrix below, Harry and Sally want to be at the
same coffee shop but donÕt care which one:
Sally
|
|
Starbucks |
L Latte |
|
| Harry |
Starbucks |
1,1 |
0,0 |