Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games

DOI10.1007/s00453-016-0143-xzbMath1409.91010arXiv1402.3450OpenAlexW2162221666MaRDI QIDQ524372

Angelo Fanelli, Ioannis Caragiannis, N. V. Gravin

Publication date: 2 May 2017

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

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

zbMATH Keywords

algorithmconstraint satisfactionpotential gamesalgorithmic game theoryapproximate equilibriapure Nash equilibriumcomplexity of equilibriaconstraint satisfaction games

Mathematics Subject Classification ID

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

Related Items (2)

Congestion Games with Complementarities ⋮ Efficient Equilibria in Polymatrix Coordination Games

Cites Work

• Unnamed Item
• Convergence and approximation in potential games
• Convergence to approximate Nash equilibria in congestion games
• Theoretical aspects of local search.
• How easy is local search?
• A class of games possessing pure-strategy Nash equilibria
• Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior
• Simple Local Search Problems that are Hard to Solve
• The complexity of pure Nash equilibria
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the hardness of global and local approximation
• Approximate Local Search in Combinatorial Optimization
• Integer Linear Programs and Local Search for Max-Cut
• Some optimal inapproximability results
• Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games

This page was built for publication: Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games