Soutenance de thèse de Marcin Przybyłko (EDP-UNC) ouverte à tous.

Cette thèse en informatique est en co-tutelle entre l’UNC et l’Université de Varsovie. La soutenance est en anglais, elle a lieu à l’Université de Varsovie par visioconférence avec l’UNC.

Résumé

Nous étudions les jeux ramifiés introduits par Mio pour définir la sémantique du µ-calcul modal stochastique. Ces jeux stochastiques infinis à information imparfaite joués tour à tour par deux joueurs forment une sous-classe des jeux infinis à somme nulle. Elles étendent les jeux de Gale-Stewart en ce que chaque partie peut se scinder en sous-parties qui se déroulent indépendamment et simultanément. En conséquence, chaque partie a une structure arborescente, contrairement à la structure linéaire des parties des jeux de Gale-Stewart.
Dans cette thèse, nous étudions les jeux ramifiés réguliers. Ceux-ci ont pour caractéristique d’avoir leurs ensembles gagnants régulières, c’est à dire, des ensembles d’arbres infinis reconnus par automates finis d’arbres. Nous nous intéressons aux problèmes de détermination, de calcul des valeurs de jeux ramifiés réguliers et de calcul effectif de la mesure d’un ensemble régulier d’arbres.
La détermination est une propriété qui garantit qu’aucun des joueurs n’acquiert ou ne perd un avantage en révélant sa stratégie au début d’une partie. En général, les jeux ramifiés réguliers ne sont pas déterminés, pas même dans les stratégies mixtes, ni lorsque les ensembles gagnants sont topologiquement simples. Du côté positif, nous montrons que les jeux ramifiés réguliers ayant pour ensembles gagnants des ouverts sont déterminés en stratégies mixtes. De plus, dans le cas où les ensembles gagnants sont reconnus par ce qu’on appelle des automates de jeu, nous montrons la détermination en stratégies pures. Ces deux résultats sont accompagnés d’exemples qui montrent les limites des techniques utilisées.

Nous donnons une réponse au problème de calcul des valeurs des jeux ramifiés réguliers. Nous montrons que les valeurs mixtes des jeux ramifiés non stochastiques ne sont pas calculables et que les valeurs pures des jeux ramifiés stochastiques ne sont pas calculables. En revanche, nous donnons un algorithme qui calcule les valeurs pures des jeux ramifiés non stochastiques.
Nous donnons une réponse partielle au problème de calcul des mesures d’un ensemble régulier d’arbres. En particulier, nous donnons un algorithme qui calcule la mesure uniforme dans les deux cas suivants : lorsque l’ensemble est défini par une formule de la logique du premier ordre qui n’utilise pas la relation de descendant, ou lorsque l’ensemble est défini par une combinaison booléenne de requêtes conjonctives.
Finalement, nous utilisons des données réelles pour présenter comment on peut employer des techniques de la théorie des jeux stochastiques en pratique. Nous proposons une procédure générale qui à partir d’une série temporelle crée un modèle réactif capable de prédire l’évolution du système. Ce modèle facilite aussi les choix des stratégies permettant d’atteindre certains objectifs prédéfinis. La procédure nous sert ensuite à créer un jeux basé sur les processus décisionnels de Markov. Le jeu obtenu peut être utilisé pour prédire et contrôler le niveau d’infestation d’un verger expérimental.

Contact

Teodor Knapik

teodor.knapick@unc.nc