On the Complexity of Iterated Weak Dominance in Constant-Sum Games |
| |
Authors: | Felix Brandt Markus Brill Felix Fischer Paul Harrenstein |
| |
Affiliation: | 1.Institut für Informatik,Technische Universit?t München,Garching,Germany;2.Harvard School of Engineering and Applied Sciences,Cambridge,USA |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|