On iterated dominance, matrix elimination, and matched paths

Felix Brandt, Felix Fischer, Markus Holzer

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationSTACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science
Pages107-118
Number of pages12
DOIs
StatePublished - 2010
Externally publishedYes
Event27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 - Nancy, France
Duration: 4 Mar 20106 Mar 2010

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume5
ISSN (Print)1868-8969

Conference

Conference27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010
Country/TerritoryFrance
CityNancy
Period4/03/106/03/10

Keywords

  • Algorithmic game theory
  • Computational complexity
  • Iterated dominance
  • Matching

Fingerprint

Dive into the research topics of 'On iterated dominance, matrix elimination, and matched paths'. Together they form a unique fingerprint.

Cite this