A reinforcement learning algorithm for obtaining the Nash equilibrium of multi-player matrix games

Vishnu Nanduri and Tapas Das

IISE Transactions, 2009, vol. 41, issue 2, 158-167

Abstract: 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.

Date: 2009
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/07408170802369417 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:41:y:2009:i:2:p:158-167

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/07408170802369417

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().