Exclusion Method for Finding Nash Equilibrium in Multiplayer Games

Authors

  • Kimmo Berg Aalto University School of Science
  • Tuomas Sandholm Carnegie Mellon University

DOI:

https://doi.org/10.1609/aaai.v31i1.10581

Keywords:

Nash equilibrium, equilibrium finding, multi-player games, exclusion oracle, noncooperative games, computation, game theory

Abstract

We present a complete algorithm for finding an epsilon-Nash equilibrium, for arbitrarily small epsilon, in games with more than two players. The method improves the best-known upper bound with respect to the number of players n, and it is the first implemented algorithm, to our knowledge, that manages to solve all instances. The main components of our tree-search-based method are a node-selection strategy, an exclusion oracle, and a subdivision scheme. The node-selection strategy determines the next region (of the strategy profile probability vector space) to be explored — based on the region's size and an estimate of whether the region contains an equilibrium. The exclusion oracle provides a provably correct sufficient condition for there not to exist an equilibrium in the region. The subdivision scheme determines how the region is split if it cannot be excluded. Unlike the well-known incomplete methods, our method does not need to proceed locally, which avoids it getting stuck in a local minimum---in the space of players' regrets — that may be far from any actual equilibrium. The run time grows rapidly with the game size; this reflects the dimensionality of this difficult problem. That suggests a hybrid scheme where one of the relatively fast prior incomplete algorithms is run, and if it fails to find an equilibrium, then our method is used.

Downloads

Published

2017-02-10

How to Cite

Berg, K., & Sandholm, T. (2017). Exclusion Method for Finding Nash Equilibrium in Multiplayer Games. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10581

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms