The complexity of uniform Nash equilibria and related regular subgraph problems

DOI10.1016/j.tcs.2008.03.036zbMath1153.91006OpenAlexW2149624304MaRDI QIDQ935157

Ugo Di Iorio, Luigi Laura, Vincenzo Bonifaci

Publication date: 31 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.03.036

zbMATH Keywords

computational complexityNP-completenessregular induced subgraphuniform Nash equilibrium

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Combinatorial games (91A46)

Related Items (4)

The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ The price of defense ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Single Parameter FPT-Algorithms for Non-trivial Games

Cites Work

• Unnamed Item
• New complexity results about Nash equilibria
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• Nash and correlated equilibria: Some complexity considerations
• On the complexity of the parity argument and other inefficient proofs of existence
• Maximum \(k\)-regular induced subgraphs
• Reducibility among equilibrium problems
• The complexity of computing a Nash equilibrium
• The complexity of pure Nash equilibria
• A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
• Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
• Node-and edge-deletion NP-complete problems
• On the complexity of the Maximum Subgraph Problem
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• Fundamentals of Computation Theory
• Algorithms and Computation
• Computing correlated equilibria in multi-player games

This page was built for publication: The complexity of uniform Nash equilibria and related regular subgraph problems