Title: Non-Decreasing Payment Rules for Combinatorial Auctions
Abstract: 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 the notion of "non-decreasing" payment rules. Under such a rule, the payment of a bidder cannot decrease as he increases his bid, which is a natural and desirable property. However, VCG-nearest, a payment rule 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. Furthermore, we 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. We present an algorithm that exploits this structure and outperforms a recent state of the art algorithm by multiple orders of magnitude.
