Designing revenue-maximizing combinatorial auctions (CAs) is a critical yet elusive problem in computational economics, unsolved even for two bidders and two items for sale. Rather than attempting to characterize the optimal combinatorial auction, there has been research into automated mechanism design, wherein the design of a high-revenue CA conducted algorithmically via a search over a parameterized class of incentive-compatible, individually-rational CAs. In this line of work, it is assumed that the algorithm has access to random samples from the distribution over the bidders’ valuations. However, until now, there has not been a theory that relates the performance of the designed mechanism on the samples and its performance on the underlying, unknown distribution over valuations. In this paper, we fill that gap and along the way, we uncover the geometric, structural underpinnings of the hierarchy of deterministic combinatorial auction classes, which include affine maximizer auctions, λ-auctions, virtual valuations combinatorial auctions, mixed bundling auctions, and mixed bundling auctions with reserve prices. We obtain these result by analyzing the revenue functions of these auction classes using learning-theoretic tools such as Rademacher complexity and pseudo-dimension.
This is joint work with Nina Balcan and Tuomas Sandholm.
BIO:
Ellen is a first year PhD student in the computer science department at CMU, coadvised by Nina Balcan and Tuomas Sandholm. Her research interests are in learning theory and mechanism design.