Approximating Pure Nash Equilibrium in Cut, Party Affiliation, and Satisfying Games

Cut games and party affiliation games are well-known classes of potential games. Schaffer and Yannakakis showed that computing pure Nash equilibrium in these games is PLS- complete. In general potential games, even the problem of computing any finite approximation to a pure equilibrium is also PLS-complete. We show that for any є \u3e 0, we design an algorithm to compute in polynomial time a (3 + є)- approximate pure Nash equilibrium for cut and party affiliation games. Prior to our work, only a trivial polynomial factor approximation was known for these games. Our approach extends beyond cut and party affiliation games to a more general class of satisfiability games. A key idea in our approach is a pre-processing phase that creates a partial order on the players. We then apply Nash dynamics to a sequence of restricted games derived from this partial order. We show that this process converges in polynomial-time to an approximate Nash equilibrium by strongly utilizing the properties of the partial order. This is in strong contrast to earlier results for some other classes of potential games that compute an approximate equilibrium by a direct application of Nash dynamics on the original game. In fact, we also show that such a technique cannot yield FPTAS for computing equilibria in cut and party affiliation games