EFFICIENCY OF AN APPROXIMATE ALGORITHM TO SOLVE FINITE THREE-PERSON GAMES (A COMPUTATIONAL EXPERIENCE)
Share
Metrics
EFFICIENCY OF AN APPROXIMATE ALGORITHM TO SOLVE FINITE THREE-PERSON GAMES (A COMPUTATIONAL EXPERIENCE)
Annotation
PII
S042473880000516-6-1
Publication type
Article
Status
Published
Authors
Evgeny Golshtein
Ustav Malkov Nikolay Sokolov
Edition
Pages
94-107
Abstract
The authors provide a short description of an approximate algorithm proposed by Ye.G. Golshtein to solve finite non-cooperative three-person games in mixed strategies. The search for a solution to such a game is reduced to the minimization of the so-called Nash function having a large number of local minima. By enumerating the original pure strategies the method finds an exact solution of the game whenever a complementarity condition holds. Otherwise, if the complementarity condition is slightly violated, a reasonable approximation to the set of Nash equilibrium points is generated. A series of numerical tests have been conducted to reveal both the algorithm’s advantages and its minor points. With the growth of interdependence coefficient of tables that determine winnings of the players, the efficiency of the algoriths decreases.
Keywords
non-cooperative games, Nash equilibrium, finite games, pure and mixed strategies, an approximate algorithm, numerical tests, linear programming
Date of publication
01.01.2017
Number of purchasers
0
Views
62