Exclusion Method for Finding Nash Equilibrium in Multi-Player Games (Extended 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 treesearch-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.