Search of Nash Equilibrium in Quadratic n-person Game

摘要

This paper is devoted to Nash equilibrium search in quadratic n-person game, where payoff function of each player is quadratic with respect to its strategic variable. Interactions between players are defined by corresponding bilinear terms in the payoffs. First, the statement is considered without any assumptions on payoffs' concavity. We use Nikaido-Isoda approach in order to reduce Nash equilibrium problem to optimization problem with nonconvex implicitly defined objective function. We propose global search algorithm based on the linearization of implicit part of the objective by linear support minorants. This technique allows to determine numerically whether the game has no equilibria. Then payoffs are assumed to be concave with respect to its strategic variables, and we suggest d.c. decomposition of the objective, thus corresponding local search method is applicable. Computational results are provided in the paper. Local search method is compared with extragradient equilibrium search algorithm.