Game Development Reference
In-Depth 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 sealed-bid auction in the case of the pivotal
mechanism we use the following observation.
Note 1.29
In the sealed-bid 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 sealed-bid 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 second-price
auction . By Groves' Theorem 1.28 this auction is incentive compatible. In
contrast, the first-price auction , in which the winner pays the price he
Search Nedrilad ::




Custom Search