Reviews: Sample Complexity of Automated Mechanism Design

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.