LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.

Past Seminars

Qualitative Determinacy and Decidability of Stochastic Games with Partial Observation

Hugo Gimbert
Date
Tuesday, April 21 2009 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Hugo Gimbert (CNRS, LABRI, Bordeaux)

(Joint work with Nathalie Bertrand and Blaise Genest.)

We consider the standard model of finite two-person zero-sum stochastic games with signals. We are interested in the existence of almost-surely winning or positively winning strategies, under reachability, safety, Büchi or co-Büchi winning objectives.

We prove two qualitative determinacy results.

First, in a reachability game either player 1 can achieve almost surely the reachability objective, or player 2 can ensure almost surely the complimentary safety objective, or both players have positively winning strategies.

Second, in a Büchi game if player 1 cannot achieve almost surely the Büchi objective, then player 2 can ensure positively the complimentary co-Büchi objective.
We prove that players only need strategies with finite-memory, whose sizes range from no memory at all to doubly-exponential size, with matching lower bounds.

We provide fix-point algorithms to decide which player has an almost surely winning or positive winning strategy and compute the finite memory strategy. Complexity ranges from EXPTIME to 2EXPTIME with matching lower bounds, and better complexity can be achieved for some special cases where one of the players is better informed than her opponent.

About LSV