Semidefinite programming for min-max problems and games
The authors propose a common methodology to approximate the optimal value of games in two different contexts. The first algorithm, intended to compute (or approximate) Nash equilibria in mixed strategies for static finite games or dynamic absorbing games, is based on a hierarchy of semidefinite programs to approximate the supremum of finitely many rational functions on a compact basic semi-algebraic set. Actually this latter formulation is also of self-interest in optimization. The second algorithm, intended to approximate the optimal value of polynomial games whose action sets are compact basic semi-algebraic sets, is also based on a hierarchy of semidefinite programs. This methodology provides a unified approach and a class of algorithms to compute Nash equilibria and min-max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.
- A differentiable homotopy approach for solving polynomial optimization problems and noncooperative games
- A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium Points
- A global Newton method to compute Nash equilibria.
- A globally convergent algorithm to compute all Nash equilibria for \(n\)-person games
- A procedure for finding Nash equilibria in bi-matrix games
- A semidefinite programming approach to the generalized problem of moments
- Algorithm 795
- Algorithmic Game Theory
- Approximations of Nash equilibria
- Computation of the Nash equilibrium selected by the tracing procedure in N-person games
- Computing Equilibria of N-Person Games
- Computing equilibria: a computational complexity perspective
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Correlated equilibria in continuous games: characterization and computation
- Equilibrium points in n -person games
- Equilibrium Points of Bimatrix Games
- Explicit formulas for repeated games with absorbing states
- Finding all Nash equilibria of a finite game using polynomial algebra
- Global optimization of rational functions: a semidefinite programming approach
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- GloptiPoly 3: moments, optimization and semidefinite programming
- Hard-to-Solve Bimatrix Games
- Homotopy methods to compute equilibria in game theory
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 592673 (Why is no real title available?)
- scientific article; zbMATH DE number 1827070 (Why is no real title available?)
- scientific article; zbMATH DE number 3205836 (Why is no real title available?)
- scientific article; zbMATH DE number 3270364 (Why is no real title available?)
- scientific article; zbMATH DE number 3394474 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- Moments and sums of squares for polynomial optimization and related problems
- On a Generalization of the Lemke–Howson Algorithm to Noncooperative N-Person Games
- On A Theorem of von Neumann
- On the complexity of Schmüdgen's Positivstellensatz
- On the complexity of the parity argument and other inefficient proofs of existence
- Optimization of Polynomials on Compact Semialgebraic Sets
- Repeated games with absorbing states
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Settling the complexity of computing two-player Nash equilibria
- Stochastic Games
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- The complexity of computing a Nash equilibrium
- The myth of the folk theorem
- The saddle point problem of polynomials
- Sums of even powers of \(k\)-regulous functions
- Introduction to semidefinite, conic and polynomial optimization
- Semidefinite Programming and Nash Equilibria in Bimatrix Games
- kNN Classification with an Outlier Informative Distance Measure
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Semidefinite programming for chance constrained optimization over semialgebraic sets
- Hybrid Systems: Computation and Control
- Multiple oracle algorithm to solve continuous games
- Hausdorff distance between convex semialgebraic sets
- Separable Network Games with Compact Strategy Sets
- The moment-SOS hierarchy: applications and related topics
- Sum-of-squares relaxations for polynomial min-max problems over simple sets
- Semidefinite games
- Convergence rates for the moment-SoS hierarchy
- Convergence rate for linear minimizer-estimators in the moment-sum-of-squares hierarchy
- A gradient-based optimization method using the Koopman operator
- All saddle points for polynomial optimization
- Convergent lifted Lasserre hierarchy of SDPs for minimizing expectation of piecewise polynomial loss over Wasserstein balls
This page was built for publication: Semidefinite programming for min-max problems and games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662286)
