On the Computational Complexity of Decision Problems about MultiPlayer Nash Equilibria We study the computational complexity of decision problems about Nash equilibria in mplayer games. Several such problems have recently been shown to be computationally equivalent to the decision problem for the existential theory of the reals, or stated in terms of complexity classes, existsmathbbRcomplete, when mgeq 3. We show that, unless they turn into trivial problems, they are existsmathbbRhard even for 3player zerosum games.  :64,also obtain new results about several other decision problems. We show that when mgeq 3 the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are existsmathbbRcomplete. The latter result rectifies a previous claim of NPcompleteness in the literature. We show that deciding if a game has an irrational valued Nash equilibrium is existsmathbbRhard, answering a question of Bilo and Mavronicolas, and address :64,also the computational complexity of deciding if a game has a rational valued Nash equilibrium. These results :64,also hold for 3player zerosum games.  :164,proof methodology applies to corresponding decision problems about symmetric Nash equilibria in symmetric games as well, and in particular our new results carry over to the symmetric setting. Finally we show that deciding whether a symmetric mplayer games has a nonsymmetric Nash equilibrium is existsmathbbRcomplete when mgeq 3, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.

Strategic Payments in Financial Networks In their seminal work on systemic risk in financial markets, Eisenberg and Noe proposed and studied a model with n firms embedded into a network of debt relations. We analyze this model from a gametheoretic point of view. Every firm is a rational agent in a directed graph that has an incentive to allocate payments in order to clear as much of its debt as possible. Each edge is weighted and describes a liability between the firms. We consider several variants of the game that differ in the permissible payment strategies. We study the existence and computational complexity of pure Nash and strong equilibria, and we provide bounds on the (strong) prices of anarchy and stability for a natural notion of social welfare. Our results highlight the power of financial regulation  if payments of insolvent firms can be centrally assigned, a socially optimal strong equilibrium can be found in polynomial time. In contrast, worstcase strong equilibria can be a factor of Omega(n) away from optimal, and, in general, computing a best response is an NPhard problem. For less permissible sets of strategies, we show that pure equilibria might not exist, and deciding their existence as well as computing them if they exist constitute NPhard problems.