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

Alex Fabrikant, Christos H. PapadimitriouSODA 2008 · OpenReview

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 also show that the concept of sink equilibria proposed recently in [11] is 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).
BibTeX
@inproceedings{fabrikant2008complexity,
  author = {Alex Fabrikant and Christos H. Papadimitriou},
  title = {{The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond}},
  booktitle = {SODA},
  year = {2008},
  url = {https://openreview.net/forum?id=DlumZonwDZ},
}

Loading related content...

Figure