Designing Core-selecting Payment Rules

We study the design of core-selecting payment rules for combinatorial auctions (CAs), a challenging setting where no strategyproof rules exist. Unfortunately, under the rule most commonly used in practice, the Quadratic rule (Day and Cramton, 2012), the Bayes-Nash equilibrium strategies are untruthful enough such that truthful play may be an implausible model of bidder behavior, which also raises concerns about revenue and efficiency. In this paper, we present a computational approach for finding good core-selecting payment rules. We present a parametrized payment rule we call Fractional* that takes three parameters (reference point, weights, and amplification) as inputs. This way, we construct and analyze 366 rules across 29 different domains. To evaluate each rule in each domain, we employ a computational Bayes-Nash equilibrium solver. We first use our approach to study the well-known Local-Local Global domain in detail, and identify a set of 20 "all-rounder rules" which beat Quadratic by a significant margin on efficiency, incentives, and revenue in all, or almost all domains. To demonstrate robustness of our findings,we take four of these all-rounder rules and evaluate them in the significantly larger LLLLGG domain (with six bidders and eight goods), where we show that all four rules also beat Quadratic. This suggests that, in practice, auctioneers may want to consider using alternative core-selecting payment rules because of the large improvements over Quadratic that may be available. Overall, our results demonstrate the power of a computational search approach in a properly parametrized mechanism design space.