Game Development Reference
InDepth Information
the mechanism is called
feasible
, which means that it can be realised without
external financing.
Each Groves mechanism is uniquely determined by the functions
h
1
,...
,
h
n
. A special case, called the
pivotal mechanism
, is obtained by using
d∈D
j
=
i
h
i
(
θ
−i
):=
−
max
v
j
(
d, θ
j
)
.
So then
t
i
(
θ
)=
j
=
i
d∈D
j
=
i
v
j
(
f
(
θ
)
,θ
j
)
−
max
v
j
(
d, θ
j
)
.
Hence for all
θ
and
i ∈{
1
,...,n}
we have
t
i
(
θ
)
≤
0, which means that
the pivotal mechanism is feasible and that each player needs to make the
payment
to the central authority.
We noted already that the decision rules used in Examples 1.26 and 1.27 are
e
cient. So in each example Groves' Theorem 1.28 applies and in particular
the pivotal mechanism is incentive compatible. Let us see now the details.

t
i
(
θ
)

Re: Example 1.26
Given a sequence
θ
of reals we denote by
θ
∗
its reordering
from the largest to the smallest element. So for example, for
θ
=(1
,
5
,
4
,
3
,
2)
we have (
θ
−
2
)
2
= 3 since
θ
−
2
=(1
,
4
,
3
,
2).
To compute the taxes in the sealedbid auction in the case of the pivotal
mechanism we use the following observation.
Note 1.29
In the sealedbid auction we have for the pivotal mechanism
t
i
(
θ
)=
θ
2
−
if
i
=
argsmax θ
0
otherwise
.
Exercise 1.10
Provide the proof.
So the highest bidder wins the object and pays for it the amount max
j
=
i
θ
j
.
The resulting sealedbid auction was introduced by Vickrey [1961] and is
called a
Vickrey auction
. To illustrate it suppose there are three players,
A, B, and C whose true types (bids) are respectively 18, 21, and 24. When
they bid truthfully the object is allocated to player C whose tax (payment)
according to Note 1.29 is 21, so the second price offered. Table 1.1 summarises
the situation.
This explains why this auction is alternatively called a
secondprice
auction
. By Groves' Theorem 1.28 this auction is incentive compatible. In
contrast, the
firstprice auction
, in which the winner pays the price he
Search Nedrilad ::
Custom Search