Finite versus infinite arenas for positionality in infinite duration games

Prelegent(ci)

Pierre Ohlmann

Afiliacja

MIM UW

Termin

7 czerwca 2023 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

This talk is about positionality (for the protagonist) in infinite duration games, either over finite or over arbitrary arenas. The aim is to compare the two notions. Classically, it is well known that the parity objective is positional over arbitrary arenas, and that the mean-payoff objective is positional over finite arenas, but not infinite ones. Given these two important examples, it is reasonable to consider the two notions separately. Some recent developments suggest that positionality is better behaved when arbitrary arenas are considered. I will discuss two results in this direction. (1) With an adequate definition (limsup <0), the mean-payoff objective is actually positional over arbitrary arenas. (2) For any objective W which is positional over finite arenas, there is an objective W' which coincides with W over finite arenas and is positional over arbitrary ones. (Joint work with Michał Skrzypczak) These results are proved using the new toolbox provided by universal graphs, which I will also recall. I will try to give a full proof of (1), and if time allows, sketch a proof of (2).

---