Finding Nash equilibrium in a bimatrix game is the problem of finding a strategy profile for the players of the game, where none of them can improve their payoffs by individually deviating from the existing strategy profile. The problem is computationally demanding and belongs to the class of PPAD complete problems. Through the years different algorithmic approaches were proposed for solving the problem. We present the mathematical background of three visible algorithms from the literature and implement them in Julia programming language. We evaluate their performance on bimatrix games of different sizes and two different types. We put forth the question of numerical stability in the case of Lemke-Howson algorithm, which we feel is not sufficiently described in the literature.
|
