ECCC-Report TR08-077https://eccc.weizmann.ac.il/report/2008/077Comments and Revisions published for TR08-077en-usThu, 28 Aug 2008 20:13:35 +0300
Paper TR08-077
| On Iterated Dominance, Matrix Elimination, and Matched Paths |
Felix Brandt,
Felix Fischer,
Markus Holzer
https://eccc.weizmann.ac.il/report/2008/077We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated as a natural elimination problem on a matrix. While enigmatic by itself, the latter turns out to be a special case of matching along paths in a directed graph, which we show to be computationally hard in general but also use to identify tractable cases of matrix elimination. We further identify different classes of anonymous games where iterated dominance is in P and NP-complete, respectively.
Thu, 28 Aug 2008 20:13:35 +0300https://eccc.weizmann.ac.il/report/2008/077