Single parameter FPT-algorithms for non-trivial games

DOI10.1007/978-3-642-19222-7_13zbMATH Open1326.68156OpenAlexW2398380006WikidataQ58803152 ScholiaQ58803152MaRDI QIDQ3000500FDOQ3000500

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

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

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)

Cites Work

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

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)