Complexity and optimality of the best response algorithm in random potential games

DOI10.1007/978-3-662-53354-3_4MaRDI QIDQ2819446zbMATH OpenOpenAlexFDO

Authors S. Durand, Bruno Gaujal

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

best response algorithmfinite potential gamespure Nash equilibrium

Mathematics Subject Classification ID

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

Recommendations

• Best-response dynamics, playing sequences, and convergence to equilibrium in random games
• On best-response dynamics in potential games
• Convergence and approximation in potential games
• The efficiency of best-response dynamics
• The speed of convergence in congestion games under best-response dynamics

Cites work

• A class of games possessing pure-strategy Nash equilibria
• A Minimum Delay Routing Algorithm Using Distributed Computation
• Best-response potential games
• Comparison methods for stochastic models and risks
• Complexity and optimality of the best response algorithm in random potential games
• Equilibrium points in n -person games
• scientific article; zbMATH DE number 2038734 (Why is no real title available?)
• scientific article; zbMATH DE number 6469241 (Why is no real title available?)
• Nash equilibria in random games
• On the impact of combinatorial structure on congestion games
• On the number of pure strategy Nash equilibria in random games
• Potential games
• The complexity of computing a Nash equilibrium
• The complexity of pure Nash equilibria

Cited in

(11)

• Deterministic approximation of best-response dynamics for the matching pennies game
• A note on the complexity of determining optimal strategies in games with common payoffs
• When ``better is better than ``best
• Complexity and optimality of the best response algorithm in random potential games
• Pure Nash equilibria and best-response dynamics in random games
• 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
• Games and random search
• Best-response dynamics in two-person random games with correlated payoffs
• Exact characterisation of asymptotic running time for approximate gradient descent on random graphs
• p-best response set

This page was built for publication: Complexity and optimality of the best response algorithm in random potential games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819446)