算法合谋与有限理性学习中的民间定理

We prove a Folk theorem when players with bounded rationality learn as they play a repeated potential game. We use a dynamic generalization of smooth fictitious play with bounded $m$-memory strategies to model learning with bounded rationality that is consistent with learning by algorithms. In a repeated potential game with perfect monitoring, we use this learning model to show that for any feasible and individually rational payoff profile, if players have sufficient memory, are sufficiently patient, and best respond with sufficiently few mistakes, then the players have a non-zero probability of learning an $m$-memory strategy profile that achieves an average payoff close to the specified payoff profile for an appropriate continuation game. Moreover, the strategy profile learned is an $m$-memory $\epsilon$-subgame perfect equilibrium of the repeated game. This finding demonstrates that competition authorities are correct in their concern about algorithmic collusion.