论文标题
组合拍卖的无债务付款规则
Non-decreasing Payment Rules for Combinatorial Auctions
论文作者
论文摘要
组合拍卖用于分配竞标者对商品捆绑的偏好偏好的域中的资源。但是，由于涉及的计算困难，在不同的付款规则下竞标者的行为尚未得到充分理解，因此在寻找此类拍卖的贝叶斯 - 纳什平衡方面的成功有限。在本文中，我们介绍了非偿还付款规则。根据这样的规则，当竞标者增加出价时，竞标者的付款不能减少，这是自然而理想的财产。 VCG-Nearest是实践中最常用的付款规则，违反了该财产，因此可以以令人惊讶的方式进行操纵。相比之下，我们表明许多其他付款规则是不续期的。我们还表明，一项非削减付款规则在拍卖游戏上实现了一个结构，使我们能够比一般情况下更有效地搜索近似贝叶斯 - 纳什平衡。最后，我们介绍了实用平面BNE算法，该算法利用了这种结构，并以多个数量级优于最先进的算法。
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.
