Computing Nash equilibria gets harder - new results show hardness even for Parameterized Complexity

There are no files associated with this record.

Title Computing Nash equilibria gets harder - new results show hardness even for Parameterized Complexity
Author Estivill-Castro, Vladimir; Parsa, Mahdi
Publication Title Proceedings of the 15th Computing: The Australasian Theory Symposium (CATS 2009)
Editor Rod Downey and Prabhu Manyem
Year Published 2009
Place of publication Sydney, Australia
Publisher Australian Computer Society
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.
Peer Reviewed Yes
Published Yes
ISBN 1445-1336
Conference name CATS 2009 (Computing: The Australasian Theory Symposium)
Location Wellington, New Zealand
Date From 2009-01-20
Date To 2009-01-23
URI http://hdl.handle.net/10072/31975
Date Accessioned 2010-03-04
Date Available 2010-07-09T07:53:19Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Analysis of Algorithms and Complexity
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice