The Complexity of Eliminating Dominated Strategies
Published Online:1 Aug 1993https://doi.org/10.1287/moor.18.3.553
Abstract
This paper deals with the computational complexity of some yes/no problems associated with sequential elimination of strategies using three domination relations: strong domination (strict inequalities), weak domination (weak inequalities), and domination (the asymmetric part of weak domination). Classification of various problems as polynomial or NP-complete seems to suggest that strong domination is a simple notion, whereas weak domination and domination are complicated ones.
