Local search in bilinear two-person game

We consider an approach that allows reducing Nash equilibrium problem to a minimax problem for rather wide class of games using the so-called Nikaido-Isoda function. One can reformulate minimax problem as an optimization problem with nonconvex and implicitly defined objective function in general case. In other words, the set of Nash equilibria of the game is coincide with the set of global solutions of derived optimization problem. In present paper we investigate such an approach as applied to bilinear two-person game with quadratic loss functions and independent strategy spaces in view of an assumption that loss functions are strictly convex with respect to own players’ variables. In this case we suggest to replace “inner” optimization problem in minimax problem by Lagrange dual one. Such a way leads to presentation of the objective function as a difference of two convex functions (d.c-decomposition of the objective function). The very function in d.c-decomposition, that forms concave part, is defined implicitly as well as the objective function. We propose a method for linearization of concave term. That allows using the well-known local search method for d.c-functions, where the next iteration point is a solution of convex optimization problem with the objective function, which gained from initial objective by linearization of concave term in d.c-decomposition. Since the concerned problem is nonconvex, we offer to use local search in combination with multistart. The results of computational experiment are provided in the paper.