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

Loading Map....
December 13, 2016 4:00 pm - 5:30 pm
SBA Research
Favoritenstraße 16
1040 Wien

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.


By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.