Smoothed Analysis of Online Non-parametric Auctions
Open Access
- 7 July 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 540-560
Abstract
Online learning of revenue-optimal auctions is a fundamental problem in mechanism design without priors. Nevertheless, all the existing positive results assume that the auctioneer optimizes over a parameterized class of auctions, such as pricings and auctions with reserves. This is perhaps not surprising given that natural correlations that occur in online sequences pose a challenge to characterizing a succinct class of revenue-optimal auctions. This has left behind a significant gap in our understanding of online-learnability of general classes of non-parametric auctions. We provide the first positive results for online learnability of a non-parametric auction class, for smooth adversaries and the class of smooth auctions. In a nutshell, an online adversary is smooth (in the style of Smoothed analysis [Spielman and Teng, 2004] in online learning [Haghtalab et al., 2021]) if the bid distribution has bounded density at every time step, and an auction is smooth if the level sets of its revenue function have small boundaries. We prove the following fundamental guarantees: (1) Revenue maximization in the class of smooth auctions is online-learnable, against smooth adversaries. (2) It is impossible to construct a no-regret algorithm even for the class of smooth auctions against worst-case adversaries. (3) It is impossible to construct a no-regret algorithm for the class of all incentive-compatible auctions even against smooth adversaries. This gives a strong characterization of when and which class of non-parametric auctions are online-learnable. To illustrate the generality of the class of smooth auctions we show that it contains the class of all monotone-revenue auctions, as well as, the class of all competition-monotone auctions. This brings up an interesting observation: while independence across bids leads to the optimal auctions being monotone, significantly weaker assumptions, compared to monotonicity of revenue, are sufficient for learnability.Keywords
Funding Information
- Army Research Office (W911NF-17-1-0304)
- National Science Foundation (CCF-2145898)
This publication has 16 references indexed in Scilit:
- Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization2018
- Online Auctions and Multi-scale Online Learning2017
- A PAC Approach to Application-Specific Algorithm Selection2016
- Regret Minimization for Reserve Prices in Second-Price AuctionsIEEE Transactions on Information Theory, 2014
- Smoothed analysis of algorithmsJournal of the ACM, 2004
- On prediction of individual sequencesThe Annals of Statistics, 1999
- Neural Network Learning1999
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- Scale-sensitive dimensions, uniform convergence, and learnabilityJournal of the ACM, 1997
- Learnability and the Vapnik-Chervonenkis dimensionJournal of the ACM, 1989