Search

• < Previous
• 1
• Next >

---

On (Subgame Perfect) Secure Equilibrium in Quantitative Reachability Games

Thomas Brihaye ; Véronique Bruyère ; Julie De Pril ; Hugo Gimbert.

We study turn-based quantitative multiplayer non zero-sum games played on finite graphs with reachability objectives. In such games, each player aims at reaching his own goal set of states as soon as possible. A previous work on this model showed that Nash equilibria (resp. secure equilibria) are&nbsp;[&hellip;]

---

Solving Simple Stochastic Games with Few Random Vertices

Hugo Gimbert ; Florian Horn.

Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the existence of optimal permutation strategies, a&nbsp;[&hellip;]

---

Deciding the value 1 problem for probabilistic leaktight automata

Nathanaël Fijalkow ; Hugo Gimbert ; Edon Kelmendi ; Youssouf Oualhadj.

The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1? This problem was proved undecidable recently; to overcome this, several classes of probabilistic automata of&nbsp;[&hellip;]

---

Controlling a population

Nathalie Bertrand ; Miheer Dewaskar ; Blaise Genest ; Hugo Gimbert ; Adwait Amit Godbole.

We introduce a new setting where a population of agents, each modelled by a finite-state system, are controlled uniformly: the controller applies the same action to every agent. The framework is largely inspired by the control of a biological system, namely a population of yeasts, where the&nbsp;[&hellip;]

---

Distributed Asynchronous Games With Causal Memory are Undecidable

Hugo Gimbert.

We show the undecidability of the distributed control problem when the plant is an asynchronous automaton, the controllers use causal memory and the goal of the controllers is to put each process in a local accepting state.

---