Open AccessAn Algorithmic Procedure for Finding Nash Equilibrium
Author(s) -
HK Das,
Tapan Kumar Saha
Publication year - 2020
Publication title -
ganit
Language(s) - English
Resource type - Journals
eISSN - 2224-5111
pISSN - 1606-3694
DOI - 10.3329/ganit.v40i1.48196
Subject(s) - nash equilibrium , epsilon equilibrium , best response , correlated equilibrium , risk dominance , mathematical economics , trembling hand perfect equilibrium , normal form game , equilibrium selection , repeated game , sequential equilibrium , computer science , mathematical optimization , folk theorem , symmetric equilibrium , game theory , mathematics
This paper proposes a heuristic algorithm for the computation of Nash equilibrium of a bi-matrix game, which extends the idea of a single payoff matrix of two-person zero-sum game problems. As for auxiliary but making the comparison, we also introduce here the well-known definition of Nash equilibrium and a mathematical construction via a set-valued map for finding the Nash equilibrium and illustrates them. An important feature of our algorithm is that it finds a perfect equilibrium when at the start of all actions are played. Furthermore, we can find all Nash equilibria of repeated use of this algorithm. It is found from our illustrative examples and extensive experiment on the current phenomenon that some games have a single Nash equilibrium, some possess no Nash equilibrium, and others had many Nash equilibria. These suggest that our proposed algorithm is capable of solving all types of problems. Finally, we explore the economic behaviour of game theory and its social implications to draw a conclusion stating the privilege of our algorithm.
GANIT J. Bangladesh Math. Soc.Vol. 40 (2020) 71-85