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

DOI10.1007/978-3-662-44803-8_5zbMATH Open1409.91010arXiv1402.3450OpenAlexW2162221666MaRDI QIDQ524372FDOQ524372

Angelo Fanelli, I. Caragiannis, N. V. Gravin

Publication date: 2 May 2017

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

Abstract: We present an algorithm that computes approximate pure Nash equilibria in a broad class of constraint satisfaction games that generalize the well-known cut and party affiliation games. Our results improve previous ones by Bhalgat et al.~(EC 10) in terms of the obtained approximation guarantee. More importantly, our algorithm identifies a polynomially-long sequence of improvement moves from any initial state to an approximate equilibrium in these games. The existence of such short sequences is an interesting structural property which, to the best of our knowledge, was not known before. Our techniques adapt and extend our previous work for congestion games (FOCS 11) but the current analysis is considerably simpler.

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

Recommendations

• Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games
• Efficient computation of approximate pure Nash equilibria in congestion games
• Computing constrained approximate equilibria in polymatrix games
• Convergence to approximate Nash equilibria in congestion games
• Approximate pure Nash equilibria in weighted congestion games

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) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Noncooperative games (91A10) Other game-theoretic models (91A40)

Cites Work

• A class of games possessing pure-strategy Nash equilibria
• Some optimal inapproximability results
• How easy is local search?
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Title not available (Why is that?)
• The complexity of pure Nash equilibria
• Convergence to approximate Nash equilibria in congestion games
• Simple Local Search Problems that are Hard to Solve
• Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games
• Circumventing the price of anarchy: leading dynamics to good behavior
• Convergence and approximation in potential games
• Theoretical aspects of local search.
• Integer Linear Programs and Local Search for Max-Cut
• Approximate Local Search in Combinatorial Optimization
• On the hardness of global and local approximation

Cited In (3)

• Efficient Equilibria in Polymatrix Coordination Games
• Congestion Games with Complementarities
• Computing better approximate pure Nash equilibria in cut games via semidefinite programming

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

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