Overbidding and underbidding in package allocation problems

Abstract

We study the problem of allocating packages of different objects to a group of bidders. A rule is overbidding-proof if no bidder has incentives to bid above his actual valuations. We prove that if an efficient rule is overbidding-proof, then each winning bidder pays a price between his winning bid and what he would pay in a Vickrey auction for the same package. In counterpart, the set of rules that satisfy underbidding-proofness always charge a price below the corresponding Vickrey price. A new characterization of the Vickrey allocation rule is provided with a weak form of strategy-proofness. The Vickrey rule is the only rule that satisfies efficiency, individual rationality, overbidding-proofness and underbidding-proofness. Our results are also valid on the domains of monotonic valuations and of single-minded bidders. Finally, a rule is introduced that is overbidding proof and its payoffs are bidder-optimal in the core of the auction game according the reported valuations.