The Cost of Simple Bidding in Combinatorial Auctions

We study a class of manipulations in combinatorial auctions where bidders fundamentally misrepresent what goods they are interested in. Prior work has largely assumed that bidders only submit bids on their bundles of interest, which we call simple bidding: strategizing over the bid amounts, but not the bundle identities. However, we show that there exists an entire class of auction instances for which simple bids are never optimal in BNE, always being strictly dominated by complex bids (where bidders bid on goods they are not interested in). We show this result for the two most widely used auction mechanisms: first price and VCG-nearest. We also explore the structural properties of the winner determination problem that cause this phenomenon, and we use the insights gained to investigate how impactful complex bidding manipulations may be. We find that, in the worst case, a bidder's optimal complex bid may require bidding on an exponential number of bundles, even if the bidder is interested only in a single good. Thus, this phenomenon can greatly impact the auction's outcome, and should not be ignored by bidders and auction designers alike.