講義 6：ゲーム理論と不完全競争
上級ミクロ経済学—財務省理論研修
安田 洋祐
政策研究大学院大学（GRIPS）
2012年6月11日
1 / 29
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 / 29
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 Sidenote 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. Examples for such strategies are prices or quantities set by firms.
◮ Let (s1, ..., s
n) denote a strategy profile (戦略プロファイル), i.e., a combination of strategies, and let s−idenote 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 / 29
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.
Def 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 max
si∈Siui(s
∗
1, ..., s∗i−1, si, s∗i+1, ..., s∗n).
4 / 29
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:
◮ If one prisoner confesses and the other one does not, the former will be given a reward of 1 and the latter will receive a fine equal to 2.
◮ If both confess, each will receive a fine equal to 1.
◮ If neither confesses, both will be set free.
This situation can be expressed by the payoff (bi-)matrix (利得表):
1 2 Silent Confess
Silent (沈黙) 0, 0 −2, 1 Confess (自白) 1, − 2 −1, − 1
5 / 29
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 / 29
Strategic Dominance | 戦略的支配
Below are useful concepts to discuss “better” or “best” strategies:
◮ A strategy siis weakly dominated (弱く支配される) by s′iif the payoff of playing s′iis always larger than that of choosing si:
ui(s′i, s−i) ≥ ui(si, s−i) for all s−i∈ S−iand ui(s′i, s−i) > ui(si, s−i) for at least one s−i∈ S−i.
◮ A strategy siis strictly dominated (強く支配される) by s′iif ui(s′i, s−i) > ui(si, s−i) for all s−i∈ S−i.
◮ A strategy s′iis a weakly dominant strategy (弱支配戦略) if playing si 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′iis a strictly dominant strategy (強支配戦略) if ui(s′i, s−i) > ui(si, s−i) for all si6= s′i and s−i∈ S−i.
7 / 29
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 extensionof strategies, mixed strategies (混合戦略), will almost always assure the existence of equilibrium.
8 / 29
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 likesuch as matching pennies, we will extend the strategy space and the concept of equilibrium.
Def 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 σiassigns 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 / 29
Mixed Strategies | 混合戦略 (2)
When σiassigns 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 / 29
Existence of Mixed-Strategy Equilibrium | 混合戦略均衡の存在
Def 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.
A pure strategy Nash equilibrium (純粋戦略均衡) is a pure strategy profile that satisfies the same conditions. The following theorem establishes the existence of mixed strategy Nash equilibrium (混合戦略均衡).
Thm 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 / 29
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 ridepends only on σ−iand not on σi, we write it as a function of the strategies of all players (including i as well), 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 / 29
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,σbn) → (σ, 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 Σiis 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 / 29
Existence of Pure-Strategy Equilibrium | 純粋戦略均衡の存在 The following theorem guarantees the existence of pure-strategy Nash equilibrium.
Thm 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 / 29
Indifference Property | 無差別の性質 (1)
Indifference Property Since expected utilities are linear in the probabilities, if a player uses a (non-degenerate) mixed strategy in a Nash equilibrium, she must be indifferent (無差別) between all pure strategies to which she assigns positive probability.
That is, for any two pure strategies siand s′ichosen with positive probabilities in equilibrium, i.e., σ∗i(si), σ∗i(s′i) > 0, we must have
ui(si, σ−i∗ ) = ui(s′i, σ
∗
−i) = ui(σi∗, σ
∗
−i).
Application Asymmetric Matching Pennies (非対称マッチング・ペニー) Consider a slightly modified version of the matching pennies (assume x > 0):
1 2 Heads Tails Heads −x, x 1, −1
Tails 1, −1 −1, 1
15 / 29
Indifference Property | 無差別の性質 (2)
✄
✂ ✁
Q Calculate a Nash equilibrium. For what values of x, does player 2 choose
“Heads” with higher probability than “Tails”?
✄
✂A Let p✁ ibe the probability for player i to choose “Heads.” Then, by indifference property, player 1 must be indifferent between the two strategies,
u1H= p2(−x) + (1 − p2) = p2− (1 − p2) = u1T.
⇒ p2= 2 3 + x.
Similarly, the indifference property for player 2 gives, u2H= p1x− (1 − p1) = −p1+ (1 − p1) = u2T.
⇒ p1= 2 3 + x.
Note that p2≥12 if and only if x ≤ 1. Moreover, p2 is decreasing in x, which implies that player 2 chooses “Heads” less often if winning payoff of {Heads, Heads} becomes larger.
16 / 29
Oligopoly Models | 寡占モデル
We have looked at the extreme market structures of monopoly and perfect competition. However, most real-world markets are somewhere between them:
◮ The number of the firms is more than one but less than the “very large number.”
◮ The situation in which there are a few competitors is called oligopoly (寡 占): (duopoly (複占) if the number is two).
One thing the monopoly (独占) and perfect competition (完全競争) have in common is that each firm does not have to worry about its rivals’ reactions.
◮ In the case of monopoly, this is trivial as there are no rivals.
◮ In the case of perfect competition, the idea is that each firm is so small that its actions have no significant impact on rivals.
An important characteristic of oligopolies is the strategic interdependence between competitors, which is appropriately analyzed by game theory.
17 / 29
Extension: Demand and Cost | 拡張：需要と費用 (1)
Consider the slightly general version of the Cournot duopoly model in which the market demand is given by
p= a − b(q1+ q2),
and the firms’ marginal costs are c1and c2, respectively.
In Nash equilibrium, each firm tries to maximize her profit given other firm’s (equilibrium) strategy:
maxqi [a − b(qi+ qj) − ci]qi.
The first order condition provides the best reply (BR) function: dπi
dqi
= a − 2bqi− bqj− ci= 0.
⇒ qi= ri(qj) =a− ci 2b −
qj
2 for i = 1, 2, i 6= j.
18 / 29
Extension: Demand and Cost | 拡張：需要と費用 (2)
Def When the best reply function is downward sloping, we call it strategic substitution (戦略的代替). On the other hand, if BR is upward sloping, then it is strategic complementarity (戦略的補完).
The Nash equilibrium (q∗1, q∗2) becomes as follows: q1∗= a− 2c1+ c2
3b and q
∗ 2=
a− 2c2+ c1
3b .
The equilibrium market price is
p∗= a − b(q∗1+ q∗2) =a+ (c1+ c2)
3 .
The equilibrium profit for each firm is πi∗= (qi∗)2= 1
3b(a − 2ci+ cj)
2.
Note that q∗i and π∗i are increasing in cj while decreasing in ci.
19 / 29
Extension: Number of Firms | 企業の数
Suppose there are n firms, and the marginal costs are identical (= c) across them. Then, the best reply becomes
dπi
dqi
= a − 2bqi− bq−i− c = 0
⇒ qi=a− c 2b −
q−i
2 for i = 1, ..., n,
where q−i=Pj6=iqj. Solving the linear equations (you can assume the equilibrium being symmetric, i.e., q1∗= · · · = q∗n), we obtain
qi∗= a− c b(n + 1), q
∗= n(a − c) b(n + 1) and p
∗= a+ nc n+ 1.
It follows that the markup (マークアップ率) at the equilibrium becomes m∗=p
∗− c
p∗ = a− c a+ nc.
As the number of firms (= n) increases, the following comparative statics are obtained: (1) individual quantity decreases, (2) total quantity increases, (3) market price decreases, and (4) markup decreases. If the number converges to infinity, the markup is going to zero, i.e., market power vanishes.
20 / 29
Bertrand with Product Differentiation | ベルトランと製品差別化 (1)
Consider the Bertrand duopoly model of differentiated products in which the demand for each firm is given as
qi= a − pi+ bpj for i = 1, 2, i 6= j, where 0 < b < 2.
◮ That is, the demand increases as its own price decreases while the rival’s price increases.
◮ The firms have different marginal costs c1and c2, respectively.
In Nash equilibrium, each firm tries to maximize her profit given other firm’s (equilibrium) strategy:
maxpi (pi− ci)(a − pi+ bqj).
21 / 29
Bertrand with Product Differentiation | ベルトランと製品差別化 (2)
By the first order condition, we obtain the BR: dπi
dpi
= a − 2pi+ bpj+ ci= 0.
⇒ pi= ri(pj) = a+ ci
2 +
bpj
2 for i = 1, 2, i 6= j.
✄
✂Rm Since the best reply is upward sloping, it shows strategic✁ complementarity.
Solving the pair of equations yields p∗1= a
2 − b+
2c1+ bc2
(2 − b)(2 + b). p∗2= a
2 − b+
2c2+ bc1
(2 − b)(2 + b).
22 / 29
【補論】 Hotelling Model | ホテリング・モデル (1)
Two convenience stores are going to open new shops on the street.
◮ Each store has to decide the location between 0 and 1.
◮ Customers are located uniformly on the street, and each customer goes to the nearest shop.
◮ If both shops choose the same location, each receives half of the customers.
◮ Each store is going to maximize the number of customers. The game is defined as follows:
◮ Players: Two stores, 1, 2.
◮ Strategies: Shop location along the street, si∈ [0, 1] for i = 1, 2.
◮ Payoffs: The number of customers described by
ui= 8< :
si+sj 2
1 −si+s2 j
if si≤ sj
if si> sj
for i = 1, 2, i 6= j.
23 / 29
【補論】 Hotelling Model | ホテリング・モデル (2)
There is a unique Nash equilibrium where both shops open at the middle, (0.5, 0.5), which is shown by the following three steps:
1. Choosing separate locations never becomes a NE.
2. Choosing the same location other than the middle point also fails to be a NE.
3. If both shops choose the middle, then no one has an incentive to change the location.
✄
✂Rm The equilibrium is often referred as the principle of minimum✁ differentiation (最小差別化の原理) to explain little product differentiation, agglomeration of shops, similar target policies set by two political parties (the median voter theorem (中位者投票定理)), and so on.
✄
✂Q What does happen if there are more than two players?✁
24 / 29
【補論】 Bertrand Model of Duopoly | ベルトランの複占モデル (1)
Two firms producing perfectly substitutable goods (完全代替財), i.e., no product differentiation, compete in their prices.
◮ A downward demand function is given, D(p).
◮ The firms have a common marginal cost c.
◮ The firm with lower price will serve the entire market demand: if the price is the same, each firm serves the half of it.
The game is defined as follows:
◮ Players: Two firms, 1, 2.
◮ Strategies: Prices they will charge, pi∈ [0, ∞) for i = 1, 2.
◮ Payoffs: Profits described by
πi= 8>
>>
<
>>
>:
(pi− c)D(pi)
(pi−c)D(pi) 2
0
if pi< pj
if pi= sj
if pi> pj
for i = 1, 2, i 6= j.
25 / 29
【補論】 Bertrand Model of Duopoly | ベルトランの複占モデル (2)
There is a unique Nash equilibrium in which both firms charge the price equal to their common marginal cost, i.e., p1= p2= c. (If there are n firms, p1= ... = pn= c will be the unique equilibrium.) This is shown by the following three steps:
1. Charging different prices (by firms) never becomes a NE.
2. Charging the same price other than the marginal cost also fails to be an equilibrium.
3. If both firms choose pi= c, then no firm has an (strict) incentive to change the price.
Bertrand Paradox Even if there are only two competitors, prices will be set at the level of marginal cost. In reality, there are many industries that look suitable for the Bertrand model but prices are higher than marginal cost. There are at least three explanations which can reasonably resolve this Bertrand paradox: 1) product differentiation, 2) capacity constraints, and 3) dynamic interaction, i.e., collusion (or cartel).
26 / 29
【補論】 Cournot Model of Duopoly | クールノーの複占モデル (1)
Two firms producing perfectly substitutable goods (no product differentiation) compete in their quantities.
◮ A (inverse) linear demand function is given, p = a − q.
◮ The firms have a common marginal cost c.
◮ The market price is set equal to the highest price that clears the market. That is,
p= a − (q1+ q2). The game is defined as follows:
◮ Players: Two firms, 1, 2.
◮ Strategies: Quantities they will produce, qi∈ [0, ∞) for i = 1, 2.
◮ Payoffs: Profits described by πi= [a − (q1+ q2) − c]qi
for i = 1, 2, i 6= j.
27 / 29
【補論】 Cournot Model of Duopoly | クールノーの複占モデル (2)
✄
✂ ✁
Q How can we derive a Nash equilibrium of this game?
In Nash equilibrium, each firm tries to maximize her profit given other firm’s (equilibrium) strategy:
maxqi [a − (qi+ qj) − c]qi.
This is just a unconstrained optimization problem (assuming qjis given). The first order condition gives best reply (BR) function:
dπi
dqi
= a − 2qi− qj− c = 0
⇒ qi= ri(qj) =a− c
2 −
qj
2 for i = 1, 2, i 6= j.
The Nash equilibrium (q∗1, q∗2) must satisfy these equations. Solving the simultaneous equations, we obtain
q1∗= q∗2 =a− c 3 .
28 / 29
【補論】 Bertrand or Cournot? | ベルトランかクールノーか？
One may want to ask “Which model should we use?”
◮ Both the Bertrand and Cournot models can be seen as particular cases of a more general model of oligopoly where firms choose prices and quantities (or capacities.)
◮ Bertrand is more reasonable when firms can adjust capacities faster than prices, e.g., software.
◮ Cournot is more appropriate when prices can vary faster than capacities, e.g., wheat, cement.
These models are different games, i.e., price vs. quality competition, but we do notneed different solution concepts.
◮ The single solution concept (Nash equilibrium) can explain different market outcomes depending on the situations.
◮ In other words, we do not need different assumptions about firms’ behaviors. Once a model is specified, then Nash equilibrium gives us the result of the game.
29 / 29
