SPEAKER: Vincent Conitzer TITLE: Computational Aspects of (Iterated) Dominance, Nash Equilibrium, and What Lies In-Between ABSTRACT: Two fundamental solution concepts in game theory are (iterated) dominance and Nash equilibrium. A strategy (probability distribution over the player's actions) is dominated if it performs worse than some other strategy, against any opponent strategies. In iterated dominance, dominated strategies are removed, after which other strategies may become dominated, etc. A Nash equilibrium consists of a strategy for each player so that no player has an incentive to deviate. A Nash equilibrium always exists (Nash 50), but the question of how hard it is to compute one has been called "together with factoring [...] the most important concrete open question on the boundary of P today" (Papadimitriou 01). In this talk, I will discuss some of our most recent results on computational questions that concern these solution concepts. I will also provide a generalized eliminability definition that spans a spectrum from dominance to Nash equilibrium. Whether a strategy can be eliminated can be computed efficiently if we are close to the "dominance" end of this spectrum, but it is coNP-complete at the "Nash" end of the spectrum.