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;]

---

Life is Random, Time is Not: Markov Decision Processes with Window Objectives

Thomas Brihaye ; Florent Delgrange ; Youssouf Oualhadj ; Mickael Randour.

The window mechanism was introduced by Chatterjee et al. to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time frame, all along their infinite execution, in contrast to the traditional&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;]

---

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;]

---