Single parameter FPT-algorithms for non-trivial games

V. Estivill-Castro, M. Parsa

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

4 Citations (Scopus)

Abstract

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
Subtitle of host publication21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010. Revised Selected Papers
EditorsCostas S. Iliopoulos, William F. Smyth
PublisherSpringer
Pages121-124
Number of pages4
ISBN (Print)9783642192210
DOIs
Publication statusPublished - 2011
Event21st International Workshop, IWOCA 2010 - London, United Kingdom
Duration: 26 Jul 201028 Jul 2010

Publication series

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

Conference

Conference21st International Workshop, IWOCA 2010
CountryUnited Kingdom
CityLondon
Period26/07/1028/07/10

    Fingerprint

Keywords

  • algorithmic game theory
  • computational complexity
  • combinational algorithms
  • discrete mathematics
  • data structures
  • coding
  • information theory

Cite this

Estivill-Castro, V., & Parsa, M. (2011). Single parameter FPT-algorithms for non-trivial games. In C. S. Iliopoulos, & W. F. Smyth (Eds.), Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010. Revised Selected Papers (pp. 121-124). (Lecture Notes in Computer Science; Vol. 6460). Springer. https://doi.org/10.1007/978-3-642-19222-7_13