We introduce Distributed Asynchronous Potential function Decrease (DAPD), a discrete-time, graph-based algorithm for finding pure Nash equilibria in ordinal potential games. Two different settings are studied: one in which cost functions are twice-differentiable and convex, with Lipschitz first derivatives, and another when costs are only Lipschitz-continuous and may be non-convex. A novel graph-based update scheduler is proposed, which accelerates DAPD convergence by allowing parallel, decentralized updates of non-neighboring players. The scheduler chooses the next player to update in each neighborhood as the one with the largest decrease in cost function at the previous update. The graph topology is fixed, connected and undirected, and the update of each player depends only on its neighbors. We prove that when run with the proposed scheduler, DAPD converges to a pure Nash equilibrium in the differentiable setting, and to an ɛ ɛ -Nash equilibrium in the Lipschitz setting. In numerical experiments, DAPD with the new scheduler converges faster than with a round-robin scheduler, while better balancing the number of computations and communications than several synchronous and asynchronous baselines.
Sântejudean et al. (Thu,) studied this question.