Computing nash equilibria gets harder : new results show hardness even for parameterized complexity
EstivillCastro, Vladimir and Parsa, Mahdi; Downey, Rod and Manyem, Prabhu, eds. (2009) Computing nash equilibria gets harder : new results show hardness even for parameterized complexity. In: Proceedings of the 15th Computing Australasian Theory Symposium (CATS 2009). CRPIT, 94 . ACS, NZL, pp. 8187. ISBN 9781920682750

PDF (CRPITV94EstivillCastro)
CRPITV94EstivillCastro.pdf Preprint Download (206kB) Preview 
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 NPcomplete. While some NPcomplete 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 fixedparameter tractable algorithms. We show that kUniform Nash and kMinimal Nash support are W[2]hard. Given a game G=(A,B) and a nonnegative integer k, the kUniform Nash problem asks whether G has a uniform Nash equilibrium of size k. The kMinimal 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 kUniform 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 kMinimal Nash support is W[2]hard (a sample Nash equilibrium in a zerosum 2player 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.
Creators(s):  EstivillCastro, Vladimir and Parsa, Mahdi ORCID: https://orcid.org/000000016294307X; Downey, Rod and Manyem, Prabhu 

Item type:  Book Section 
ID code:  47988 
Keywords:  computing, Nash equilibria, hard, harder, hardness, NPcomplete, parameterized complexity theory, kMinimal Nash support, kUniform Nash, Electronic computers. Computer science, Computer Science(all) 
Subjects:  Science > Mathematics > Electronic computers. Computer science 
Department:  Strathclyde Business School > Management Science 
Depositing user:  Pure Administrator 
Date deposited:  12 May 2014 10:17 
Last modified:  07 Aug 2020 09:08 
URI:  https://strathprints.strath.ac.uk/id/eprint/47988 
Export data: 