The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
arXiv:2307.09478 · doi:10.1145/3618260.3649658
Abstract
We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item's value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction's \emph{transparency}, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder's valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.
Accepted at STOC 2024
References in corpus (6)
- Auctions Between Regret-Minimizing Agents
- Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions
- A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem
- Smoothed Analysis of Online and Differentially Private Learning
- Smoothed Online Learning is as Easy as Statistical Learning
- Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions