Potential games form a key class of games in which the existence of pure Nash equilibria is guaranteed, yet their computation is often intractable. This challenge has motivated extensive research on the computation of approximate equilibria. In this talk, we focus on payoff-maximization potential games. We introduce an algorithmic framework for efficiently computing approximate pure Nash equilibria in P_d-Flip games, and then present a recent extension based on group deviations that applies to more general potential games. The connection with Markov Random Fields (MRFs) is emphasized throughout the presentation, as it motivates the study of equilibrium computation for problems related to MRFs. 

Retour page d'accueil du séminaire