Search

• < Previous
• 1
• Next >

---

Arena-Independent Finite-Memory Determinacy in Stochastic Games

Patricia Bouyer ; Youssouf Oualhadj ; Mickael Randour ; Pierre Vandenhove.

We study stochastic zero-sum games on graphs, which are prevalent tools to model decision-making in presence of an antagonistic opponent in a random environment. In this setting, an important question is the one of strategy complexity: what kinds of strategies are sufficient or required to play&nbsp;[&hellip;]

---

Half-Positional Objectives Recognized by Deterministic B\"uchi Automata

Patricia Bouyer ; Antonio Casares ; Mickael Randour ; Pierre Vandenhove.

In two-player games on graphs, the simplest possible strategies are those that can be implemented without any memory. These are called positional strategies. In this paper, we characterize objectives recognizable by deterministic B\"uchi automata (a subclass of omega-regular objectives) that are&nbsp;[&hellip;]

---

Games Where You Can Play Optimally with Arena-Independent Finite Memory

Patricia Bouyer ; Stéphane Le Roux ; Youssouf Oualhadj ; Mickael Randour ; Pierre Vandenhove.

For decades, two-player (antagonistic) games on graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one is controller synthesis, which can be rephrased through the game-theoretic metaphor as the quest for a winning strategy of the system in&nbsp;[&hellip;]

---