Optimal Shill Bidding in the VCG Mechanism

This paper studies shill bidding in the 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 (Sakurai, Yokoo, and Matsubara 1999). 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–which searches for the cheapest way to win a given package using shills. This formulation leads to an exact characterization of the aggregate bids b such that some bidder would have an incentive to shill bid against b. It is well known that when goods are substi-tutes, there is no incentive to shill bid. In contrast, I show that when goods are pure complements, the incentive to shill takes a simple form: there is an incentive to disintegrate and bid for each item using a different identity. With a mix of substitutes and complements, I show that the winner determination problem (for single minded bidders)–the problem of finding an efficient allocation in a combinatorial auction–can be embedded into the optimal shill bidding problem. Shill bidding is closely related to collusion. Setting aside the ordinary incentive to suppress competition, the disin-centive to disintegrate using shills when facing a substitutes valuation translates into an incentiv