Parameterized Two-Player Nash Equilibrium

We study the problem of computing Nash equilibria in a two-player normal form (bimatrix) game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in...

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 65, No. 4 (2013), p. 802-816
Main Author: Hermelin, Danny
Other Involved Persons: Huang, Chien-Chung ; Kratsch, Stefan ; Wahlström, Magnus
Format: electronic Article
Language:English
ISSN:1432-0541
Item Description:The third author acknowledges support by the Netherlands Organisation for Scientific Research (NWO), project "KERNELS: Combinatorial Analysis of Data Reduction”.
Physical Description:Online-Ressource
DOI:10.1007/s00453-011-9609-z
Subjects:
QR Code: Show QR Code