The Library
On the complexity of iterated weak dominance in constant-sum games
Tools
Brandt, Felix, Brill, Markus, Fischer, Felix and Harrenstein, Paul (2011) On the complexity of iterated weak dominance in constant-sum games. Theory of Computing Systems, 49 (1). pp. 162-181. doi:10.1007/s00224-010-9282-7 ISSN 1432-4350.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00224-010-9282-7
Abstract
In game theory, an action is said to be weakly dominated if there exists another action of the same player that, with respect to what the other players do, is never worse and sometimes strictly better. We investigate the computational complexity of the process of iteratively eliminating weakly dominated actions (IWD) in two-player constant-sum games, i.e., games in which the interests of both players are diametrically opposed. It turns out that deciding whether an action is eliminable via IWD is feasible in polynomial time whereas deciding whether a given subgame is reachable via IWD is NP-complete. The latter result is quite surprising, as we are not aware of other natural computational problems that are intractable in constant-sum normal-form games. Furthermore, we slightly improve on a result of V. Conitzer and T. Sandholm by showing that typical problems associated with IWD in win-lose games with at most one winner are NP-complete.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Theory of Computing Systems | ||||||
Publisher: | Springer | ||||||
ISSN: | 1432-4350 | ||||||
Official Date: | July 2011 | ||||||
Dates: |
|
||||||
Volume: | 49 | ||||||
Number: | 1 | ||||||
Page Range: | pp. 162-181 | ||||||
DOI: | 10.1007/s00224-010-9282-7 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |