  There are p heterogeneous objects to be assigned to n competing agents (n >
p) each with unit demand. It is required to design a Groves mechanism for this
assignment problem satisfying weak budget balance, individual rationality, and
minimizing the budget imbalance. This calls for designing an appropriate rebate
function. When the objects are identical, this problem has been solved which we
refer as WCO mechanism. We measure the performance of such mechanisms by the
redistribution index. We first prove an impossibility theorem which rules out
linear rebate functions with non-zero redistribution index in heterogeneous
object assignment. Motivated by this theorem, we explore two approaches to get
around this impossibility. In the first approach, we show that linear rebate
functions with non-zero redistribution index are possible when the valuations
for the objects have a certain type of relationship and we design a mechanism
with linear rebate function that is worst case optimal. In the second approach,
we show that rebate functions with non-zero efficiency are possible if
linearity is relaxed. We extend the rebate functions of the WCO mechanism to
heterogeneous objects assignment and conjecture them to be worst case optimal.
