The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond
Lists
Only you see this
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...