Computing nash equilibria gets harder: new results show hardness even for parameterized complexity

Vladimir Estivill-Castro, Mahdi Parsa

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

21 Downloads (Pure)

Abstract

In this paper we show that some decision problems regarding the computation of Nash equilibria are to be considered particularly hard. Most decision problems regarding Nash equilibria have been shown to be NP-complete. While some NP-complete problems can find an alternative to tractability with the tools of Parameterized Complexity Theory, it is also the case that some classes of problems do not seem to have fixed-parameter tractable algorithms. We show that k-Uniform Nash and k-Minimal Nash support are W[2]-hard. Given a game G=(A,B) and a nonnegative integer k, the k-Uniform Nash problem asks whether G has a uniform Nash equilibrium of size k. The k-Minimal Nash support asks whether has Nash equilibrium such that the support of eacGh player’s Nash strategy has size equal to or less than k. First, we show that k-Uniform Nash (with k as the parameter) is W[2]-hard even when we have 2 players, or fewer than 4 different integer values in the matrices. Second, we illustrate that even in zerosum games k-Minimal Nash support is W[2]-hard (a sample Nash equilibrium in a zero-sum 2-player game can be found in polynomial time (von Stengel 2002)). Thus, it must be the case that other more general decision problems are also W[2]-hard. Therefore, the possible parameters for fixed parameter tractability in those decision problems regarding Nash equilibria seem elusive.
Original languageEnglish
Title of host publicationProceedings of the 15th Computing Australasian Theory Symposium (CATS 2009)
EditorsRod Downey, Prabhu Manyem
Place of PublicationWellington, New Zealand
Pages81-87
Number of pages7
Volume94
Publication statusPublished - 1 Jan 2009
Event15th Computing Australasian Theory Symposium (CATS 2009) - Wellington, New Zealand
Duration: 20 Jan 200923 Jan 2009

Publication series

NameCRPIT
PublisherACS

Conference

Conference15th Computing Australasian Theory Symposium (CATS 2009)
CountryNew Zealand
CityWellington
Period20/01/0923/01/09

    Fingerprint

Keywords

  • computing
  • Nash equilibria
  • hard
  • harder
  • hardness
  • NP-complete
  • parameterized complexity theory
  • k-Minimal Nash support
  • k-Uniform Nash

Cite this

Estivill-Castro, V., & Parsa, M. (2009). Computing nash equilibria gets harder: new results show hardness even for parameterized complexity. In R. Downey, & P. Manyem (Eds.), Proceedings of the 15th Computing Australasian Theory Symposium (CATS 2009) (Vol. 94, pp. 81-87). (CRPIT). Wellington, New Zealand.