Article ID: | iaor1994442 |
Country: | United States |
Volume: | 18 |
Issue: | 3 |
Start Page Number: | 553 |
End Page Number: | 565 |
Publication Date: | Aug 1993 |
Journal: | Mathematics of Operations Research |
Authors: | Gilboa Itzhak, Zemel Eitan, Kalai Ehud |
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.