On Iterated Dominance, Matrix Elimination, and Matched Paths

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.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.107-118, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455361
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 11:17:46
Dernière modification le : mercredi 10 février 2010 - 11:26:38
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:53:49

Fichier

brandt.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455361, version 1

Collections

Citation

Felix Brandt, Felix Fischer, Markus Holzer. On Iterated Dominance, Matrix Elimination, and Matched Paths. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.107-118, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455361〉

Partager

Métriques

Consultations de la notice

170

Téléchargements de fichiers

473