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

computational complexityalgorithmic game theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) 2-person games (91A05) 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)

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

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)