Semidefinite programming for min-max problems and games (Q662286)

From MaRDI portal
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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references