Mechanism Design Theory II Bayesian Nash Equilibrium

Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Mechanism Design Theory II
Bayesian Nash Equilibrium Implementation
May 4, 2014
#
1/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Outline
1 Bayesian Nash equilibrium (BNE) implementation
2 Specializing to Quasi-Linear Utility
3 Necessary and sufficient conditions for BNE implementation
#
2/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Bayesian Nash Equilibrium (BNE)
Implementation
1
BNE: s (·) is a BNE of the game induced by Γ if ∀i and ∀θi ∈ Θi
Eθ˜−i ui (g (si (θi ), s−i (θ˜−i )), θi ) | θi ≥ Eθ˜−i ui (g (si0 , s−i (θ˜−i )), θi ) | θi ,
∀si0 ∈ Si .
2
3
Indirect implementation: The mechanism Γ implements f (·) in BNE
if Γ has a BNE, s (θ ), such that g (s (θ )) = f (θ ), ∀θ ∈ Θ.
Direct implementation: f (·) is truthfully implementable in BNE, if
si (θi ) = θi , ∀θi ∈ Θi , ∀i, is a BNE of the direct mechanism
Γ = (Θ1 , . . . , ΘI , f (·)), i.e. if ∀i and ∀θi ∈ Θi
Eθ˜−i ui (f (θi , θ˜−i ), θi | θi ) ≥ Eθ˜−i ui (f (θi0 , θ˜−i ), θi | θi ) , ∀θi0 ∈ Θi .
#
3/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Bayesian Nash Equilibrium (BNE)
Implementation
1
BNE: s (·) is a BNE of the game induced by Γ if ∀i and ∀θi ∈ Θi
Eθ˜−i ui (g (si (θi ), s−i (θ˜−i )), θi ) | θi ≥ Eθ˜−i ui (g (si0 , s−i (θ˜−i )), θi ) | θi ,
∀si0 ∈ Si .
2
3
Indirect implementation: The mechanism Γ implements f (·) in BNE
if Γ has a BNE, s (θ ), such that g (s (θ )) = f (θ ), ∀θ ∈ Θ.
Direct implementation: f (·) is truthfully implementable in BNE, if
si (θi ) = θi , ∀θi ∈ Θi , ∀i, is a BNE of the direct mechanism
Γ = (Θ1 , . . . , ΘI , f (·)), i.e. if ∀i and ∀θi ∈ Θi
Eθ˜−i ui (f (θi , θ˜−i ), θi | θi ) ≥ Eθ˜−i ui (f (θi0 , θ˜−i ), θi | θi ) , ∀θi0 ∈ Θi .
#
3/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Bayesian Nash Equilibrium (BNE)
Implementation
1
BNE: s (·) is a BNE of the game induced by Γ if ∀i and ∀θi ∈ Θi
Eθ˜−i ui (g (si (θi ), s−i (θ˜−i )), θi ) | θi ≥ Eθ˜−i ui (g (si0 , s−i (θ˜−i )), θi ) | θi ,
∀si0 ∈ Si .
2
3
Indirect implementation: The mechanism Γ implements f (·) in BNE
if Γ has a BNE, s (θ ), such that g (s (θ )) = f (θ ), ∀θ ∈ Θ.
Direct implementation: f (·) is truthfully implementable in BNE, if
si (θi ) = θi , ∀θi ∈ Θi , ∀i, is a BNE of the direct mechanism
Γ = (Θ1 , . . . , ΘI , f (·)), i.e. if ∀i and ∀θi ∈ Θi
Eθ˜−i ui (f (θi , θ˜−i ), θi | θi ) ≥ Eθ˜−i ui (f (θi0 , θ˜−i ), θi | θi ) , ∀θi0 ∈ Θi .
#
3/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Revelation Principle for BNE Strategies
Proposition
Suppose Γ implements f (·) in BNE. Then f (·) is truthfully
implementable in BNE.
In other words: if f (·) is indirectly implementable, it is also directly
implementable.
Proof: Since Γ implements f (·) in BNE, there exists a BNE s (θ ) such
that g (s (θ )) = f (θ ), ∀θ, i.e. for all i and for all θi
Eθ˜−i ui (g (si (θi ), s−i (θ˜−i ), θi ) | θi ≥ Eθ˜−i ui (g (si0 , s−i (θ˜−i ), θi ) | θi , ∀si0 ∈ Si
Therefore, in particular:
Eθ˜−i ui (g (si (θi ), s−i (θ˜−i ), θi ) | θi ≥ Eθ˜−i ui (g (si (θi0 ), s−i (θ˜−i ), θi ) | θi ,
∀θi0 ∈ Θi
#
4/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
continued ...
Because g (s (θ )) = f (θ ), ∀θ it follows that for all i
Eθ˜−i ui (f (θi , θ˜−i ), θi ) | θi ≥ Eθ˜−i ui (f (θi0 , θ˜−i ), θi ) | θi , ∀θi0 ∈ Θi
Hence, f (·) is truthfully implementable in BNE.
Corollary
1) If you want to know which social choice function can be implemented,
you only need to find out which social choice function can be truthfully
implemented.
This reduces the design of optimal institutions to an operational
optimization problem.
2) Useful test: a strategy profile s (θ ) is not an equilibrium of a game Γ if
the social choice function implemented by s (θ ) is not truthfully
implementable.
#
5/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Outline
1 Bayesian Nash equilibrium (BNE) implementation
2 Specializing to Quasi-Linear Utility
3 Necessary and sufficient conditions for BNE implementation
#
6/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
BNE Implementation with Quasi–Linear
Utility Functions
Let x = (k, t ), k ∈ <I (allocation vector), t ∈ <I (transfer vector),
f (θ ) = (k (θ ), t (θ )), iid random types, and assume
ui (x , θi ) = θi vi (k ) + ti .
Define θi : true state, θˆi : reported state, Θi := (θ i , θ¯i ), and
v¯i (θˆi ) : = Eθ˜−i [v (k (θˆi , θ˜−i )]
t¯i (θˆi ) : = Eθ˜−i [t (θˆi , θ˜−i )]
(expected benefit)
(expected transfer)
U¯ i (θˆi , θi ) : = θi v¯i (θˆi ) + t¯i (θˆi ) (expected payoff)
Ui (θi ) : = U¯ i (θi , θi ) = θi v¯i (θi ) + t¯i (θi ) (expected payoff at truthtelling)
. . . all conditional on all other players telling the truth.
#
7/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Outline
1 Bayesian Nash equilibrium (BNE) implementation
2 Specializing to Quasi-Linear Utility
3 Necessary and sufficient conditions for BNE implementation
#
8/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Necessary and Sufficient Conditions for
BNE Implementation
Q: Which social choice rules f (·) are truthfully implementable in BNE?
Proposition
The social choice rule f (·) = (k (·), t (·)) is truthfully implementable in
BNE iff
v¯i (θi )
is non decreasing
Ui (θi ) = Ui (θi ) +
Z θi
(1)
v¯i (s )ds.
(2)
θi
#
9/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Proof of necessity
1) Necessity: Consider two types, θi , θˆi ∈ Θi , and let θˆi > θi . Since f (.)
is truthfully implementable in BNE
Ui (θi ) ≥ U¯ i (θˆi , θi ) = Ui (θˆi ) + (θi − θˆi )v¯i (θˆi )
Ui (θˆi ) ≥ U¯ i (θi , θˆi ) = Ui (θi ) + (θˆi − θi )v¯i (θi )
Hence,
Ui (θˆi ) − Ui (θi )
v¯i (θˆi ) ≥
≥ v¯i (θi )
θˆi − θi
which proves monotonicity (1). Taking the limit, limθˆi →θi gives
Ui0 (θi ) = v¯i (θi ). Integration implies (2).
#
10/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Proof of sufficiency
2) Sufficiency: Let θˆi < θi . By (2) and (1)
Ui (θi ) − Ui (θˆi ) =
Z θi
θˆi
v¯i (s )ds ≥ v¯i (θˆi )
Z θi
θˆi
ds = (θi − θˆi )v¯i (θˆi )
Hence,
Ui (θi ) ≥ Ui (θˆi ) + (θi − θˆi )v¯i (θˆi ) = U¯ i (θˆi , θi )
Similarly, one can show that Ui (θˆi ) ≥ U¯ i (θi , θˆi ). Therefore, f (·) is
truthfully implementable in BNE.
#
11/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
How to construct a choice rule that is
truthfully implementable in BNE?
• Choose the k (·) function in such a way that the expected benefit
functions, v¯i (θi ), are non decreasing (in the auctions setting: choose
monotone expected probabilities of winning y¯i (θi ))
• Choose the transfers in such a way that:
Ui (θi )
| {z }
= Ui (θi ) +
Z θi
v¯i (s )ds
θi
θi v¯i (θi )+t¯i (θ )
i.e., t¯i (θi ) = Ui (θi ) +
Z θi
v¯i (s )ds − θi v¯i (θi ).
θi
• To assure voluntary participation (if that is required), choose
Ui (θ i ) ≥ 0. This is sufficient since Ui (θi ) is monotone increasing.
#
12/13
Bayesian Nash equilibrium (BNE) implementation
Specializing to Quasi-Linear Utility
Necessary and sufficient conditions for BNE implementation
Standard Applications
Next, we cover the following applications:
1
Matching
2
Public Goods Problem
3
Auctions
4
Bilateral Trade under two-sided private information
(Myerson/Satterwhaite Theorem)
#
13/13

Download Report