TITLE:
A Regret-Based Algorithm for Computing All Pure Nash Equilibria for Noncooperative Games in Normal Form
AUTHORS:
H. W. Corley
KEYWORDS:
Pure Nash Equilibria, Algorithm for Pure Nash Equilibria, Regret Matrix, Pareto Nash Equilibrium
JOURNAL NAME:
Theoretical Economics Letters,
Vol.10 No.6,
December
11,
2020
ABSTRACT: The concept of a pure Nash equilibrium (NE) for a
noncooperative game is simpler than that of a mixed NE, which always exists.
However, pure NEs probably have more practical significance even though such a
game may not have a pure NE. An efficient algorithm is presented here to
determine whether an n-person game in
normal form has a pure NE and, if so, to obtain all NEs. This algorithm uses
the notion of regret, and the payoff matrix (PM) is transformed into a regret
matrix (RM)—a loss matrix with an intuitive interpretation. The RM has the
property that an action profile of the PM is a pure NE if and only if (0,· · ·,0) is the corresponding element of the RM. The computational
complexity of the algorithm is O(N) in the number of individual utilities N in the PM, and so it is substantially
faster than a total enumeration.