TY - JOUR

T1 - On the Complexity of Iterated Weak Dominance in Constant-Sum Games

AU - Brandt, Felix

AU - Brill, Markus

AU - Fischer, Felix

AU - Harrenstein, Paul

N1 - Funding Information:
Acknowledgements This material is based on work supported by the Deutsche Forschungsgemein-schaft under grants BR 2312/3-2, BR 2312/3-3, BR 2312/6-1, BR 2312/7-1, and FI 1664/1-1. We thank the anonymous reviewers for helpful comments.

PY - 2011/7

Y1 - 2011/7

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Constant-sum games

KW - Game theory

KW - Iterated weak dominance

KW - Solutions concepts

UR - http://www.scopus.com/inward/record.url?scp=79955841941&partnerID=8YFLogxK

U2 - 10.1007/s00224-010-9282-7

DO - 10.1007/s00224-010-9282-7

M3 - Article

AN - SCOPUS:79955841941

SN - 1432-4350

VL - 49

SP - 162

EP - 181

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -