  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 Bayes-Nash
equilibrium, 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 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.
