THE COMPLEXITY OF ELIMINATING DOMINATED STRATEGIES

Authors
GILBOA I KALAI E ZEMEL E
Citation
I. Gilboa et al., THE COMPLEXITY OF ELIMINATING DOMINATED STRATEGIES, Mathematics of operations research, 18(3), 1993, pp. 553-565
Citations number
12
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
Journal title
Mathematics of operations research → ACNP
ISSN journal
0364765X
Volume
18
Issue
3
Year of publication
1993
Pages
553 - 565
Database
ISI
SICI code
0364-765X(1993)18:3<553:TCOEDS>2.0.ZU;2-M
Abstract
This paper deals with the computational complexity of some yes/no prob lems associated with sequential elimination of strategies using three domination relations: strong domination (strict inequalities), weak do mination (weak inequalities), and domination (the asymmetric part of w eak domination). Classification of various problems as polynomial or N P-complete seems to suggest that strong domination is a simple notion, whereas weak domination and domination are complicated ones.