Computing Better Approximate Pure Nash Equilibria in Payoff-maximization Potential Games

Abstract

Potential games are a fundamental class of games in which pure Nash equilibria are guaranteed to exist, yet computing such equilibria is computationally intractable for several natural subclasses of these games. This has led to extensive research on computing approximate pure Nash equilibria. In this paper, we study payoff-maximization potential games, a class that captures many natural optimization settings. For these games, strong theoretical guarantees are known only for restricted subclasses, most notably $P_d$--{\sc Flip} games, which belong to the class of constraint satisfaction games. We show that standard approaches based on unilateral improvement moves can fail to provide meaningful approximation guarantees even for natural extensions of constraint satisfaction games. To overcome this limitation, we propose an algorithmic framework based on coordinated strategy changes by small groups of players that computes an approximate pure Nash equilibrium with a provable guarantee depending on a natural parameter of the game. In the special case of $P_d$–{\sc Flip} games, our framework can be configured to recover existing algorithms, preserving their approximation guarantees and convergence time.