[Séminaire Caen] Computing Better Approximate Pure Nash Equilibria in Payoff-maximization Potential Games - UFR SEGGAT - MRSH

Abstract:
Potential games are a fundamental class of games in which pure Nash equilibria are guaranteed to exist, but computing such equilibria is computationally intractable for broad classes of games. This has motivated a large body of work on the computation of approximate pure Nash equilibria. In this paper, we focus on the class of payoff-maximization potential games, which captures many natural optimization settings. For this class, the strong theoretical guarantees of existing methods are typically limited to narrow subclasses of games, most notably Pd-Flip games. We show that standard approaches based on unilateral improvement moves may fail to yield meaningful approximation guarantees across a broad family of payoff-maximization potential games. To overcome this limitation, we propose an algorithmic framework based on coordinated deviations by small groups of players, which converges to an approximate pure Nash equilibrium with a provable guarantee that depends on natural game-dependent parameters. In the special case of Pd-Flip games, our framework specializes to existing algorithms and matches their approximation guarantees.