Single parameter FPT-algorithms for non-trivial games
Estivill-Castro, V. and Parsa, M.; Iliopoulos, Costas S. and Smyth, William F., eds. (2011) Single parameter FPT-algorithms for non-trivial games. In: Combinatorial Algorithms. Lecture Notes in Computer Science . Springer, GBR, pp. 121-124. ISBN 9783642192210 (https://doi.org/10.1007/978-3-642-19222-7_13)
Full text not available in this repository.Request a copyAbstract
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.
ORCID iDs
Estivill-Castro, V. and Parsa, M. ORCID: https://orcid.org/0000-0001-6294-307X; Iliopoulos, Costas S. and Smyth, William F.-
-
Item type: Book Section ID code: 47983 Dates: DateEvent2011PublishedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Strathclyde Business School > Management Science Depositing user: Pure Administrator Date deposited: 12 May 2014 09:25 Last modified: 11 Nov 2024 14:55 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/47983