Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions

Authors

  • Zhe Feng Harvard University
  • Guru Guruganesh Google Research
  • Christopher Liaw University of British Columbia
  • Aranyak Mehta Google Research
  • Abhishek Sethi Google Research

Keywords:

Auctions and Market-Based Systems

Abstract

The connection between games and no-regret algorithms has been widely studied in the literature. A fundamental result is that when all players play no-regret strategies, this produces a sequence of actions whose time-average is a coarse-correlated equilibrium of the game. However, much less is known about equilibrium selection in the case that multiple equilibria exist. In this work, we study the convergence of no-regret bidding algorithms in auctions. Besides being of theoretical interest, bidding dynamics in auctions is an important question from a practical viewpoint as well. We study the repeated game between bidders in which a single item is sold at each time step and the bidder's value is drawn from an unknown distribution. We show that if the bidders use any mean-based learning rule then the bidders converge with high probability to the truthful pure Nash Equilibrium in a second price auction, in VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a first price auction. We note mean-based algorithms cover a wide variety of known no-regret algorithms such as Exp3, UCB, \epsilon-Greedy etc. Also, we analyze the convergence of the individual iterates produced by such learning algorithms, as opposed to the time-average of the sequence. Our experiments corroborate our theoretical findings and also find a similar convergence when we use other strategies such as Deep Q-Learning.

Downloads

Published

2021-05-18

How to Cite

Feng, Z., Guruganesh, G., Liaw, C., Mehta, A., & Sethi, A. (2021). Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5399-5406. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16680

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms