Nash Convergence of Mean-Based Learning Algorithms in First Price
  Auctions
  Understanding the convergence properties of learning dynamics in repeated
auctions is a timely and important question in the area of learning in
auctions, with numerous applications in, e.g., online advertising markets. This
work focuses on repeated first price auctions where bidders with fixed values
for the item learn to bid using mean-based algorithms -- a large class of
online learning algorithms that include popular no-regret algorithms such as
Multiplicative Weights Update and Follow the Perturbed Leader. We completely
characterize the learning dynamics of mean-based algorithms, in terms of
convergence to a Nash equilibrium of the auction, in two senses: (1)
time-average: the fraction of rounds where bidders play a Nash equilibrium
approaches 1 in the limit; (2)last-iterate: the mixed strategy profile of
bidders approaches a Nash equilibrium in the limit. Specifically, the results
depend on the number of bidders with the highest value: - If the number is at
least three, the bidding dynamics almost surely converges to a Nash equilibrium
of the auction, both in time-average and in last-iterate. - If the number is
two, the bidding dynamics almost surely converges to a Nash equilibrium in
time-average but not necessarily in last-iterate. - If the number is one, the
bidding dynamics may not converge to a Nash equilibrium in time-average nor in
last-iterate. Our discovery opens up new possibilities in the study of
convergence dynamics of learning algorithms.
