Semidefinite programming for min-max problems and games (Q662286): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10107-010-0353-y / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2069764498 / rank | |||
Normal rank |
Revision as of 22:28, 19 March 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