file.pdf (326.47 kB)
Download file

Complexity of (Iterated) Dominance

Download (326.47 kB)
journal contribution
posted on 01.01.2008, 00:00 by Vincent Conitzer, Tuomas W Sandholm

We study various computational aspects of solving games using dominance and iterated dominance. We first study both strict and weak dominance (not iterated), and show that checking whether a given strategy is dominated by some mixed strategy can be done in polynomial time using a single linear program solve. We then move on to iter- ated dominance. We show that determining whether there is some path that eliminates a given strategy is NP-complete with iterated weak dominance. This allows us to also show that determining whether there is a path that leads to a unique solution is NP-complete. Both of these results hold both with and without dominance by mixed strategies. (A weaker version of the second result (only without dominance by mixed strategies) was already known [7].) Iterated strict dominance, on the other hand, is path-independent (both with and without dominance by mixed strategies) and can therefore be done in polynomial time.

History

Date

01/01/2008

Usage metrics

Exports