8 papers
The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and omega-regular Objectives
Véronique Bruyère, Jean-François Raskin, Alexis Reynouard +1
This paper studies the rational synthesis problem for multi-player games played on graphs when rational players are following subgame perfect equilibria. In these games, one player…
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…
Hierarchical Information and the Synthesis of Distributed Strategies
Dietmar Berwanger, Anup Basil Mathew, Marie van den Bogaard
Infinite games with imperfect information are known to be undecidable unless the information flow is severely restricted. One fundamental decidable case occurs when there is a tota…
Consensus Game Acceptors and Iterated Transductions
Dietmar Berwanger, Marie van den Bogaard
We study a game for recognising formal languages, in which two players with imperfect information need to coordinate on a common decision, given private input words correlated by a…