Groves class of mechanisms are the only efficient allocation mechanisms that are DSIC
in quasi-linear environment. To obtain a mechanism which is more budget balanced in
Groves class, a rebate (or) redistribution was introduced by Moulin in [16] in the pay-
ment of VCG mechanism. A rebate function determines the redistributions back to the
agents of a portion of the VCG payments. The choice of these rebates should be such
that the DSIC property of the mechanism is preserved. Moreover, the mechanism should
be anonymous, i.e., two agents with identical bids should get identical rebates. The con-
dition for obtaining an anonymous and DSIC rebate function is given in the following
theorem.
Theorem 1. Suppose that agents bid scalar values and that the scalar parameterized value
functions satisfy Assumption 1. Then, any mechanism with deterministic and anonymous
redistributions is DSIC if and only if the rebate function can be written as
r
i
= f (
1
,
2
, . . . ,
i-1
,
i+1
, . . . ,
n
)
for some f with arguments satisfying
1
2
. . .
i-1
i+1
. . .
n
.
Proof. The proof is identical to that in Guo & Conitzer [15].
The payment for the new mechanism with rebates, one that remains within the Groves
class of mechanisms, is given by
p
i
() =
j=i
v
j
(a
-i,j
(
-i
),
j
) -
j=i
v
j
(a
j
(),
j
) - r
i
(
-i
).
(2.2)
The rebate function in Theorem 1 should preserve all the desirable properties of the VCG
14