Optimal shill bidding in the VCG mechanism

This paper studies shill bidding in the Vickrey?CClarke?CGroves (VCG) mechanism applied to combinatorial auctions. Shill bidding is a strategy whereby a single decision-maker enters the auction under the guise of multiple identities (Yokoo et?al. Games Econ Behav, 46?pp. 174?C188, 2004). I formulate the problem of optimal shill bidding for a bidder who knows the aggregate bid of her opponents. A key to the analysis is a subproblem??the cost minimization problem (CMP)??which searches for the cheapest way to win a given package using shills. An analysis of the CMP leads to several fundamental results about shill bidding: (i) I provide an exact characterization of the aggregate bids b such that some bidder would have an incentive to shill bid against b in terms of a new property Submodularity at the Top; (ii) the problem of optimally sponsoring shills is equivalent to the winner determination problem (for single minded bidders)??the problem of finding an efficient allocation in a combinatorial auction; (iii) shill bidding can occur in equilibrium; and (iv) the problem of shill bidding has an inverse, namely the collusive problem that a coalition of bidders may have an incentive to merge (even after competition among coalition members has been suppressed). I show that only when valuations are additive can the incentives to shill and merge simultaneously disappear.