The Pseudo-Dimension of Near-Optimal Auctions
This paper develops a general approach, rooted in statistical learning theory, to learning an approximately revenue-maximizing auction from data. We introduce t-level auctions to interpolate between simple auctions, such as welfare maximization with reserve prices, and optimal auctions, thereby balancing the competing demands of expressivity and simplicity. We prove that such auctions have small representation error, in the sense that for every product distribution F over bidders' valuations, there exists a t-level auction with small t and expected revenue close to optimal. We show that the set of t-level auctions has modest pseudodimension (for polynomial t) and therefore leads to small learning error. One consequence of our results is that, in arbitrary single-parameter settings, one can learn a mechanism with expected revenue arbitrarily close to optimal from a polynomial number of samples.
This paper addresses the problem of learning reserve prices that approximately maximize revenue, using sample draws from an unknown distribution over bidder valuations. The authors introduce t-level auctions, in which (roughly speaking) each bidder's bid space is effectively discretized into levels, and the bidder whose bid falls on the highest level wins and pays the lowest value that falls on its lowest level required to win. The authors bound the number of samples needed to find an approximately revenue-maximizing auction from all auctions in a set C (e.g., from the set of 10-level auctions). They bound the difference in revenue between the revenue-maximizing t-level auction and the optimal auction. Results are presented for single-item auctions but are generalized to matroid settings and single-parameter settings.This paper is well-written and does a good job of comparing/contrasting the problem, approach, and results to other relevant papers in the literature. The work is novel and makes connections across multiple disciples (auction theory and learning theory). The paper is of very strong technical quality, with some of the most interesting technical results extending into the appendix. One issue that might be of practical importance: after a particular t-level auction is implemented, there is likely information lost about the subsequent bidder valuations. While truth-telling is a dominant strategy, so is reporting the lowest value that falls on the same level as the bidder's true value. If the bidder is concerned about revealing information to the auctioneer (e.g., it thinks the bidder may try to re-learn the optimal reserves in a subsequent period, in the case that F is non-stationary), it seems reasonable to think that the bidder would choose this "lowest value on interval" strategy, since it gets the same payment and allocation as truthfully reporting but reveals less information to the auctioneer. If the auctioneer wants to re-learn optimal reserves in the future or otherwise understand how bidders will respond to a change in the mechanism, losing some precision in observed bidder valuations could be problematic.As a more fundamental side-note: I understand the theoretical importance in any case, so this point does not really impact my score, but I am a little skeptical of the value of revenue-maximizing auctions in practice, at least in some well-studied real-world domains, because they don't capture the fact that bidders are often making decisions over time, and extracting as much revenue as possible in the current auction doesn't necessarily coincide with maximizing long-term revenue. I would be curious to hear any normative statement from the authors (in either direction) about the practical importance of optimal auctions in real-world domains, or how to otherwise reconcile this tension in optimizing short- versus long-term revenue. If there is space and a good argument to be made, adding a comment to the paper would be valuable.Minor question: in a footnote it is mentioned that results hold for other tie-breaking rules. Which ones? It may be worth calling out whether results hold when ties are broken uniformly at random (my initial thought is that results would not hold, but the authors probably have a definitive answer).