Tight SoS-Degree Bounds for Approximate Nash Equilibria.
Aram W. HarrowAnand NatarajanXiaodi WuPublished in: Computational Complexity Conference (2016)
Keyphrases
- nash equilibria
- upper bound
- lower bound
- incomplete information
- worst case
- game theory
- stochastic games
- nash equilibrium
- generalization error bounds
- fictitious play
- game theoretic
- pure strategy
- upper and lower bounds
- congestion games
- np hard
- solution concepts
- artificial intelligence
- normal form games
- cooperative
- optimal solution
- multi agent