Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
From MaRDI portal
Publication:5449531
DOI10.1007/11841036_23zbMath1131.91301OpenAlexW2166112996MaRDI QIDQ5449531
Mauro Leoncini, Giovanni Resta, Bruno Codenotti
Publication date: 11 March 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11841036_23
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05)
Related Items
Constant Rank Two-Player Games are PPAD-hard ⋮ The Linear Complementarity Problems with a Few Variables per Constraint ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ On mutual concavity and strategically-zero-sum bimatrix games ⋮ Parameterized two-player Nash equilibrium ⋮ The complexity of uniform Nash equilibria and related regular subgraph problems ⋮ Some Tractable Win-Lose Games ⋮ The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values ⋮ (In)existence of equilibria for 2-player, 2-value games with semistrictly quasiconcave cost functions