Cherlin Zhu, Columbia University

Abstract

In the framework of "algorithms with predictions,'' algorithms are augmented with a machine-learned prediction and the goal is to obtain improved guarantees when the prediction is correct (consistency) while simultaneously guaranteeing some worst-case bounds even if the prediction is arbitrarily wrong (robustness). The majority of the work on this framework has focused on online algorithms with predictions regarding future input. A subsequent line of work has focused on mechanism design, where the prediction is regarding the private information of strategic agents. In this paper, we initiate the study of online mechanism design with predictions, which combines the challenges of online algorithms with predictions and mechanism design with predictions. We consider the problem of designing a revenue-maximizing auction to sell a single item to strategic bidders who arrive and depart over time. We study the learning-augmented version of this problem, where the auction designer is given a prediction regarding the maximum value over all agents. Our main result is a strategyproof mechanism whose revenue guarantees are $alpha$-consistent with respect to the highest value and $(1-alpha^2)/4$-robust with respect to the second-highest value, for $alpha in [0,1]$. We show that this trade-off is optimal within a broad family of auctions.

See: https://theory.cs.rutgers.edu/theory_seminar