Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Online Mechanism Design with Predictions
arXiv.org
26 Mar 2024
Abstract
Aiming to overcome some of the limitations of worst-case analysis, the
recently proposed framework of "algorithms with predictions" allows algorithms
to be augmented with a (possibly erroneous) machine-learned prediction that
they can use as a guide. In this framework, the goal is to obtain improved
guarantees when the prediction is correct, which is called \emph{consistency},
while simultaneously guaranteeing some worst-case bounds even when the
prediction is arbitrarily wrong, which is called \emph{robustness}. The vast
majority of the work on this framework has focused on a refined analysis of
online algorithms augmented with predictions regarding the future input. A
subsequent line of work has also successfully adapted this framework to
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 well-studied problem of designing a revenue-maximizing
auction to sell a single item to strategic bidders who arrive and depart over
time, each with an unknown, private, value for the item. 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 tradeoff is
optimal within a broad and natural family of auctions, meaning that any
$\alpha$-consistent mechanism in that family has robustness at most
$(1-\alpha^2)/4$. Finally, we extend our mechanism to also achieve expected
revenues proportional to the prediction quality.
Metrics
14 Record Views
Details
- Title
- Online Mechanism Design with Predictions
- Creators
- Eric BalkanskiVasilis GkatzelisXizhi TanCherlin Zhu
- Publication Details
- arXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science
- Other Identifier
- 991021868090904721