On the impossibility of achieving no regrets in repeated games

Regret-minimizing strategies for repeated games have been receiving increasing attention in the literature. These are simple adaptive behavior rules that lead to no regrets and, if followed by all players, exhibit nice convergence properties: the average play converges to correlated equilibrium, or even to Nash equilibrium in certain classes of games. However, the no-regret property relies on a strong assumption that each player treats her opponents as unresponsive and fully ignores the opponents' possible reactions to her actions. We show that if at least one player is slightly responsive, it is impossible to achieve no regrets, and convergence results for regret minimization with responsive opponents are unknown.