Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Qualitative Determinacy and Decidability of Stochastic Games with Partial Observation

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Hugo Gimbert
Date
Le mardi 21 avril 2009 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
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.


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 19 février

Les séminaires précédents