On the complexity of deciding degeneracy in a bimatrix game with sparse payoff matrix

DOI10.1016/j.tcs.2012.10.053zbMath1257.68072MaRDI QIDQ1939257

Ye Du

Publication date: 4 March 2013

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

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

zbMATH Keywords

degeneracy; NP-complete; bimatrix game; sparsity; computational economics

Mathematics Subject Classification ID

91A05: 2-person games

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)