The complexity of eliminating dominated strategies

Itzhak Gilboa, Ehud Kalai and Eitan Zemel
Additional contact information
Ehud Kalai: Northwestern University [Evanston]
Eitan Zemel: Northwestern University [Evanston]

Post-Print from HAL

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.

Keywords: Game theory; Player strategy; Computability; Polynomial time; NP complete problem (search for similar items in EconPapers)
Date: 1993-08
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Published in Mathematics of Operations Research, 1993, Vol.18, n°3, pp. 553-565. ⟨10.1287/moor.18.3.553⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
Working Paper: The Complexity of Eliminating Dominated Strategies (1989)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00481372

DOI: 10.1287/moor.18.3.553

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().