18/02/2026, 16:00 — 17:00 Europe/Lisbon —
Online
Jan Swart, Czech Academy of Sciences
A min-max random game on a graph that is not a tree
In a classical game two players, Alice and Bob, take turns to play $n$ moves each. Alice starts. For each move each player has two options, 1 and 2. The outcome is determined by the exact sequences of moves played by each player. Prior to the game, a winner is assigned to each of the $2^{2n}$ possible outcomes in an i.i.d. fashion, where $p$ is the probability that Bob is the winner for a given outcome. Then it is known that there exists a value $p_c\in (0,1)$ such that the probability that Bob has a winning strategy for large $n$ tends to one if $p>p_c$ and to zero if $p< p_c$. We study a modification of this game for which the outcome is determined by the exact sequence of moves played by Alice as before, but in the case of Bob all that matters is how often he has played move 1. We show that also in this case, there exists a sharp threshold $p'_c$ that determines which player has with large probability a winning strategy in the limit as $n$ tends to infinity. Joint work with Anja Sturm (Göttingen) and Natalia Cardona-Tobón (Bogotá).
