Search of nash equilibrium in quadratic n-person game

Статья конференции

Minarchenko I.

Журнал: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

9th International Conference on Discrete Optimization and Operations Research, DOOR 2016

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.9869 LNCS. P.509-521.

DOI: 10.1007/978-3-319-44914-2_40

ISBN: 9 783 319

2016

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. © Springer International Publishing Switzerland 2016.

Библиографическая ссылка

Minarchenko I. Search of nash equilibrium in quadratic n-person game // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.9869 LNCS. 2016. P.509-521. ISBN (print): 9 783 319 . DOI: 10.1007/978-3-319-44914-2_40

computation theory