ejercicios teoria de juegos

Vista previa del material en texto

UC Berkeley
Fall 2007
Economics 201A - Section 6
Marina Halac
1 What we learnt this week
• Basics: trigger strategy
• Classes of games: infinitely repeated games, static Bayesian games
• Solution concepts: subgame perfect Nash equilibrium, Bayesian Nash equilibrium
• Applications: auction model
2 Problems
Problem 1: Infinitely repeated asymmetric prisoners’ dilemma
Consider an infinitely repeated game with discount factor δ and the following stage-game
C D
C 3, 2 -1, 3
D 5, -1 0, 0
(i) What are the payoffs in the worst possible SPNE?
(ii) What is the lowest discount factor δ∗ for which the players achieve cooperation in a SPNE?
(iii) Is it possible to achieve payoffs better than (0, 0) in a SPNE for discount factors lower than
δ∗? Hint: Think about a SPNE in which the players alternate between (C, D) and (D, C) on
the equilibrium path.
Problem 2: Equilibria with payoffs worse than Nash
Consider an infinitely repeated game with discount factor δ and the following stage-game
D E
D 0,0 -1,-1
E -1,-1 -2,-2
Assume δ > 1/2. Can (E,E) be played in a SPNE? Note that (E,E) gives payoffs (-2,-2) which
are lower than the payoffs achieved in the stage-game Nash equilibrium, (0,0). If your answer is
yes, propose strategies that sustain (E,E) in some period in a SPNE. If your answer is no, prove it.
Problem 3: Cournot oligopoly
Let Yk be player k’s payoff in his worst Nash equilibrium of the stage game. Let Dk(a1, ..., aN ) ≡
maxa∈Ak Uk(a1, ..., ak−1, a, ak+1, ..., aN ). In problem 11 of Problem Set Nagano, you are asked to
prove the following theorem: Consider a stage-game G and an action profile of G, (a1, ..., aN ), with
payoffs (X1, X2, ..., XN ) such that Xk > Yk. Then for all δ > maxk Dk−XkDk−Yk , there exists a SPNE of
G(T=∞,δ) where players play (a1, ..., aN ) each period.
1
Now consider n firms in a Cournot oligopoly. Inverse demand is given by P (Q) = a−Q, where
Q = q1 + ...+qn. Total costs for firm i are ci(qi) = cqi. Consider the infinitely repeated game based
on this stage game. Using the theorem above, find the lowest value of δ such that the firms can
sustain the monopoly output level in a SPNE. How does you answer vary with n?
Problem 4: Bayesian game
C D
A x,y 4,5
B 2,y x,3
Let x ∈ {3, 5} and y ∈ {4, 6}, independently drawn. Both values of x and both values of y are
equally likely. Suppose that each player knows his own payoff: player 1 observes x and player 2
observes y. Player 1 does not observe y and player 2 does not observe x. Find the BNE.
Problem 5: Cournot with asymmetric information (Gibbons 3.2)
Consider a Cournot duopoly operating in a market with inverse demand P (Q) = a − Q, where
Q = q1 + q2 is the aggregate quantity on the market. Both firms have total costs ci(qi) = cqi, but
demand is uncertain: it is high (a = aH) with probability θ and low (a = aL) with probability 1−θ.
Furthermore, information is asymmetric: firm 1 knows whether demand is high or low, but firm 2
does not. All of this is common knowledge. The two firms simultaneously choose quantities. What
are the strategy spaces for the two firms? Make assumptions concerning aH , aL, θ, and c such that
all equilibrium quantities are positive. What is the BNE of this game?
Problem 6: Second-price auction (MWG 8B3)
Consider the following action (known as second-price or Vickrey auction). An object is auctioned
off to I bidders. Bidder i’s valuation of the object is vi. Each bidder observes only his own valuation.
The auction rules are that each player submit a bid (a nonnegative number) in a sealed envelope.
The envelopes are then opened, and the bidder who has submitted the highest bid gets the object
but pays the auctioneer the amount of the second highest bid. If more than one bidder submits
the highest bid, each gets the object with equal probability. Show that submitting a bid of vi
with certainty is a weakly dominant strategy for bidder i. Also argue that this is bidder i’s unique
weakly dominant strategy.
Problem 7: First-price auction
Consider a first-price sealed-bid auction of an object with two bidders. Each bidder i’s valuation of
the object is vi. Each bidder observes only his own valuation. The valuation is distributed uniformly
and independently on [0, 1] for each bidder. The auction rules are that each player submit a bid in
a sealed envelope. The envelopes are then opened, and the bidder who has submitted the highest
bid gets the object and pays the auctioneer the amount of his bid. If the bidders submit the same
bid, each gets the object with probability 1/2. Derive the BNE of this auction. Hint: Look for an
equilibrium in which bidder i’s strategy is bi(vi) = civi for some constant ci.
2
3 Answers
Problem 1
(i) The payoffs in the worst SPNE are (0, 0). They are achieved by the repetition of the stage-
game Nash equilibrium (D,D). It is not possible to achieve payoffs worse than 0 since either
player can always guarantee himself a payoff of at least 0 by playing D in every period.
(ii) According to part (a) the worst available punishment has a payoff of 0 for both players. So
for neither player to want to deviate from (C, C), both of the following conditions must hold
5 6 3/(1− δ) ⇔ δ > 2/5 (deviation of player 1)
3 6 2/(1− δ) ⇔ δ > 1/3 (deviation of player 2)
We find that δ∗ = 2/5.
(iii) Yes. Define the following regimes: regime 1: play (C, D); regime 2: play (D, C). Then consider
the following strategies (for each player): Start in regime 1. If the outcome in regime 1 is
(C,D), go to regime 2; otherwise, play (D,D) forever. If the outcome in regime 2 is (D,C), go
to regime 1; otherwise, play (D,D) forever.
We now prove that there exists δ < δ∗ for which these strategies constitute a SPNE with
payoffs better than (0,0). In this SPNE, the players alternate between (C,D) and (D,C)
as long as neither player deviates, and deviations are punished by the stage-game Nash
equilibrium forever. For no player to want to deviate in any regime, the following conditions
must hold
3 6 5 − δ + 5δ2 − δ3... = (5− δ)/(1− δ2) always holds (player 1 in regime (D,C))
0 6 −1 + 3δ − δ2 + 3δ3... = (−1 + 3δ)/(1− δ2) holds if δ > 1/3 (player 2 in regime (D,C))
0 6 −1 + 5δ − δ2 + 5δ3... = (−1 + 5δ)/(1− δ2) holds if δ > 1/5 (player 1 in regime (C,D))
2 6 3 − δ + 3δ2 − δ3... = (3− δ)/(1− δ2) always holds (player 2 in regime (C,D))
Note also that no player deviates from (D,D) (in the subgame following deviation) as (D,D) is
a Nash equilibrium of the stage game. Hence, a SPNE in which the players alternate between
(C, D) and (D, C) exists if δ > 1/3 (note that 1/3 < δ∗). If players start in regime (C, D),
they get strictly positive payoffs of (−1 + 5δ)/(1− δ2) and (3− δ)/(1− δ2).
Problem 2
The answer is yes. For δ > 1/2, a SPNE that implements (E,E) in some period exists. Define the
following regimes: regime 1: play (E,E); regime 2: play (D,D). Consider the following strategies
(for each player): Start in regime 1. If outcome is (E,E) in regime 1, go to regime 2. Otherwise,
stay in regime 1. Regime 2 is absorbing.
We check that neither player wants to deviate in regimes 1 and 2. Regime 2 is a repetition of a
stage-game Nash equilibrium, so no player has incentives to deviate. In regime 1, if a player does
not deviate, his payoff is −2. If a player deviates once, his payoff is
−1− 2δ + 0δ2 + ... = −1− 2δ
Hence, a SPNE in which the players play (E,E) in the first period exists if δ > 1/2. (Note that I
used the One-Stage Deviation Principle: In a repeated game, a combination of players’ strategies
s is a SPNE iff no player can gain by deviating in a single stage, and confirming to s thereafter.)
3
Problem 3
The monopoly output is QM = (a− c)/2. Thus, if the n firms share the monopoly output equally,
each produces qM = (a− c)/(2n), with profit
πM =
(a− c)2
4n
A firm’s optimal stage-game deviation, qD, when the n− 1 other firms choose qM is
qD = arg max
q
q(a− (n− 1)a− c
2n
− q − c) = n+ 1
4n
(a− c)
This gives the deviator a profit level of
πD =
(n+ 1)2
16n2
(a− c)2
The unique stage-gameNE is for each firm to choose
qi = arg max
qi
qi(a− qi −
∑
j 6=i
qj − c) =
a−
∑
j 6=i qj − c
2
Solving the system of equations, the n-firm Cournot NE outcome involves each firm producing
qC = (a− c)/(n+ 1), with profit
πC =
(a− c)2
(n+ 1)2
Consider the proposed trigger-strategy for each player:
Play qM in period 1. In period t, play qM if all firms have played qM in all previous
periods; play qC otherwise.
Using the theorem above, these trigger strategies constitute a SPNE if
δ ≥ π
D − πM
πD − πC
=
(n+1)2
16n2
− 14n
(n+1)2
16n2
− 1
(n+1)2
≡ δ∗
Note that δ∗ → 1 as n→∞. Hence, collusion is harder to sustain when there are more firms.
Problem 4
Each player has two types: T1 = {t1L, t1H}, where t1L knows that x = 3 and t1H knows that x = 5,
and T2 = {t2L, t2H}, where t2L knows that y = 4 and t2H knows that y = 6. To find the BNE, note
that for type t1L, playing A strictly dominates playing B (regardless of his belief about player 2’s
action, A is t1L’s best response), and for type t2H , playing C strictly dominates playing D. Hence,
in any BNE, t1L plays A and t2H plays C.
Consider next type t1H . His expected payoff from playing A is
5p1(s2 = C|t1H) + 4(1− p1(s2 = C|t1H)) = 4 + p1(s2 = C|t1H)
4
and his expected payoff from playing B is
2p1(s2 = C|t1H) + 5(1− p1(s2 = C|t1H)) = 5− 3p1(s2 = C|t1H)
Thus, for t1H , playing A is a best response iff the probability that player 2 plays C is at least 1/4.
Now note that in equilibrium, the probability that player 2 plays C is always greater than 1/4,
since for any q ∈ [0, 1],
p1(s2 = C|t1H) = p1(t2H |t1H).1 + p1(t2L|t1H)q = 1/2 + q/2 > 1/2
Hence, in any BNE, t1H plays A.
Finally, consider type t2L. Regardless of what player 1 does, the payoff from playing C is always
y = 4 for this type. His expected payoff from playing D is
U2(s∗1L, D; t1L, t2L)p2(t1L|t2L) + U2(s∗1H , D; t1H , t2L)p2(t1H |t2L)
= U2(A,D; t1L, t2L)p2(t1L|t2L) + U2(A,D; t1H , t2L)p2(t1H |t2L) = 5 > 4
Hence, in any BNE, t2L plays D.
We have found that there exists a unique BNE with (s∗1L, s
∗
1H , s
∗
2L, s
∗
2H) = (A,A,D,C).
Problem 5
Firm 1’s strategy space is [0,∞)× [0,∞), and firm 2’s strategy space is [0,∞).
The strategies (q∗1L, q
∗
1H , q
∗
2) constitute a BNE iff
q∗1L = arg maxq q(aL − q − q
∗
2 − c),
q∗1H = arg maxq q(aH − q − q
∗
2 − c), and
q∗2 = arg maxq θq(aH − q − q
∗
1H − c) + (1− θ)q(aL − q − q∗1L − c)
The three first-order conditions are:
q∗1L =
aL − c− q∗2
2
,
q∗1H =
aH − c− q∗2
2
, and
q∗2 =
θaH + (1− θ)aL − c− (θq∗1H + (1− θ)q∗1L)
2
Therefore, the unique BNE is:
(q∗1L, q
∗
1H , q
∗
2) =
(
−θaH + (2 + θ)aL − 2c
6
,
(3− θ)aH − (1− θ)aL − 2c
6
,
θaH + (1− θ)aL − c
3
)
Problem 6
We prove that bidding vi is at least as good as any other bid no matter what other bids are.
Consider an alternative bid bi > vi. Case 1: There is another bid higher than bi. Then neither of
the bids wins the auction and so both give a payoff of 0. Case 2: The second highest bid is less
than vi. Then bidder i wins the auction and pays the same second highest bid in both cases. Both
bids give the same payoff. Case 3: The highest bid of other players is between vi and bi. Then bid
vi would lose the auction and give a payoff of 0. Bid bi would win the auction but the bidder would
5
have to pay more than his valuation, obtaining a negative payoff. Hence, bidding bi > vi is weakly
dominated by bidding vi.
Consider next an alternative bid bi < vi. Case 1: There is another bid higher than vi. Then
neither of the bids wins the auction and so both give a payoff of 0. Case 2: The second highest
bid is less than bi. Then bidder i wins the auction and pays the same second highest bid in both
cases. Both bids give the same payoff. Case 3: The highest bid of other players is between bi and
vi. Then bid bi would lose the auction and give a payoff of 0. Bid vi would win the auction and
the bidder would have to pay less than his valuation, obtaining a positive payoff. Hence, bidding
bi < vi is weakly dominated by bidding vi.
This argument implies that bidding vi is the unique weakly dominant strategy for player i.
Problem 7
Following the hint, suppose player j’s strategy is bj(vj) = cjvj . For a given value of vi, player i’s
best response solves
max
bi
(vi − bi)Pr(bi > bj) = (vi − bi)Pr(bi > cjvj)
(Note that we can ignore a tie since Pr(bi = bj) = 0 because bj(vj) = cjvj and vj is uniformly
distributed, so bj is uniformly distributed.) Now note that
Pr(bi > cjvj) = Pr(vj < bi/cj) = bi/cj
where the last equality uses bi/cj ∈ [0, 1], which follows from the fact that player i would not bid
below 0 nor above cj . Hence, player i’s best response is
bi(vi) = vi/2
The same analysis for player j yields
bj(vj) = vj/2
So each player submits a bid equal to half his valuation. This reflects the trade-off that a player
faces in an auction: the higher the bid, the more likely to win; the lower the bid, the larger the
gain if the player wins.
6