Memoryless Algorithmic Collusion: Sure to Fail, Slow to Fall

Abstract

This paper shows that, in a class of Bertrand-style competition games, memoryless Q-learning algorithms should adapt to Nash Equilibrium given sufficient explorations in the long-run. This is also verified through accelerating simulations, while the convergence time grows super-exponentially for high discount factors. The resilience of collusive outcomes in the short-run is due to exploration of unprofitable actions, making the system resemble random walk. A structural model is proposed to estimate the convergence time, which not only explains the role of discount factor, but also unveils the non-monotonic relation in learning rate, which is overlooked in the literature.