Computing Approximate Nash Equilibria in Polymatrix Games

Argyrios Deligkas, John Fearnley, Rahul Savani, Paul G. Spirakis

Introduction

In game theory, the Nash equilibrium represents a stable state where no player can improve their payoff by unilaterally changing their strategy. While conceptually foundational, the computational complexity of finding an exact Nash equilibrium is a significant hurdle. The problem is known to be PPAD-complete, even for two-player games, suggesting that no polynomial-time algorithm exists unless P = PPAD. This has shifted the focus of algorithmic game theory toward finding approximate ($\epsilon$-Nash) equilibria, where players have a maximum incentive of $\epsilon$ to deviate.

For two-player (bimatrix) games, several constant-factor approximation algorithms exist. However, as the number of players ($n$) increases, the problem becomes substantially more difficult. In general $n$-player games, existing polynomial-time approximations often provide guarantees that degrade as $n$ grows, eventually approaching a trivial bound of 1. This paper addresses this gap by focusing on polymatrix games, a structured class of multi-player games where the approximation guarantee remains independent of the number of players.

Polymatrix Games and the Approximation Challenge

Polymatrix games are a "succinct" representation of multi-player interactions. In these games, the players are nodes in a network, and the total payoff for any player is the sum of payoffs from separate two-player games played against their neighbors. While more structured than general strategic-form games, they remain complex enough to capture many real-world scenarios, including auctions and social network dynamics.

The primary contribution of this research is a polynomial-time algorithm that computes a $(0.5 + \delta)$-Nash equilibrium for any polymatrix game. Crucially, this $0.5$ bound is constant and does not increase regardless of how many players are added to the network, providing a robust solution for large-scale systems.

Methodology: Gradient Descent on Regret

The proposed algorithm is based on a gradient descent approach applied to the "maximum regret" of the players. Regret is defined as the difference between a player's current payoff and the payoff they could achieve by switching to their best possible response. To minimize this regret, the authors employ several key technical strategies:

  1. Payoff Normalization: To ensure the approximation $\epsilon$ is meaningful across different network topologies, the authors rescale payoffs so that each player's total possible payoff range is exactly $[0, 1]$.
  2. Steepest Descent via Linear Programming: At each step, the algorithm identifies a direction to move the current strategy profile that reduces the maximum regret. The authors demonstrate that this direction of steepest descent can be efficiently found by solving a specific Linear Program (LP).
  3. $\delta$-Best Responses: To guarantee termination in polynomial time, the algorithm utilizes "$\delta$-best responses"—strategies that are within $\delta$ of the optimal response—rather than searching for the absolute best response in every iteration. This modification ensures the algorithm converges in $O(1/\delta^2)$ iterations.

Key Insights and Theoretical Results

The work successfully generalizes the influential algorithm by Tsaknakis and Spirakis (2009), which was originally designed for two-player bimatrix games. While the original TS algorithm relied on maintaining equal regret among players, this paper develops a more flexible analysis that accommodates the unequal regrets inherent in multi-player polymatrix settings.

The $(0.5 + \delta)$ Bound

The authors prove that the gradient descent does not settle at arbitrary points; rather, any stationary point (a point where no further local improvement in regret is possible) is guaranteed to be at least a $(0.5 + \delta)$-Nash equilibrium. This result is significant because it provides a universal performance guarantee for a broad class of games.

Application to Bayesian Games

Beyond polymatrix games, the paper demonstrates a mathematical reduction from two-player Bayesian games to polymatrix games. In a Bayesian game, players have private information (their "type") and uncertainty about their opponent's type. By transforming these into polymatrix games, the authors provide the first polynomial-time algorithm to find a $(0.5 + \delta)$-Bayesian Nash Equilibrium (BNE) in these settings.

Limitations and Future Work

While the $0.5$ bound is a major advancement for $n$-player games, it remains higher than the $0.3393$ bound currently known for two-player bimatrix games. It remains an open question whether the analysis can be tightened or if a different initialization strategy could lower this constant.

Additionally, the paper focuses on $\epsilon$-Nash equilibria rather than the stricter "well-supported" approximate Nash equilibrium ($\epsilon$-WSNE). In a well-supported equilibrium, players are not only limited in their total regret but are also forbidden from playing any individual strategy that is significantly sub-optimal. Extending these results to $\epsilon$-WSNE in polymatrix games represents a challenging and important direction for future research.

Summary updated

BibTeX
@article{deligkas2017computing,
  author = {Argyrios Deligkas and John Fearnley and Rahul Savani and Paul G. Spirakis},
  title = {{Computing Approximate Nash Equilibria in Polymatrix Games}},
  journal = {Algorithmica},
  year = {2017},
  doi = {10.1007/s00453-015-0078-7},
}
Figure