Game Development Reference
InDepth 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,
Search Nedrilad ::
Custom Search