Seminars

Title:
Game Theory and Real Algebraic Geometry:
algorithms and bounds for stochastic games

Abstract:
Shapley's discounted stochastic games and Everett's recursive games are classical models of game theory describing two-player zero-sum games of potentially infinite duration.
We present an exact algorithm for solving exactly such games based on separation bounds from real algebraic geometry.
We also present lower bounds on the algebraic degree of the values of stochastic and recursive games induced from the irreducibility of certain univariate polynomials that have coefficients that depend on the combinatorial parameters of the games.

Joint work with K.A. Hansen, M. Koucky, N. Lauritzen, and P.B. Miltersen.