M / E23

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 such games based on solving systems of polynomial equations and separation bounds. When the number of positions of the game is a constant, then the algorithm runs in polynomial time and is the first with this property. We will also present lower bounds on the algebraic degree of the values of stochastic games, induced from the irreducibility of polynomials that have coefficients that depend on the combinatorial parameters of the games, based on a generalization of Eisenstein criterion.

Elias Tsigaridas

Paris