Two Algorithms for Computing Exact and Approximate Nash Equilibria in Bimatrix Games

Abstract

In this paper, we first devise two algorithms to determine whether or not a bimatrix game has a strategically equivalent zero-sum game. If so, we propose an algorithm that computes the strategically equivalent zero-sum game. If a given bimatrix game is not strategically equivalent to a zero-sum game, we then propose an approach to compute a zero-sum game whose saddle-point equilibrium can be mapped to a well-supported approximate Nash equilibrium of the original game. We conduct extensive numerical simulation to establish the efficacy of the two algorithms.

arXiv comment20 pages, 3 figures. Replaces "On the Computation of Strategically Equivalent Rank-0 Games" by condensing the main results of that paper and extending the results with an algorithm for well-supported approximate Nash equilibrium. Submitted to 2021 Conference on Decision and Game Theory for Security (GameSec 2021)