Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games.
Paul W. GoldbergMatthew J. KatzmanPublished in: CoRR (2021)
Keyphrases
- query complexity
- lower bound
- nash equilibria
- concept class
- vc dimension
- game theoretic
- nash equilibrium
- pure nash equilibria
- game theory
- upper bound
- concept classes
- learning theory
- membership queries
- equivalence queries
- incomplete information
- repeated games
- concept learning
- worst case
- data complexity
- exact learning
- uniform distribution
- dnf formulas
- np hard
- sample complexity
- decision problems
- objective function
- efficient learning
- database
- pac learning
- upper and lower bounds
- lower and upper bounds
- special case
- statistical queries
- learning problems
- target concept
- resource allocation