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 G has equilibrium such that the support of each
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). 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. |
| Cite as: Estivill-Castro, V. and Parsa, M. (2009). Computing Nash Equilibria Gets Harder: New Results Show Hardness Even for Parameterized Complexity. In Proc. Fifteenth Computing: The Australasian Theory Symposium (CATS 2009), Wellington, New Zealand. CRPIT, 94. Downey, R. and Manyem, P., Eds. ACS. 81-87. |
 (from crpit.com)
(local if available)
|