Optimal strategy synthesis for request-response games

DOI10.1007/978-3-540-88387-6_31zbMATH Open1347.68206arXiv1406.4648OpenAlexW2198629034MaRDI QIDQ3465629FDOQ3465629

Wolfgang Thomas, Nico Wallmeier, Martín G. Zimmermann, Florian Horn

Publication date: 22 January 2016

Published in: RAIRO - Theoretical Informatics and Applications, Automated Technology for Verification and Analysis (Search for Journal in Brave)

Abstract: We show the existence and effective computability of optimal winning strategies for request-response games in case the quality of a play is measured by the limit superior of the mean accumulated waiting times between requests and their responses.

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

Recommendations

• Optimal strategy synthesis for request-response games
• Optimizing Winning Strategies in Regular Infinite Games
• The complexity of request-response games
• Time-Optimal Winning Strategies for Poset Games
• On the synthesis of strategies in infinite games

zbMATH Keywords

optimal strategiesmean-payoff gamesrequest-response games

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80) 2-person games (91A05) Games involving graphs (91A43) Games involving topology, set theory, or logic (91A44)

Cites Work

• The complexity of mean payoff games on graphs
• Automata, logics, and infinite games. A guide to current research
• Hybrid Systems: Computation and Control
• Positional strategies for mean payoff games
• On the synthesis of strategies in infinite games
• Parametric temporal logic for “model measuring”
• Solving Sequential Conditions by Finite-State Strategies
• Symbolic Synthesis of Finite-State Controllers for Request-Response Specifications
• Playing infinite games in finite time.
• CONCUR 2005 – Concurrency Theory
• Tools and Algorithms for the Construction and Analysis of Systems
• Faster Algorithms for Finitary Games
• From Liveness to Promptness
• Deterministic Priority Mean-Payoff Games as Limits of Discounted Games
• Mathematical Foundations of Computer Science 2005

Cited In (9)

• Optimizing Winning Strategies in Regular Infinite Games
• Time-Optimal Winning Strategies for Poset Games
• Title not available (Why is that?)
• A delayed promotion policy for parity games
• Multiplayer Cost Games with Simple Nash Equilibria
• Stochastic window mean-payoff games
• Down the Borel hierarchy: solving Muller games via safety games
• On equilibria in quantitative games with reachability/safety objectives
• Title not available (Why is that?)

This page was built for publication: Optimal strategy synthesis for request-response games

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