Complexity and Optimality of the Best Response Algorithm in Random Potential Games

DOI10.1007/978-3-662-53354-3_4zbMath1403.91025OpenAlexW2508718653MaRDI QIDQ2819446

Bruno Gaujal, Stephane Durand

Publication date: 29 September 2016

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53354-3_4

zbMATH Keywords

pure Nash equilibriumbest response algorithmfinite potential games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Related Items (5)

When ``better is better than ``best ⋮ Best-response dynamics, playing sequences, and convergence to equilibrium in random games ⋮ Affine Relaxations of the Best Response Algorithm: Global Convergence in Ratio-Bounded Games ⋮ Complexity and Optimality of the Best Response Algorithm in Random Potential Games ⋮ Pure Nash Equilibria and Best-Response Dynamics in Random Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of pure strategy Nash equilibria in random games
• Potential games
• Best-response potential games
• A class of games possessing pure-strategy Nash equilibria
• Complexity and Optimality of the Best Response Algorithm in Random Potential Games
• On the impact of combinatorial structure on congestion games
• The complexity of pure Nash equilibria
• A Minimum Delay Routing Algorithm Using Distributed Computation
• The Complexity of Computing a Nash Equilibrium
• Nash equilibria in random games
• Equilibrium points in n -person games

This page was built for publication: Complexity and Optimality of the Best Response Algorithm in Random Potential Games