Inapproximability of NP-Complete Variants of Nash Equilibrium.
Per AustrinMark BravermanEden ChlamtacPublished in: APPROX-RANDOM (2011)
Keyphrases
- nash equilibrium
- np complete
- game theory
- np hard
- approximation algorithms
- game theoretic
- randomly generated
- worst case
- computational complexity
- pure strategy
- pareto optimal
- mixed strategy
- stackelberg game
- nash equilibria
- solution concepts
- regret minimization
- fictitious play
- stochastic games
- variational inequalities
- equilibrium strategies
- repeated games
- polynomial time complexity
- lower bound