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

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin

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 ga…