Skip to yearly menu bar Skip to main content


Poster

Swap Regret, Symmetry, and Nash Convergence in Games

Renato Leme · Georgios Piliouras · Jon Schneider

[ ]
Fri 13 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract:

In this paper, we investigate the question of whether no-swap-regret dynamics have stronger convergence properties in repeated games than regular no-external-regret dynamics. We prove that in almost all symmetric zero-sum games with symmetric initialization, continuous no-swap-regret dynamics are guaranteed to converge to the Nash equilibrium (whereas no-external-regret dynamics are known to exhibit cyclic or even chaotic behavior under the same circumstances). On the other hand, we show that under asymmetric initial conditions, no-swap-regret dynamics may also cycle.We show that these convergence properties come at a cost. While no-external-regret dynamics can be completely determined by the cumulative reward vector received by each player, we show there does not exist any general no-swap-regret dynamics defined on the same state space. In fact, we prove that any no-swap-regret learning algorithm must play a time-asymmetric function over the set of previously observed rewards, ruling out any dynamics based on a symmetric function of the current set of rewards.

Live content is unavailable. Log in and register to view live content