On the Complexity of Deciding Degeneracy in Games
arXiv:0905.3012
Abstract
We show that it is NP-Complete to decide whether a bimatrix game is degenerate and it is Co-NP-Complete to decide whether a bimatrix game is nondegenerate.
arXiv:0905.3012
We show that it is NP-Complete to decide whether a bimatrix game is degenerate and it is Co-NP-Complete to decide whether a bimatrix game is nondegenerate.