Semidefinite programming for min-max problems and games (Q662286): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: SeDuMi / rank | |||
Normal rank |
Revision as of 17:56, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Semidefinite programming for min-max problems and games |
scientific article |
Statements
Semidefinite programming for min-max problems and games (English)
0 references
22 February 2012
0 references
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.
0 references
N-player games
0 references
Nash equlibria
0 references
min-max optimization problems
0 references
semidefinite programming
0 references