The complexity of eliminating dominated strategies - Archive ouverte HAL Access content directly
Journal Articles Mathematics of Operations Research Year : 1993

The complexity of eliminating dominated strategies

(1) , (1) , (1)
1

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.

Dates and versions

hal-00481372 , version 1 (06-05-2010)

Identifiers

Cite

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

Collections

HEC
85 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More