Complexity of Verifying Game Equilibria

摘要

We consider the problem of verifying game equilibria in multi-agent systems. We first identify a certain class of games where Nash or Bayesian Nash equilibria can be verified in polynomial time. Second, we show that verifying a dominant strategy equilibrium is NP-complete even for normal form games. Eventually, we consider general games and discuss the complexity of equilibrium verification.