Semidefinite programming for min-max problems and games

DOI10.1007/S10107-010-0353-YzbMATH Open1242.90158OpenAlexW2069764498MaRDI QIDQ662286FDOQ662286

Authors: R. Laraki, Jean B. Lasserre 

Publication date: 22 February 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0353-y

Recommendations

• Hybrid Systems: Computation and Control
• Min-max and robust polynomial optimization
• A semidefinite programming approach to the generalized problem of moments
• Semidefinite Programming
• Semidefinite programming relaxations for semialgebraic problems

zbMATH Keywords

semidefinite programmingmin-max optimization problemsN-player gamesNash equlibria

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Semidefinite programming (90C22) Minimax problems in mathematical programming (90C47) 2-person games (91A05) (n)-person games, (n>2) (91A06) Stochastic games, stochastic differential games (91A15)

Cites Work

• Algorithm 795
• Title not available (Why is that?)
• Algorithmic Game Theory
• Equilibrium points in n -person games
• On a Generalization of the Lemke–Howson Algorithm to Noncooperative N-Person Games
• Stochastic Games
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• GloptiPoly
• Global optimization of rational functions: a semidefinite programming approach
• Title not available (Why is that?)
• GloptiPoly 3: moments, optimization and semidefinite programming
• Title not available (Why is that?)
• The complexity of computing a Nash equilibrium
• Optimization of Polynomials on Compact Semialgebraic Sets
• Explicit formulas for repeated games with absorbing states
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
• A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium Points
• A semidefinite programming approach to the generalized problem of moments
• Semidefinite characterization and computation of zero-dimensional real radical ideals
• On the complexity of the parity argument and other inefficient proofs of existence
• Equilibrium Points of Bimatrix Games
• Approximations of Nash equilibria
• Title not available (Why is that?)
• Settling the complexity of computing two-player Nash equilibria
• On the complexity of Schmüdgen's Positivstellensatz
• Title not available (Why is that?)
• LATIN 2004: Theoretical Informatics
• Homotopy methods to compute equilibria in game theory
• Moments and sums of squares for polynomial optimization and related problems
• Repeated games with absorbing states
• A globally convergent algorithm to compute all Nash equilibria for \(n\)-person games
• Finding all Nash equilibria of a finite game using polynomial algebra
• Correlated equilibria in continuous games: characterization and computation
• Title not available (Why is that?)
• Hard-to-Solve Bimatrix Games
• Computing Equilibria of N-Person Games
• The myth of the folk theorem
• A global Newton method to compute Nash equilibria.
• Title not available (Why is that?)
• A differentiable homotopy approach for solving polynomial optimization problems and noncooperative games
• A procedure for finding Nash equilibria in bi-matrix games
• On A Theorem of von Neumann
• Computation of the Nash equilibrium selected by the tracing procedure in \(N\)-person games
• Computing equilibria: a computational complexity perspective

Cited In (14)

• The saddle point problem of polynomials
• Hybrid Systems: Computation and Control
• Hausdorff distance between convex semialgebraic sets
• Semidefinite Programming and Nash Equilibria in Bimatrix Games
• Semidefinite programming for chance constrained optimization over semialgebraic sets
• The moment-SOS hierarchy: applications and related topics
• DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
• kNN Classification with an Outlier Informative Distance Measure
• Introduction to semidefinite, conic and polynomial optimization
• Semidefinite games
• Sum-of-squares relaxations for polynomial min-max problems over simple sets
• Multiple oracle algorithm to solve continuous games
• Sums of even powers of \(k\)-regulous functions
• Separable Network Games with Compact Strategy Sets

Uses Software

• PHCpack
• SeDuMi
• GloptiPoly

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)