Skip to Main content Skip to Navigation
Journal articles

The complexity of eliminating dominated strategies

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.
Complete list of metadatas

https://hal-hec.archives-ouvertes.fr/hal-00481372
Contributor : Antoine Haldemann <>
Submitted on : Thursday, May 6, 2010 - 3:00:39 PM
Last modification on : Sunday, November 18, 2012 - 6:16:37 PM

Links full text

Identifiers

Collections

Citation

Itzhak Gilboa, Ehud Kalai, Eitan Zemel. The complexity of eliminating dominated strategies. Mathematics of Operations Research, INFORMS, 1993, Vol.18, n°3, pp. 553-565. ⟨10.1287/moor.18.3.553⟩. ⟨hal-00481372⟩

Share

Metrics

Record views

254