On Iterated Dominance, Matrix Elimination, and Matched Paths

Computer Science – Computer Science and Game Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

12 pages, 3 figures, 27th International Symposium on Theoretical Aspects of Computer Science (STACS)

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On Iterated Dominance, Matrix Elimination, and Matched Paths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Iterated Dominance, Matrix Elimination, and Matched Paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Iterated Dominance, Matrix Elimination, and Matched Paths will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-7420

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.