Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions
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 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, -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.
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 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, -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.
Research Areas
