Timezone: »

 
Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions
Xiaotie Deng · Xinyan Hu · Tao Lin · Weiqiang Zheng

@
in Learning in Presence of Strategic Behavior »
Event URL: https://openreview.net/forum?id=MwYDSM6hbZm »

We consider repeated first price auctions where each bidder, having a deterministic type, learns to bid using a mean-based learning algorithm. We completely characterize the Nash convergence property of the bidding dynamics in two senses: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium approaches to 1 in the limit; (2) last-iterate: the mixed strategy profile of bidders approaches to 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.

Author Information

Xiaotie Deng (Peking University)
Xinyan Hu (Peking University)
Tao Lin (Harvard University, Harvard University)
Weiqiang Zheng (Yale University)

More from the Same Authors