Single parameter FPT-algorithms for non-trivial games

Vladimir Estivill-Castro, Mahdi Parsa

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


We know that k -Uniform Nash is W[2]-Complete when we consider imitation symmetric win-lose games (with k as the parameter) even when we have two players. However, this paper provides positive results regarding Nash equilibria. We show that consideration of sparse games or limitations of the support result in fixed-parameter algorithms with respect to one parameter only for the k -Uniform Nash problem. That is, we show that a sample uniform Nash equilibrium in r-sparse imitation symmetric win-lose games is not as hard because it can be found in FPT time (i.e polynomial in the size of the game, but maybe exponential in r). Moreover, we show that, although NP-Complete, the problem of Best Nash Equilibrium is also fix-parameter tractable.
Original languageEnglish
Title of host publicationCombinatorial Algorithms
EditorsCostas S. Iliopoulos, William F. Smyth
PublisherSpringer Berlin
Number of pages4
ISBN (Electronic)978-3-642-19222-7
ISBN (Print)978-3-642-19221-0
Publication statusPublished - 2011
Externally publishedYes
EventInternational Workshop on Combinatorial Algorithms - London, United Kingdom
Duration: 26 Jul 201028 Jul 2010
Conference number: 21st

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceInternational Workshop on Combinatorial Algorithms
Abbreviated titleIWOCA 2010
Country/TerritoryUnited Kingdom


Dive into the research topics of 'Single parameter FPT-algorithms for non-trivial games'. Together they form a unique fingerprint.

Cite this