Guest Talk: "Exact Algorithms for Stochastic Games and Polynomial System Solving"

Elias Tsigaridas, POLSYS team, INRIA Paris, France, is giving a guest talk about "Exact Algorithms for Stochastic Games and Polynomial System Solving".

Abstract: Shapley introduced stochastic games in 1953 and since then they are a subject of intensive study. They model dynamic interactions in an environment that changes in response to the behavior of the players. Their applications include industrial organization, resource economics, market games, communication networks.

In this context Shapley's discounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. For these games we can express the equilibrium strategies and the payoffs of the players using systems of polynomial equations and inequalities.

We present an exact algorithm for solving such games based on the properties of polynomial system solving.  When the number of positions of the game is constant, the algorithm runs in polynomial time and is the first with this property.

If time permits, 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.

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

This event is hosted by the IEEE CS/SMCS Austria Chapter.