  The family of Groves mechanisms, which includes the well-known VCG mechanism
(also known as the Clarke mechanism), is a family of efficient and
strategy-proof mechanisms. Unfortunately, the Groves mechanisms are generally
not budget balanced. That is, under such mechanisms, payments may flow into or
out of the system of the agents, resulting in deficits or reduced utilities for
the agents. We consider the following problem: within the family of Groves
mechanisms, we want to identify mechanisms that give the agents the highest
utilities, under the constraint that these mechanisms must never incur
deficits.
  We adopt a prior-free approach. We introduce two general measures for
comparing mechanisms in prior-free settings. We say that a non-deficit Groves
mechanism $M$ {\em individually dominates} another non-deficit Groves mechanism
$M'$ if for every type profile, every agent's utility under $M$ is no less than
that under $M'$, and this holds with strict inequality for at least one type
profile and one agent. We say that a non-deficit Groves mechanism $M$ {\em
collectively dominates} another non-deficit Groves mechanism $M'$ if for every
type profile, the agents' total utility under $M$ is no less than that under
$M'$, and this holds with strict inequality for at least one type profile. The
above definitions induce two partial orders on non-deficit Groves mechanisms.
We study the maximal elements corresponding to these two partial orders, which
we call the {\em individually undominated} mechanisms and the {\em collectively
undominated} mechanisms, respectively.
