Lower bounds for the query complexity of equilibria in Lipschitz games

DOI10.1007/978-3-030-85947-3_9zbMath1492.91014arXiv2107.03898OpenAlexW3202943119MaRDI QIDQ2670917

Matthew J. Katzman, Paul W. Goldberg

Publication date: 1 June 2022

Full work available at URL: https://arxiv.org/abs/2107.03898

zbMATH Keywords

Nash equilibriumquery complexityLipschitz games

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Algorithmic game theory and complexity (91A68)

Related Items (3)

Lower bounds for the query complexity of equilibria in Lipschitz games ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games

Cites Work

• Unnamed Item
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• The query complexity of correlated equilibria
• Logarithmic query complexity for approximate Nash computation in large games
• Lipschitz continuity and approximate equilibria
• Approximate Nash equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• Best-reply dynamics in large binary-choice anonymous games
• Non-cooperative games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Query Complexity of Approximate Nash Equilibria
• Lipschitz Games
• Fast Convergence of Best-Reply Dynamics in Aggregative Games

This page was built for publication: Lower bounds for the query complexity of equilibria in Lipschitz games