Combinatorial auctions are used to allocate resources in domains where bidders have complex preferences over bundles of goods. However, the behavior of bidders under different payment rules is not well understood, and there has been limited success in finding Bayes-Nash equilibria of such auctions due to the computational difficulties involved. In this paper, we introduce non-decreasing payment rules. Under such a rule, the payment of a bidder cannot decrease when he increases his bid, which is a natural and desirable property. VCG-nearest, the payment rule most commonly used in practice, violates this property and can thus be manipulated in surprising ways. In contrast, we show that many other payment rules are non-decreasing. We also show that a non-decreasing payment rule imposes a structure on the auction game that enables us to search for an approximate Bayes-Nash equilibrium much more efficiently than in the general case. Finally, we introduce the utility planes BNE algorithm, which exploits this structure and outperforms a state-of-the-art algorithm by multiple orders of magnitude.
翻译:合并拍卖用于在投标人对成批货物有复杂偏好的领域分配资源。 但是,对于不同支付规则下的投标人的行为,人们并没有很好地理解,而且由于所涉及的计算困难,在找到这种拍卖的Bayes-Nash平衡方面,也取得了有限的成功。在本文中,我们引入了非削减付款规则。根据这样的规则,如果投标人增加投标,则其付款不能减少,而投标人是自然和可取的财产。VCG-nearest,这是实践中最常用的付款规则,违反这种财产,因而可以令人吃惊地加以操纵。相比之下,我们表明许多其他支付规则是非削减性的。我们还表明,非削减付款规则在拍卖游戏上规定了一种结构,使我们能够比一般情况下更高效地寻找大约的Bayes-Nash平衡。最后,我们引入了通用飞机BNE算法,它利用了这种结构,并超越了多种数量级的状态算法。