Game Development Reference
In-Depth Information
( t 1 ( θ ) ,...,t n ( θ )) is the vector of the resulting payments. If t i ( θ )
0, player
i receives from the central authority t i ( θ ), and if t i ( θ ) < 0, he pays to the
central authority
.
The following definition then captures the idea that taxes prevent manip-
ulations. We say that a direct mechanism with tax function t is incentive
compatible if for all θ
|
t i ( θ )
|
and θ i
Θ, i
∈{
1 ,...,n
}
Θ i
u i (( f, t )( θ i −i ) i ) ≥ u i (( f, t )( θ i −i ) i ) .
Intuitively, this means that for each player i announcing one's true type ( θ i )
is better than announcing another type ( θ i ). That is, false announcements,
i.e., manipulations, do not pay off.
From now on we focus on specific incentive compatible direct mechanisms.
Each Groves mechanism is a direct mechanism obtained by using a tax
function t ( · ):=( t 1 ( · ) ,...,t n ( · )), where for all i ∈{ 1 ,...,n}
• t i R is defined by t i ( θ ):= g i ( θ )+ h i ( θ −i ), where
• g i ( θ ):= j = i v j ( f ( θ ) j ),
h i −i R
is an arbitrary function.
Note that, not accidentally, v i ( f ( θ ) i )+ g i ( θ ) is simply the initial social
welfare from the decision f ( θ ).
The importance of Groves mechanisms is then revealed by the following
crucial result due to Groves [1973].
Theorem 1.28 (Groves) Consider a decision problem ( D, Θ 1 ,..., Θ n ,v 1 ,
...,v n ,f ) with an e cient decision rule f. Then each Groves mechanism is
incentive compatible.
Proof The proof is remarkably straightforward. Since f is e cient, for all
θ ∈ Θ, i ∈{ 1 ,...,n} and θ i Θ i we have
n
u i (( f, t )( θ i −i ) i )=
v j ( f ( θ i −i ) j )+ h i ( θ −i )
j =1
n
v j ( f ( θ i −i ) j )+ h i ( θ −i )
j =1
= u i (( f, t )( θ i −i ) i ) .
Θwehave i =1 t i ( θ )
When for a given direct mechanism for all θ
0,