TY - GEN
T1 - On iterated dominance, matrix elimination, and matched paths
AU - Brandt, Felix
AU - Fischer, Felix
AU - Holzer, Markus
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Algorithmic game theory
KW - Computational complexity
KW - Iterated dominance
KW - Matching
UR - http://www.scopus.com/inward/record.url?scp=79960731297&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2010.2448
DO - 10.4230/LIPIcs.STACS.2010.2448
M3 - Conference contribution
AN - SCOPUS:79960731297
SN - 9783939897163
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 107
EP - 118
BT - STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science
T2 - 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010
Y2 - 4 March 2010 through 6 March 2010
ER -