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.