Lecture 4: Static Games
Advanced Microeconomics II
Yosuke YASUDA
Osaka University, Department of Economics yasuda@econ.osaka-u.ac.jp
December 2, 2014
1 / 14
Game Theory: Introduction
Game theory is the formal analysis of decision making in situations of strategic interactions, where the optimal strategy for one player depends on the strategies chosen by others.
A (non-cooperative) game can be formalized in two different ways, in its normal-form and in its extensive-form.
We start with one-shot simultaneous move games, which are best analyzed in their normal-form.
The normal-form representation of a game specifies its:
1 Players in the game.
2 Strategies available to each player.
3 Payoffs received by each player for each combination of strategies that could be chosen by the players.
2 / 14
Game Theory: Notations
The below are basic notations used in game theory.
Players are numbered from 1 to n and an arbitrary player is called player i.
Let Si denote i’s strategy space, i.e., the set of strategies available to player i, and let si(∈ Si) denote an arbitrary member of this set.
Let (s1, ..., sn) denote a strategy profile, i.e., a combination of strategies, and let s−i denote a strategy profile other than player i’s strategy, (s1, ..., si−1, si+1, ..., sn).
Let ui : S1× · · · × Sn→ R denote player i’s payoff function: ui(s1, ..., sn) is the payoff to player i if the players choose the strategies (s1, ..., sn).
3 / 14
Nash Equilibrium
Suppose that game theory makes a unique prediction about the strategy each player will choose. In order for this prediction to be correct, it is necessary that each player be willing to choose the strategy predicted by the theory.
Thus, each player’s predicted strategy must be that player’s best response to the predicted strategies of the other players.
Definition 1
In the n-player normal-form game, the strategy profile (s∗1, ..., s
∗ n)
is a Nash equilibrium if, for each player i, s∗i is player i’s best response to the strategies specified for n − 1 other players:
ui(s∗1, ..., s∗n) ≥ ui(si, s∗−i)
for every feasible strategy si ∈ Si. In other words, s∗i solves
smaxi∈Si
ui(s∗1, ..., s∗i−1, si, s∗i+1, ..., s∗n).
4 / 14
Prisoner’s Dilemma (1)
Two suspects are charged with a joint crime, and they are held separately by the police. Each prisoner is told the following (assume that a plea bargain is allowed):
If both confess, each receives 3 years imprisonment. If neither confesses, both receive 1 year.
If one confesses and the other one does not, the former will be set free immediately (0 payoff) and the latter receives 5 years. This situation can be expressed by the payoff (bi-)matrix:
1 2 Silent Confess
Silent −1, − 1 −5, 0 Confess 0, − 5 −3, − 3
5 / 14
Prisoner’s Dilemma (2)
Remarks on Payoff Matrix
Any two players game (with finite number of strategies) can be expressed as a bi-matrix.
The payoffs to the two players when a particular pair of strategies is chosen are given in the appropriate cell. The payoff to the row player (= player 1) is given first, followed by the payoff to the column player (= player 2). The unique Nash equilibrium is (Confess, Confess):
“Confess” is an optimal strategy no matter what other players will do, i.e., a dominant strategy for each player.
The unique Nash equilibrium outcome (Confess, Confess) is not Pareto efficient, since (Silent, Silent) Pareto dominates it.
6 / 14
Strategic Dominance
Below are useful concepts to discuss “better” or “best” strategies: A strategy si is weakly dominated by s′i if the payoff of playing s′i is always larger than that of choosing si:
ui(s′i, s−i) ≥ ui(si, s−i) for all s−i ∈ S−i and ui(s′i, s−i) > ui(si, s−i) for at least one s−i ∈ S−i. A strategy si is strictly dominated by s′i if
ui(s′i, s−i) > ui(si, s−i) for all s−i ∈ S−i.
A strategy s′i is a weakly dominant strategy if playing s′i is optimal for any combination of other players’ strategies:
ui(s′i, s−i) ≥ ui(si, s−i) for all s ∈ S and ui(s′i, s−i) > ui(si, s−i) for at least one s ∈ S. A strategy s′i is a strictly dominant strategy if
ui(s′i, s−i) > ui(si, s−i) for all si 6= s′i and s−i∈ S−i.
7 / 14
Matching Pennies
Matching Pennies The following game called “matching pennies”does not have a Nash equilibrium.
1 2 Heads Tails Heads −1, 1 1, −1
Tails 1, −1 −1, 1
In this game, a player’s strategy space is {Heads, Tails}. Each player has a penny and must choose whether to display it with heads or tails facing up.
If the two pennies match, then player 2 wins player 1’s penny; if the pennies do not match, then 1 wins 2’s penny.
Although the existence of Nash equilibrium is not guaranteed, the natural extension of strategies, mixed strategies, will almost always assure the existence of equilibrium.
8 / 14
Mixed Strategies (1)
No pair of strategies satisfies the Nash equilibrium condition.
→ Can’t we provide any theoretical prediction or stable outcomes? To analyze the games without Nash equilibrium such as matching pennies, we will extend the strategy space and the concept of equilibrium in what follows.
Definition 2
A mixed strategy for player i is a probability distribution, denoted by σi, over (some of) the strategies in Si= {s1, ..., sJ}.
We will denote the space of player i’s mixed strategy by Σi, whose element σi(sj) is the probability that σi assigns to sj. That is, σi= (σi(s1), ..., σi(sJ)) satisfies
0 ≤ σi(sj) ≤ 1 for j = 1, 2, ..., J, and σi(s1) + · · · + σi(sJ) = 1.
9 / 14
Mixed Strategies (2)
When σi assigns probability 1 to some strategy sj (σi(sj) = 1), we call it a pure strategy. We assume that
Each player’s randomization is “statistically independent” of those of her opponents.
The payoffs to a profile of mixed strategies are the expected values of the corresponding pure strategy payoffs.
In other words, players’ preferences satisfy the expected utility hypothesis and payoffs are vNM expected utilities.
The space of mixed strategy profiles is denoted Σ = Σ1× · · · × Σn, with element σ. Player i’s payoff to profile σ is
ui(σ) =X
s∈S
σ1(s1) × · · · × σn(sn)ui(s)
=X
s∈S
( Yn i=1
σi(si))ui(s).
10 / 14
Existence of Mixed-Strategy Nash Equilibrium
Definition 3
A mixed-strategy profile σ∗ is a Nash equilibrium if, ui(σi∗, σ∗−i) ≥ ui(σi, σ∗−i) for all σi∈ Σi, for all players i, which is equivalent to
ui(σi∗, σ∗−i) ≥ ui(si, σ−i∗ ) for all si ∈ Si.
The following theorem establishes the existence of mixed strategy Nash equilibrium.
Theorem 4
Every finite normal-form game (the game has finitely many players and strategies) has at least one mixed-strategy equilibrium.
Recall that a pure strategy equilibrium is an equilibrium in degenerate (i.e., a special case of) mixed strategies.
11 / 14
Sketch of the Proof (1)
The idea of the proof is to apply Kakutani’s fixed-point theorem to the players’ best reply (BR) correspondences.
Player i’s BR correspondence, ri, maps each strategy profile σ = (σ1, ..., σn) to the set of mixed strategies that maximize player i’s payoff when her opponents play σ−i.
Although ri depends only on σ−i and not on σi, we write it as a function of the strategies of all players, because later we will look for a fixed point in the space Σ of strategy profiles. Define the correspondence r : Σ ⇒ Σ be the Cartesian product of players’ best reply correspondences, r1, ..., rn.
A fixed point of r is a σ∗ such that σ∗∈ r(σ∗), so that, for each player, σ∗i ∈ ri(σ∗).
Thus, a fixed point of r is a Nash equilibrium.
12 / 14
Sketch of the Proof (2)
From Kakutani’s theorem, the following is the set of sufficient conditions for r : Σ ⇒ Σ to have a fixed point:
1 Σ is a compact, convex, nonempty subset of a (finite-dimensional) Euclidean space.
2 r(σ) is nonempty for all σ.
3 r(σ) is convex for all σ.
4 r(·) has a closed graph: If (σn,bσn) → (σ, bσ) with bσn∈ r(σn), then bσ∈ r(σ). (also called as upper hemi-continuity) Let us check conditions 1 and 2. (Verify 3 and 4 by yourself.)
1 Each Σi is a simplex of dimension |Si| − 1.
2 Each player’s payoff function is linear, and therefore
continuous in her own mixed strategy. Note that continuous functions on compact sets attain maximum point by
Weierstrass theorem.
13 / 14
Existence of Pure-Strategy Nash Equilibrium
The following theorem guarantees the existence of pure-strategy Nash equilibrium.
Theorem 5
Suppose that the strategy sets are nonempty convex and compact subsets of Euclidean space and the payoff to firm i is continuous in the actions of all firms and quasi-concave in its own action. Then, there exists a pure-strategy Nash equilibrium.
The proof applies Kakutani’s fixed point theorem to the best reply mapping defined over pure-strategy profiles.
1 Continuity of payoffs and compactness of strategy sets imply that best reply correspondences are upper hemi-continuous.
2 Quasi-concavity of payoffs and convexity of strategy sets implies that they are convex valued.
3 It also follows that the equilibrium set is compact.
14 / 14
