10.4230/LIPICS.STACS.2010.2448
Brandt, Felix
Felix
Brandt
Fischer, Felix
Felix
Fischer
Holzer, Markus
Markus
Holzer
On Iterated Dominance, Matrix Elimination, and Matched Paths
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Article
Algorithmic Game Theory
Computational Complexity
Iterated Dominance
Matching
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
2010
2010-03-09
2010-03-09
2010-03-09
en
urn:nbn:de:0030-drops-24485
10.4230/LIPIcs.STACS.2010
978-3-939897-16-3
1868-8969
10.4230/LIPIcs.STACS.2010
LIPIcs, Volume 5, STACS 2010
27th International Symposium on Theoretical Aspects of Computer Science
2013
5
11
107
118
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
5
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
307370 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We study computational problems arising from the iterated removal of weakly dominated actions in anonymous games. Our main result shows that it is NP-complete to decide whether an anonymous game with three actions can be solved via iterated weak dominance. The two-action case can be reformulated as a natural elimination problem on a matrix, the complexity of which turns out to be surprisingly difficult to characterize and ultimately remains open. We however establish connections to a matching problem along paths in a directed graph, which is computationally hard in general but can also be used to identify tractable cases of matrix elimination. We finally identify different classes of anonymous games where iterated dominance is in P and NP-complete, respectively.
LIPIcs, Vol. 5, 27th International Symposium on Theoretical Aspects of Computer Science, pages 107-118