Computer aided synthesis: a game-theoretic approach

DOI10.1007/978-3-319-62809-7_1MaRDI QIDQ2408790zbMATH OpenOpenAlexFDO

Authors Véronique Bruyère

Publication date 13 October 2017

Full work available at URL https://arxiv.org/abs/1706.00652

zbMATH Keywords

Boolean objectivegames played on graphsNash equilibriumquantitative objectivesynthesiswinning strategy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Games involving graphs (91A43) Applications of game theory (91A80)

Abstract: In this invited contribution, we propose a comprehensive introduction to game theory applied in computer aided synthesis. In this context, we give some classical results on two-player zero-sum games and then on multi-player non zero-sum games. The simple case of one-player games is strongly related to automata theory on infinite words. All along the article, we focus on general approaches to solve the studied problems, and we provide several illustrative examples as well as intuitions on the proofs.

Recommendations

• Non-zero sum games for reactive synthesis
• Graph Games and Reactive Synthesis
• On the synthesis of strategies in infinite games
• Automata and games for synthesis
• The complexity of rational synthesis for concurrent games

Cited in

(24)

• Simplifying optimal strategies in \(\limsup\) and \(\liminf\) stochastic games
• On subgame perfect equilibria in turn-based reachability timed games
• Perfect information games where each player acts only once
• Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives
• Subgame perfection in recursive perfect information games
• Subgame maxmin strategies in zero-sum stochastic games with tolerance levels
• A game-theoretic approach for the synthesis of complex systems
• Individual upper semicontinuity and subgame perfect \(\epsilon\)-equilibria in games with almost perfect information
• Reachability and safety objectives in Markov decision processes on long but finite horizons
• On the existence of weak subgame perfect equilibria
• Using the compatibility analysis of logical specifications of automata to solve game problems
• Non-zero sum games for reactive synthesis
• Constrained existence problem for weak subgame perfect equilibria with -regular Boolean objectives
• The complexity of subgame perfect equilibria in quantitative reachability games
• scientific article; zbMATH DE number 7649921 (Why is no real title available?)
• Energy mean-payoff games
• Subgame-perfect Equilibria in Mean-payoff Games (journal version)
• Stackelberg-Pareto synthesis
• A game-theoretic approach to indistinguishability of winning objectives as user privacy
• Arena-independent memory bounds for Nash equilibria in reachability games
• Arena-independent memory bounds for Nash equilibria in reachability games
• Regularity of the minmax value and equilibria in multiplayer Blackwell games
• Games with -automatic preference relations
• The non-cooperative rational synthesis problem for SPEs and -regular objectives

This page was built for publication: Computer aided synthesis: a game-theoretic approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408790)