Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-077 | 23rd May 2008 00:00

On Iterated Dominance, Matrix Elimination, and Matched Paths

RSS-Feed




TR08-077
Authors: Felix Brandt, Felix Fischer, Markus Holzer
Publication: 28th August 2008 20:13
Downloads: 1633
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint