The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond

Abstract

We settle the complexity of a well-known problem in networking by establishing that it is PSPACE-complete to tell whether a system of path preferences in the BGP protocol [25] can lead to oscillatory behavior; one key insight is that the BGP oscillation question is in fact one about Nash dynamics. We show that the concept of sink equilibria proposed recently in [11] is also PSPACE-complete to analyze and approximate for graphical games. Finally, we propose a new equilibrium concept inspired by game dynamics, unit recall equilibria, which we show to be close to universal (exists with high probability in a random game) and algorithmically promising. We also give a relaxation thereof, called componentwise unit recall equilibria, which we show to be both tractable and universal (guaranteed to exist in every game).