Evènement pour le groupe
Modélisation et Verification
Date | 2013-05-30 11:30-12:30 |
Titre | Exact algorithms for stochastic games and real algebraic geometry |
Résumé | 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 separation
bounds from real algebraic geometry. When the number of positions of the game is
constant, the algorithm runs in polynomial time and is the first with this property.
We 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. |
Lieu | 076 |
Orateur | Elias Tsigaridas |
Email | elias.tsigaridas@gmail.com |
Url | LIP6 |
Aucun document lié à cet événement.
RetourRetour à l'index