A Reinforcement Learning Algorithm For Obtaining The Nash Equilibrium Of Multi-player Matrix Games

摘要

With the advent of e-commerce, the contemporary marketplace has evolved significantly toward competition-based trading of goods and services. Competition in many such market scenarios can be modeled as matrix games. This paper presents a computational algorithm to obtain the Nash equilibrium of n-player matrix games. The algorithm uses a stochastic-approximation-based Reinforcement Learning (RL) approach and has the potential to solve n-player matrix games with large player-action spaces. The proposed RL algorithm uses a value-iteration-based approach, which is well established in the Markov decision processes/semi-Markov decision processes literature. To emphasize the broader impact of our solution approach for matrix games, we discuss the established connection of matrix games with discounted and average reward stochastic games, which model a much larger class of problems. The solutions from the RL algorithm are extensively benchmarked with those obtained from an openly available software (GAMBIT). This comparative analysis is performed on a set of 16 matrix games with up to four players and 64 action choices. We also implement our algorithm on practical examples of matrix games that arise due to strategic bidding in restructured electric power markets.