Game Theory
Daniel Guetta, based on `Microeconomic Theory' by MWG
Game Theory deals with situations in which the utility the other player hid their action). These nodes are
of one player depends on the actions on some of the aggregated in an information set, a subset of a given
other players as well as their own. player's decision nodes at a given time. Note that every
decision node in an information set must have the same
set of possible actions.
1 Basic elements of noncooperative
games De
nition 1. (Perfect information) A game is
one of perfect information if each information set
contains a single decision node. Otherwise, it is a
Example game of imperfect information.
Sealed-bid auctions : First-price auction: the win-
ner pays his valuation. Second-price auction: the
winner pays the second highest bid. All pay Chance can be introduced by adding `nature' as a
auction: everyone pays their bid, regardless of player, with a probability associated to each branch.
whether they win or lose.
Oligopolist models : n > 1
rms. Each has the
ability to produce any quantity qi of a product at
cost Ci (qi ). 1.2 Normal Form Representation
Cournot : quantity competition. Firms simul-
taneously and secretly choose their outputs, De
nition 2. (Strategy) Let
and the price is determined by the inverse
market demand • Hi denote the collection of player i's informa-
tion sets.
p = p (σi qi )
• A denote the set of possible actions in the
The pro
t of
rst i is game.
• C(H) ⊂ A denote the set of actions possible
Πi (q1 , · · · , qn ) = q1 p (σi qi ) − Ci (qi ) at information set H .
A strategy for player i is a function si : Hi → A
Bertrandt : price competition. Firms simul-
such that si (H) ∈ C(H) for all H ∈ Hi .
taneously and secretly choose their prices
pi . These are then revealed and demand
D(pm in) is realised. All
rms who posted
that price share in the demand (and pro
ts) Clearly, if we have every possible strategy as well as the
equally. outcomes from each strategy, we have a full description
of the game.
1.1 Extensive Representation De
nition 3. (Normal form representation)
For a game with ` players, the normal form rep-
The extensive form of a game involves a game tree resentation ΓN speci
es (for each player) a set of
this shows every possible move every player could strategies Si and a payo function ui (s1 , · · · , s` )
make, sequentially. (with si ∈ Si for all i), giving von Neumann-
Morgenstern utility levels associated with the (pos-
It is possible that, before his move, the player could sibly random) outcome arising from strategies
be at any one of a number of nodes (for example, if
1
, We denote
s1 , · · · , s` . Formally,
s−i = (s1 , · · · , si−1 , si+1 , · · · , s` )
ΓN = [`, {Si }, {ui (·)}]
S−i = S1 × · · · × Si−1 × Si+1 × · · · × S`
Every extensive representation has a unique normal
form representation. The reverse is not true some 2.1 Dominant and Dominated Strategies
information is lost in the normal form.
De
nition 5. (Strictly dominant strategy) A
1.3 Randomized choices strategy si ∈ Si is a strictly dominant strategy for
player i if for all s0i 6= si , we have
De
nition 4. (Mixed strategy) Given a player ui (si , s−i ) > ui (s0i , s−i )
i's (
nite) pure strategy set Si , a mixed strategy for
for all s−i ∈ S−i .
this player, denoted σi : Si → [0, 1], assigns to each
pure strategy si ∈ Si a probability σi (si ) ≥ 0 that The strategy si is said to be weakly dominant if
it will be played (with probabilities summing to 1). the inequality above is strict for at least one s0i ,
but possibly soft for the others.
(All possible mixed strategies for player i lie on a sim-
plex, which we denote ∆(Si )). We therefore denote a Rational players never play strictly dominated strate-
normal form game with mixed strategies by gies. The argument for weakly dominated strategies
is not as strong, since there are always some strategies
ΓN = [`, {∆(Si )}, {ui (·)}] that the opponent might play against which the weakly
dominated strategy performs just as well. A weakly
This randomization over strategies induces a random- dominated strategy can only be declared irrational in
ization over terminal nodes. Letting S = S1 × · × a situation in which the player knows his opponent puts
S` , player i's von Neumann-Morgenstern utility from positive probability on every strategy available to him.
mixed strategy pro
le σ is Note that if we assume full information and, further,
" `
# that every player knows the other player is rational, we
can go through multiple iterations of deleting strictly
X Y
ui (s) σi (si )
s∈S i=1 dominated strategies. The order in which such strate-
gies are deleted does not matter. Deleting weakly dom-
inated strategies results in a game that does depend
Note that an alternative representation of randomized
on the order of deletion (because the assumption an
choices that uses the extensive version of the game
opponent puts positive probability on all strategies is
is through a behaviour strategy, which, for every in-
incorrect if some of those are weakly dominated and
formation set, associates a probability to each action.
will be deleted).
For games of perfect recall (in which a player remem-
bers what he did in every previous move), Kunh (1953)
showed that these two concepts are identical. De
nition 6. (Strictly dominant mixed
strategy) A strategy σi ∈ ∆(Si ) is strictly dom-
inated for player i if there exists another strategy
2 Simultaneous Move Games σi0 ∈ ∆(Si ) such that for all σ−i ∈
Q
j6=i ∆(Sj )
ui (σi0 , σ−i ) > ui (σi , σ−i )
Given a a normal form game ΓN , can be predict what
will happen?
2
Daniel Guetta, based on `Microeconomic Theory' by MWG
Game Theory deals with situations in which the utility the other player hid their action). These nodes are
of one player depends on the actions on some of the aggregated in an information set, a subset of a given
other players as well as their own. player's decision nodes at a given time. Note that every
decision node in an information set must have the same
set of possible actions.
1 Basic elements of noncooperative
games De
nition 1. (Perfect information) A game is
one of perfect information if each information set
contains a single decision node. Otherwise, it is a
Example game of imperfect information.
Sealed-bid auctions : First-price auction: the win-
ner pays his valuation. Second-price auction: the
winner pays the second highest bid. All pay Chance can be introduced by adding `nature' as a
auction: everyone pays their bid, regardless of player, with a probability associated to each branch.
whether they win or lose.
Oligopolist models : n > 1
rms. Each has the
ability to produce any quantity qi of a product at
cost Ci (qi ). 1.2 Normal Form Representation
Cournot : quantity competition. Firms simul-
taneously and secretly choose their outputs, De
nition 2. (Strategy) Let
and the price is determined by the inverse
market demand • Hi denote the collection of player i's informa-
tion sets.
p = p (σi qi )
• A denote the set of possible actions in the
The pro
t of
rst i is game.
• C(H) ⊂ A denote the set of actions possible
Πi (q1 , · · · , qn ) = q1 p (σi qi ) − Ci (qi ) at information set H .
A strategy for player i is a function si : Hi → A
Bertrandt : price competition. Firms simul-
such that si (H) ∈ C(H) for all H ∈ Hi .
taneously and secretly choose their prices
pi . These are then revealed and demand
D(pm in) is realised. All
rms who posted
that price share in the demand (and pro
ts) Clearly, if we have every possible strategy as well as the
equally. outcomes from each strategy, we have a full description
of the game.
1.1 Extensive Representation De
nition 3. (Normal form representation)
For a game with ` players, the normal form rep-
The extensive form of a game involves a game tree resentation ΓN speci
es (for each player) a set of
this shows every possible move every player could strategies Si and a payo function ui (s1 , · · · , s` )
make, sequentially. (with si ∈ Si for all i), giving von Neumann-
Morgenstern utility levels associated with the (pos-
It is possible that, before his move, the player could sibly random) outcome arising from strategies
be at any one of a number of nodes (for example, if
1
, We denote
s1 , · · · , s` . Formally,
s−i = (s1 , · · · , si−1 , si+1 , · · · , s` )
ΓN = [`, {Si }, {ui (·)}]
S−i = S1 × · · · × Si−1 × Si+1 × · · · × S`
Every extensive representation has a unique normal
form representation. The reverse is not true some 2.1 Dominant and Dominated Strategies
information is lost in the normal form.
De
nition 5. (Strictly dominant strategy) A
1.3 Randomized choices strategy si ∈ Si is a strictly dominant strategy for
player i if for all s0i 6= si , we have
De
nition 4. (Mixed strategy) Given a player ui (si , s−i ) > ui (s0i , s−i )
i's (
nite) pure strategy set Si , a mixed strategy for
for all s−i ∈ S−i .
this player, denoted σi : Si → [0, 1], assigns to each
pure strategy si ∈ Si a probability σi (si ) ≥ 0 that The strategy si is said to be weakly dominant if
it will be played (with probabilities summing to 1). the inequality above is strict for at least one s0i ,
but possibly soft for the others.
(All possible mixed strategies for player i lie on a sim-
plex, which we denote ∆(Si )). We therefore denote a Rational players never play strictly dominated strate-
normal form game with mixed strategies by gies. The argument for weakly dominated strategies
is not as strong, since there are always some strategies
ΓN = [`, {∆(Si )}, {ui (·)}] that the opponent might play against which the weakly
dominated strategy performs just as well. A weakly
This randomization over strategies induces a random- dominated strategy can only be declared irrational in
ization over terminal nodes. Letting S = S1 × · × a situation in which the player knows his opponent puts
S` , player i's von Neumann-Morgenstern utility from positive probability on every strategy available to him.
mixed strategy pro
le σ is Note that if we assume full information and, further,
" `
# that every player knows the other player is rational, we
can go through multiple iterations of deleting strictly
X Y
ui (s) σi (si )
s∈S i=1 dominated strategies. The order in which such strate-
gies are deleted does not matter. Deleting weakly dom-
inated strategies results in a game that does depend
Note that an alternative representation of randomized
on the order of deletion (because the assumption an
choices that uses the extensive version of the game
opponent puts positive probability on all strategies is
is through a behaviour strategy, which, for every in-
incorrect if some of those are weakly dominated and
formation set, associates a probability to each action.
will be deleted).
For games of perfect recall (in which a player remem-
bers what he did in every previous move), Kunh (1953)
showed that these two concepts are identical. De
nition 6. (Strictly dominant mixed
strategy) A strategy σi ∈ ∆(Si ) is strictly dom-
inated for player i if there exists another strategy
2 Simultaneous Move Games σi0 ∈ ∆(Si ) such that for all σ−i ∈
Q
j6=i ∆(Sj )
ui (σi0 , σ−i ) > ui (σi , σ−i )
Given a a normal form game ΓN , can be predict what
will happen?
2
