On the Computational Complexity of Quasi-Variational Inequalities and Multi-Leader-Follower Games

We introduce a computational version of the generalized quasivariational inequality problem and study its computational complexity, in particular proving that it is PPAD-complete. We also consider applications to multi-leader-follower games, a domain traditionally marked by the absence of general solutions. However, through the use of relaxation techniques, we obtain versions of these problems which may be formulated in terms of quasivariational inequalities, allowing us to obtain PPAD-completeness for such games.