Sample Complexity of Automated Mechanism Design
The design of revenue-maximizing combinatorial auctions, i.e. multi-item auctions over bundles of goods, is one of the most fundamental problems in computational economics, unsolved even for two bidders and two items for sale. In the traditional economic models, it is assumed that the bidders' valuations are drawn from an underlying distribution and that the auction designer has perfect knowledge of this distribution. Despite this strong and oftentimes unrealistic assumption, it is remarkable that the revenue-maximizing combinatorial auction remains unknown. In recent years, automated mechanism design has emerged as one of the most practical and promising approaches to designing high-revenue combinatorial auctions. The most scalable automated mechanism design algorithms take as input samples from the bidders' valuation distribution and then search for a high-revenue auction in a rich auction class. In this work, we provide the first sample complexity analysis for the standard hierarchy of deterministic combinatorial auction classes used in automated mechanism design. In particular, we provide tight sample complexity bounds on the number of samples needed to guarantee that the empirical revenue of the designed mechanism on the samples is close to its expected revenue on the underlying, unknown distribution over bidder valuations, for each of the auction classes in the hierarchy. In addition to helping set automated mechanism design on firm foundations, our results also push the boundaries of learning theory. In particular, the hypothesis functions used in our contexts are defined through multi-stage combinatorial optimization procedures, rather than simple decision boundaries, as are common in machine learning.
This paper deals with the sample complexity of automated mechanism design for the problem of maximizing the revenue in a combinatorial auction (CA). Given a class of auction mechanisms, the automated mechanism design takes as input samples from the bidders’ valuation distribution (which, in practice, may be the history records from the previous auctions), and output the choice of auction mechanism with high revenue. This work presents several upper bounds on the sample complexities for various auction classes.  Although Morgenstern and Roughgarden (reference [19] in this paper) studied the same problem of bounding the sample complexities of CA, their work only deals with “simple auctions” which can be reduced to the single-bidder setting. In contrast, this paper studies the hierarchy of deterministic CA families consists of VCG-based mechanisms. As opposed to sequential auctions, these auction classes have more complex structure, and provide the auctioneer more degrees of freedom in designing mechanism.   In particular, the authors study the affine maximizer auction (AMA), the virtual valuation CA (VVCA), the lambda-auction, the mixed bundling auction with reserve prices (MBARPs) and the mixed bundling auction (MBA). For AMA, VVCA and lambda-auction, the authors provide certain negative results. Firstly, an exponential upper bound on the Rademacher complexity of the revenue function is given for the class AMA. (Theorem 2) Based on this, an exponential upper bound on sample complexity for all these three classes is provided, while two exponential lower bounds are provided for lambda-auction and VVCA respectively as complementary results (Theorem 1).   For the less general models MBARPs and MBA, on the other hand, many positive results are given. For MBA with only 2 bidders, the authors first show that the pseudo-dimension is 2 (theorem 3), and provide a polynomial upper bound on sample complexity (Theorem 4). Then the authors generalize these results for the general case with n bidders (Theorem 5, 6). Finally, the authors provide polynomial upper bounds on the pseudo-dimension and sample complexity of MBARPs.
This paper appears to be mostly a followup on the work of [19], "learning simple auctions" where techniques used to prove generalization error bounds were used to help reason about the design of mechanisms. In the present submission, the authors focus a much broader classes of auctions (affine maximize auction, virtual valuation CA, lambda-auction, mixed bundling auction with reserve price, and mixed bundling auction), and provide much more general results.  The techniques and results are interesting. But in the context of the previous work already introducing the underlying idea that you can apply learning theory to mechanism design problems of this form, I do wonder whether the results are suitably exciting to deserve publication in NIPS. (The paper is clearly above the bar for other conference venues)