  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. Our main result is an impossibility theorem which rules out linear
rebate functions with non-zero efficiency 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 are possible when the valuations for the objects are correlated. In
the second approach, we show that rebate functions with non-zero efficiency are
possible if linearity is relaxed.
