5 papers
Bounds for Synchronizing Markov Decision Processes
Laurent Doyen, Marie van den Bogaard
We consider Markov decision processes with synchronizing objectives, which require that a probability mass of accumulates in a designated set of target states, either once, a…
The Complexity of SPEs in Mean-payoff Games
Léonard Brice, Jean-François Raskin, Marie van den Bogaard
We establish that the subgame perfect equilibrium (SPE) threshold problem for mean-payoff games is NP-complete. While the SPE threshold problem was recently shown to be decidable (…
The Impatient May Use Limited Optimism to Minimize Regret
Michaël Cadilhac, Guillermo A. Pérez, Marie van den Bogaard
Discounted-sum games provide a formal model for the study of reinforcement learning, where the agent is enticed to get rewards early since later rewards are discounted. When the ag…
Beyond admissibility: Dominance between chains of strategies
Nicolas Basset, Ismaël Jecker, Arno Pauly +2
Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by resul…
Games with Delays. A Frankenstein Approach
Dietmar Berwanger, Marie van den Bogaard
We investigate infinite games on finite graphs where the information flow is perturbed by nondeterministic signalling delays. It is known that such perturbations make synthesis pro…