Randomized Truthful Auctions with Learning Agents

• Published in: arXiv.org 2024-11
• Main Authors: Aggarwal, Gagan, Gupta, Anupam, Perlroth, Andres, Velegkas, Grigoris
• Format: Article
• Language: English
• Subjects: Algorithms; Auctioning; Auctions; Bids; Machine learning; Maximization; Optimization; Reserves
• ISSN: 2331-8422

We study a setting where agents use no-regret learning algorithms to participate in repeated auctions. \citet{kolumbus2022auctions} showed, rather surprisingly, that when bidders participate in second-price auctions using no-regret bidding algorithms, no matter how large the number of interactions \(T\) is, the runner-up bidder may not converge to bidding truthfully. Our first result shows that this holds for \emph{general deterministic} truthful auctions. We also show that the ratio of the learning rates of the bidders can \emph{qualitatively} affect the convergence of the bidders. Next, we consider the problem of revenue maximization in this environment. In the setting with fully rational bidders, \citet{myerson1981optimal} showed that revenue can be maximized by using a second-price auction with reserves.We show that, in stark contrast, in our setting with learning bidders, \emph{randomized} auctions can have strictly better revenue guarantees than second-price auctions with reserves, when \(T\) is large enough. Finally, we study revenue maximization in the non-asymptotic regime. We define a notion of {\em auctioneer regret} comparing the revenue generated to the revenue of a second price auction with truthful bids. When the auctioneer has to use the same auction throughout the interaction, we show an (almost) tight regret bound of \(\smash{\widetilde \Theta(T^{3/4})}.\) If the auctioneer can change auctions during the interaction, but in a way that is oblivious to the bids, we show an (almost) tight bound of \(\smash{\widetilde \Theta(\sqrt{T})}.\)