Prochain Exposé
April 13, 3PM (Paris/France). Salle Aurigny.
Benjamin Bordais (Univ Paris-Saclay)
Playing (almost-)optimally in concurrent games with parity objectives
In a two-player win/lose concurrent graph game, two players at a given state concurrently (i.e. simultaneously) choose an action (among a finite set of available actions) which leads to another state. The process is repeated indefinitely thus forming an infinite sequence of states. The winnor of the game is determined by an objective (i.e. a subset of infinite sequences of states). Concurrent games are more general than their turn-based counterparts in which, at each state, only one player chooses the next state to visit. However, this comes at the cost of not enjoying the desirable properties that turn-based games do. (For instance, in turn-based games with parity objectives, there are always optimal strategies that are deterministic and positional whereas optimal strategies do not exist in general in concurrent games.) In this talk, I will illustrate the turn-based and concurrent formalisms and show on specific examples why concurrent games behave more poorly than turn-based games. Then I will present how to build concurrent games that are more general than turn-based games but still enjoy similar properties that turn-based game do for specific objectives.
Exposés des semaines suivantes
Vos propositions sont les bienvenues !
