Local search in quadratic two-person game

I. M. Minarchenko

The Bulletin of Irkutsk State University. Series Mathematics, Tome 18 (2016), pp. 60-73

Résumé

We consider a noncooperative two-person game in strategic form with quadratic players' loss functions. Loss function of every player is assumed to be strictly convex quadratic function with respect to own variable and linear with respect to another player's variable defining by corresponding bilinear term. Nash equilibrium problem for such a game is reduced to an equivalent minmax problem by Nikaido–Isoda approach. As the "inner" maximization problem does not admit analytical solution, the minmax problem is represented by the minimization problem of nonconvex implicitly defined function over the set of strategy profiles of the game. The "inner" maximization problem, which is turn out to be convex, is replaced by Lagrange dual problem. For the problem under consideration, it leads to d.c.-decomposition of the objective function. In other words, the objective is represented as a difference of two convex functions with implicit function that defines concave part of the decomposition. In this paper we propose a natural way to linearize concave term, and then iterative local search method for d.c.-functions is suggested to use. The main idea of this method is that the next point is chosen as a solution of auxiliary convex optimization problem where objective function is taken as initial objective with linearized concave term. Since the problem is nonconvex, we propose to use multistart of local search from randomly generated initial points. It is known, that minimum of the objective function is zero, and the set of the points bringing minimal value to the objective is coincide with the set of Nash equilibria of the game. Therefore one can easily verify whether stationary point obtained by local search is Nash equilibrium. In the paper we provide results of numerical testing of local search for d.c.-functions on the randomly generated problems and a comparison with some existing algorithms for computing Nash equilibria.

Détail

Keywords: Nash equilibrium, Nikaido–Isoda function, algorithms for computing Nash equilibria.
Mots-clés : d.c.-decomposition