Single parameter FPT-algorithms for non-trivial games

DOI10.1007/978-3-642-19222-7_13MaRDI QIDQ3000500zbMATH OpenOpenAlexWikidataFDO

Authors Mahdi Parsa, Vladimir Estivill-Castro

Publication date 19 May 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10072/39590

zbMATH Keywords

algorithmic game theorycomputational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Noncooperative games (91A10) Games involving graphs (91A43)

Recommendations

• The complexity of uniform Nash equilibria and related regular subgraph problems
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• scientific article; zbMATH DE number 2243403

Cites work

• How hard is it to find extreme Nash equilibria in network congestion games?
• Nash and correlated equilibria: Some complexity considerations
• New complexity results about Nash equilibria
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• The complexity of uniform Nash equilibria and related regular subgraph problems
• The structure and complexity of Nash equilibria for a selfish routing game
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(2)

• Pure Nash equilibria in graphical games and treewidth
• Spy game: FPT-algorithm, hardness and graph products

This page was built for publication: Single parameter FPT-algorithms for non-trivial games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000500)