THE COMPLEXITY OF ELIMINATING DOMINATED STRATEGIES

• 成果类型: Article
• 署名作者: GILBOA, I; KALAI, E; ZEMEL, E
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.18.3.553
• 发表日期: 1993
• 页码: 553-565
• 关键词: modeling rational players; BEHAVIOR

摘要

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.