Semidefinite programming for min-max problems and games

Rida Laraki, Jean B. LasserreMath. Program 2012 · DOI

Abstract

This paper introduces a unified numerical framework based on Semidefinite Programming (SDP) to solve complex game-theoretic problems, including $N$-player games and games with rational payoffs. By extending the "moment-SOS" hierarchy—a cornerstone of polynomial optimization—to the Minimizing the supremum of Rational Functions (MRF) problem, the authors provide a globally convergent numerical scheme. This approach effectively bridges the gap between global optimization and game theory, offering a robust method for finding Nash equilibria in finite games and optimal strategies in continuous polynomial zero-sum games.

Introduction

Finding a Nash Equilibrium—a state where no player can improve their outcome by changing their strategy unilaterally—is a fundamental challenge in game theory. While 2-player zero-sum games are efficiently solved using Linear Programming, $N$-player games and games with continuous action sets or rational payoffs are significantly more complex. Computing Nash equilibria for finite games is known to be PPAD-complete, and existing methods, such as the Lemke-Howson algorithm, often struggle with "degenerate" games or fail to scale.

Laraki and Lasserre (2009) propose a more robust, unified approach that handles non-linearities and continuous strategy sets by leveraging the power of Semidefinite Programming (SDP).

Methodology: The MRF Problem and Moment-SOS Hierarchy

The paper's primary contribution is the formulation and solution of the Minimizing the supremum of Rational Functions (MRF) problem.

1. MRF Reformulation

The authors demonstrate that the non-smooth problem of minimizing the maximum of several rational functions can be transformed into a problem of minimizing a single rational function. This is achieved by introducing a dummy variable $z$ and additional constraints, effectively smoothing the optimization landscape.

2. The Moment-SOS Hierarchy

The authors apply Lasserre’s "moment-SOS" approach to this reformulated problem. This involves:

  • Measure Representation: Representing the problem in terms of measures, which are probability distributions over the players' strategies.
  • Sums of Squares (SOS): Utilizing SOS polynomials to construct a hierarchy of increasingly tight SDP relaxations.
  • Putinar’s Property: Relying on this technical condition to ensure that the strategy sets (defined by polynomial inequalities) are compact. This guarantees that the SDP hierarchy converges to the true global optimum.

The numerical implementation was conducted using GloptiPoly 3, a Matlab-based tool designed for solving these types of SDP relaxations.

Key Insights

  • A Unified Framework: The authors show that finite games, Loomis games (rational payoffs), and absorbing games (stochastic games) can all be reduced to the same MRF problem.
  • Extension to Rational Functions: While previous work in this area focused on polynomial optimization, this paper successfully extends the "moment approach" to rational functions (fractions of polynomials). This is critical, as many game-theoretic payoffs are naturally expressed as ratios.
  • Generalization of Linear Programming: For 2-player zero-sum finite games, the first level of the SDP hierarchy collapses into the standard Linear Programming approach, demonstrating that the method is a true generalization of classical techniques.

Results and Performance

The authors evaluated their method on randomly generated reward matrices and illustrative $2 \times 2$ games. Key findings include:

  • Finite Convergence: In practice, the hierarchy often converges at a very low relaxation order (usually $r=3$ or $r=4$), rather than requiring an infinite sequence.
  • High Precision: For $2 \times 2$ games, the method yielded optimal values with a precision of $10^{-11}$ and successfully extracted exact mixed strategies.
  • N-Player Games: In 3-player non-zero-sum games, the 4th relaxation order was sufficient to extract the global minimizer (the Nash equilibrium) in 80% of the tested cases.

Limitations and Future Directions

Despite its power, the method faces the "curse of dimensionality." The size of the SDP matrices grows as $O(n^d)$, where $n$ is the number of variables and $d$ is the relaxation order, making large-scale games computationally expensive. Future work may involve exploiting "sparsity"—where a player's payoff depends only on a subset of other players—to improve scalability. Additionally, while the paper addresses zero-sum games with continuous strategies, the non-zero-sum continuous case remains an open challenge.

Conclusion

Laraki and Lasserre provide a significant advancement in computational game theory by applying global optimization techniques to the search for Nash equilibria. Their SDP-based framework offers a theoretically grounded and numerically robust alternative to traditional algorithms, capable of handling a wide array of game structures within a single mathematical paradigm.

Summary updated

BibTeX
@article{laraki2012semidefinite,
  author = {Rida Laraki and Jean B. Lasserre},
  title = {{Semidefinite programming for min-max problems and games}},
  journal = {Math. Program.},
  year = {2012},
  doi = {10.1007/s10107-010-0353-y},
}
Figure