08.12.2014New Working Paper "Fairness Beyond the Core: New Payment Rules for Combinatorial Auctions"

Combinatorial spectrum auctions have been some of the biggest successes of auction design over the last 20 years. However, designing an optimal payment rule still remains a challenging problem. Unfortunately, in domains with complementarities, the classic VCG mechanism often produces prices outside the core. Informally, this means that VCG prices could be too low, such that some bidders would be willing to pay more than what the winners are paying. For this reason, recent auctions have employed \emph{core-selecting} payment rules. Day and Raghavan (2007) have argued that the core provides a fairness guarantee in that the winners' payments will be at least as high as the sum of the bids of any other coalition of bidders. However, we argue that the core primarily provides a fairness guarantee to losing bidders and says little about how payoffs are distributed among the winners.
In this paper, we propose an additional notion of fairness that goes beyond the core. We consider the fact that auction participants are often heterogeneous in size and value, and we study the distribution of winners' payoffs. We find that the most common pricing rule that has been used in practice, the Quadratic rule (Day and Cramton, 2012), is unfair towards small players participating in the auction. In contrast to prior work, which has only studied the Quadratic rule in stylized settings, we use computational methods to study approximate Bayes-Nash equilibria of payment rules in more complex settings. We propose alternative, fairer payment rules that improve upon the Quadratic rule while retaining its high efficiency. Our new rules involve novel bidder weightings, an ε-relaxation of the core, and new distance metrics to VCG prices. To find a payment rule that strikes an optimal trade-off between all design objectives (efficiency, core, fairness, revenue, and incentives), we have evaluated over 100 different payment rules via our computational Bayes-Nash equilibrium analysis.[pdf]