Exclusion method for finding Nash equilibrium in multi-player games

Kimmo Berg, Tuomas Sandholm

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)

Abstract

We present a complete algorithm for finding an ∈-Nash equilibrium, for arbitrarily small ∈, in games with more than two players. The best prior complete algorithm has significantly worse complexity and has, to our knowledge, never been implemented. 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 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 well-known incomplete methods, our method does not need to proceed locally, which avoids it getting stuck in a local minimum that may be far from any actual equilibrium. The run time grows rapidly with the game size, and this 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.

Original languageEnglish
Title of host publicationAAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1417-1418
Number of pages2
ISBN (Electronic)9781450342391
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Autonomous Agents and Multiagent Systems - Singapore, Singapore
Duration: 9 May 201613 May 2016
Conference number: 15

Conference

ConferenceInternational Conference on Autonomous Agents and Multiagent Systems
Abbreviated titleAAMAS
CountrySingapore
CitySingapore
Period09/05/201613/05/2016

Keywords

  • Multi-player games
  • Nash equilibrium
  • Noncooperative games

Cite this