We study the complexity of bidding optimally in one-shot combinatorial auction mechanisms. Specifically, we consider the two most-commonly used payment rules: first-price and VCG-nearest. Prior work has largely assumed that bidders only submit bids on their bundles of interest. However, we show the surprising result that a single-minded bidder may lose an exponential amount of utility by playing his optimal simple strategy (only bidding on his bundle of interest) compared to playing his optimal complex strategy (which involves bidding on an exponential number of bundles). Our work suggests that it is important for future research on combinatorial auctions to fully take these effects into account.

翻译：我们用一次性组合拍卖机制对投标的复杂性进行了最佳的研究。 具体地说,我们考虑了两种最常用的付款规则:第一价和VCG最接近的付款规则。 先前的工作基本上假设投标人只对其利益包投标。 然而,我们显示了一个令人惊讶的结果,即一个心怀单心的投标人可能因他最理想的简单策略(只对其利益包投标)而损失了惊人的效用,而与其最佳的复杂策略相比(这涉及对数量惊人的捆包投标 ) 。 我们的工作表明,对组合拍卖的未来研究必须充分考虑到这些效果。