Topics in algorithms for new classes of non-cooperative games

2018-07-19Introduced by John Nash, modern-day game theory in non-cooperative games has developed into a very fruitful research discipline. Depending on the properties of players' objective functions and constraints, there are various classes of non-cooperative games. In this thesis, we have studied a variety of non-cooperative games, including Nash games with non-differentiable non-separable objective functions, value-function based games, DC potential games, and generalized Nash equilibrium problem with coupling constraints. In order to compute the solutions to these different classes of games, we designed algorithms and proved the convergence of these algorithms. We established the convergence of best-response algorithm under non-separable, C¹ objective functions, extending the results from Jong-Shi Pang and Meisam Razaviyayn. We developed the relaxed convergent conditions, including the corresponding convergent conditions for games with differentiable objective functions and non-differentiable objective functions. Some specific classes of games satisfy such conditions, including bi-Lipschitz games, poly-matrix games, minmax games and two-stage stochastic games. We have also studied the value-function based games. Generalizing certain network interdiction games communicated to us by Andrew Liu and his collaborators, we have studied a bilevel, non-cooperative game wherein the objective function of each player’s optimization problem contains a value function of a second-level linear program parameterized by the first-level variables in a non-convex manner. In the applied network interdiction games, this parameterization is through a piecewise linear function that upper bounds the second-level decision variable. In order to give a unified treatment to the overall two-level game where the second-level problems may be minimization or maximization, we formulated it as a one-level game of a particular kind. Namely, each player’s objective function is the sum of a first-level objective function ± a value function of a second-level maximization problem whose objective function involves a difference-of-convex (dc), specifically piecewise affine, parameterization by the first-level variables. We investigated the existence of a first-order stationary solution of such a game, which we call a quasi-Nash equilibrium, and study the computation of such a solution in the linear-quadratic case by Lemke’s method using a linear complementarity formulation. We have also introduced the DC potential games, where the objective function of each player is a DC function, i.e., the difference of two convex functions. A linearized best-response algorithm to compute a solution to the DC potential games with differentiable objective functions has been discussed, and the convergence of such algorithm has been proved. In the end, we have used the augmented Lagrangian based algorithm to compute a solution to the generalized Nash equilibrium problem, and proved its convergence. A generalized Nash equilibrium problem is an extension of the standard Nash equilibrium problem, where both the objective function and the feasible set of each player depend on the other players’ decision variables