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

Ioannis Caragiannis (), Angelo Fanelli () and Nick Gravin
Additional contact information
Ioannis Caragiannis: CTI - Computer Technology Institute - Computer Technology Institute
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique
Nick Gravin: Microsoft Research [Redmond] - Microsoft Corporation [Redmond, Wash.]

Post-Print from HAL

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.

Keywords: Simulation; modeling; constraint satisfaction games (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Published in Ron Lavi. Algorithmic Game Theory, Springer Berlin Heidelberg, pp.49-60, 2014, Lecture Notes in Computer Science, 978-3-662-44802-1. ⟨10.1007/978-3-662-44803-8_5⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-01104061

DOI: 10.1007/978-3-662-44803-8_5

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().