Inapproximability of NP-Complete Variants of Nash Equilibrium
Per AustrinMark BravermanEden ChlamtacPublished in: CoRR (2011)
Keyphrases
- nash equilibrium
- np complete
- game theory
- np hard
- approximation algorithms
- game theoretic
- randomly generated
- worst case
- pareto optimal
- variational inequalities
- nash equilibria
- solution concepts
- stochastic games
- mixed strategy
- pure strategy
- computational complexity
- polynomial time complexity
- regret minimization
- stackelberg game
- repeated games
- imperfect information
- fictitious play
- incentive compatible
- scheduling problem
- optimal solution
- multi agent
- objective function
- learning algorithm