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 family of overbidding rules is introduced that price the assigned packages at a fixed average of the Vickrey price and the pay-as-bid price.