Reference:

Javier Esparza, Thomas Gawlitza, Stefan Kiefer, and Helmut Seidl. Approximative methods for monotone systems of min-max-polynomial equations. Technical report, Technische Universität München, Institut für Informatik, February 2008.

Abstract:

A monotone system of min-max-polynomial equations (min-max-MSPE) over the variables X_1, ..., X_n has for every i exactly one equation of the form X_i = f_i(X_1, ..., X_n) where each f_i(X_1, ..., X_n) is an expression built up from polynomials with non-negative coefficients, minimum- and maximum-operators. The question of computing least solutions of min-max-MSPEs arises naturally in the analysis of recursive stochastic games. Min-max-MSPEs generalize MSPEs for which convergence speed results of Newton's method have been established in previous papers. We present the first methods for approximatively computing least solutions of min-max-MSPEs which converge at least linearly. Whereas the first one converges faster, a single step of the second method is cheaper. Furthermore, we compute epsilon-optimal positional strategies for the player who wants to maximize the outcome in a recursive stochastic game.

Suggested BibTeX entry:

@techreport{EGKS08:minMaxTechRep,
    author = {Javier Esparza and Thomas Gawlitza and Stefan Kiefer and Helmut Seidl},
    institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
    month = {February},
    title = {Approximative Methods for Monotone Systems of min-max-Polynomial Equations},
    year = {2008}
}