Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions
<|reference_start|>Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions: Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning, which has seen a recent surge in interest due to the transition of display advertising to first-price auctions. In this work, we propose a novel concave formulation for pure-strategy bidding in first-price auctions, and use it to analyze natural Gradient-Ascent-based algorithms for this problem. Importantly, our analysis goes beyond regret, which was the typical focus of past work, and also accounts for the strategic backdrop of online-advertising markets where bidding algorithms are deployed -- we provide the first guarantees of strategic-robustness and incentive-compatibility for Gradient Ascent.   Concretely, we show that our algorithms achieve $O(\sqrt{T})$ regret when the highest competing bids are generated adversarially, and show that no online algorithm can do better. We further prove that the regret reduces to $O(\log T)$ when the competition is stationary and stochastic, which drastically improves upon the previous best of $O(\sqrt{T})$. Moving beyond regret, we show that a strategic seller cannot exploit our algorithms to extract more revenue on average than is possible under the optimal mechanism. Finally, we prove that our algorithm is also incentive compatible -- it is a (nearly) dominant strategy for the buyer to report her values truthfully to the algorithm as a whole. Altogether, these guarantees make our algorithms the first to simultaneously achieve both optimal regret and strategic-robustness.<|reference_end|>
@article{kumar2024strategically-robust,
    title={Strategically-Robust Learning Algorithms for Bidding in First-Price
  Auctions},
    author={Rachitesh Kumar, Jon Schneider, Balasubramanian Sivan},
    journal={arXiv preprint arXiv:2402.07363},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07363},
    primaryClass={cs.GT cs.LG}
}