title: Nonconvex Nash Games : Solution Concepts and Algorithms
Creators: name: Nowak, Daniel
Publisher: name: UNSPECIFIED
Year: 2021

description: Game theory is a mathematical approach to model competition between several parties, called players. The goal of each player is to choose a strategy, which solves his optimization problem, i.e. minimizes or maximizes his objective function. Due to the competitive setting, this strategy may influence the optimization problems of other players. In the non-cooperative setting each player acts selfish, meaning he does not care about the objective of his opponents. A solution concept for this problem is a Nash equilibrium, which was introduced by John Forbes Nash in his Ph.D. thesis in 1950. Convexity of the optimization problems is a crucial assumption for the existence of Nash equilibria. This work investigates settings, where this convexity assumption fails to hold. The first part of this thesis extends results of Jong-Shi Pang and Gesualdo Scutari from their paper "Nonconvex Games with Side Constraints'' published in 2011. In this publication, a game with possibly nonconvex objective functions and nonconvex individual and shared inequality constraints was investigated. We extend these results twofold. Firstly, we generalize the individual and shared polyhedral constraints to general convex constraints and, secondly, we introduce convex and nonconvex, individual and shared equality constraints. After a detailed comparison of solution concepts for the generalized Nash game and a related Nash game, we show that so-called quasi-Nash equilibria exist under similar assumptions than in the original work, provided some additional constraint qualification holds. Subsequently, we prove that the existence of Nash equilibria needs additional assumptions on the gradients of the equality constraints. Furthermore, a special case of a multi-leader multi-follower game is investigated. We show the convergence of epsilon-quasi-Nash equilibria to C-stationary points and prove that these are also Clarke-stationary under reasonable assumptions. In the second part of this thesis, an application in computation offloading is investigated. We consider several mobile users that are able to offload parts of a computation task to a connected server. However, the server has limited computation capacities which leads to competition among the mobile users. If a user decides to offload a part of his computation, he needs to wait for the server to finish before he can assemble the results of his computation. This leads to a vanishing constraint in the optimization problem of the mobile users which is a nonconvex and nonsmooth condition. We show the existence of a unique Nash equilibrium for the computation offloading game and provide an efficient algorithm for its computation. Furthermore, we present two extensions to this game, which inherit similar properties and we also show the limitations of these formulations. The third part investigates a hierarchical constrained Cournot game. In the upper level, several firms decide on capacities which act as constraints for the production variables. In the lower level the same firms engage in a Cournot competition, where they choose production variables to maximize profit. The prior chosen capacities are upper bounds on these production variables. This hierarchical setting induces nonconvexity and nonsmoothness in the upper level objective functions. After a detailed sensitivity analysis of the lower level, we give necessary optimality conditions for the upper level, i.e. for the hierarchical Cournot game. Using these conditions, we construct an algorithm which provably finds all Nash equilibria of the game, provided some assumptions are satisfied. This algorithm is numerically tested on several examples which are motivated by the gas market.