Obliging games

K. Chatterjee, F. Horn, C. Löding, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 284–296.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
Graph games of infinite length provide a natural model for open reactive systems: one player (Eve) represents the controller and the other player (Adam) represents the environment. The evolution of the system depends on the decisions of both players. The specification for the system is usually given as an ω-regular language L over paths and Eve’s goal is to ensure that the play belongs to L irrespective of Adam’s behaviour. The classical notion of winning strategies fails to capture several interesting scenarios. For example, strong fairness (Streett) conditions are specified by a number of request-grant pairs and require every pair that is requested infinitely often to be granted infinitely often: Eve might win just by preventing Adam from making any new request, but a “better” strategy would allow Adam to make as many requests as possible and still ensure fairness. To address such questions, we introduce the notion of obliging games, where Eve has to ensure a strong condition Φ, while always allowing Adam to satisfy a weak condition Ψ. We present a linear time reduction of obliging games with two Muller conditions Φ and Ψ to classical Muller games. We consider obliging Streett games and show they are co-NP complete, and show a natural quantitative optimisation problem for obliging Streett games is in FNP. We also show how obliging games can provide new and interesting semantics for multi-player games.
Publishing Year
Date Published
2010-09-08
Volume
6269
Page
284 - 296
Conference
CONCUR: Concurrency Theory
Conference Location
Paris, France
Conference Date
2010-08-31 – 2010-09-03
IST-REx-ID

Cite this

Chatterjee K, Horn F, Löding C. Obliging games. In: Vol 6269. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:284-296. doi:10.1007/978-3-642-15375-4_20
Chatterjee, K., Horn, F., & Löding, C. (2010). Obliging games (Vol. 6269, pp. 284–296). Presented at the CONCUR: Concurrency Theory, Paris, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-642-15375-4_20
Chatterjee, Krishnendu, Florian Horn, and Christof Löding. “Obliging Games,” 6269:284–96. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.1007/978-3-642-15375-4_20.
K. Chatterjee, F. Horn, and C. Löding, “Obliging games,” presented at the CONCUR: Concurrency Theory, Paris, France, 2010, vol. 6269, pp. 284–296.
Chatterjee K, Horn F, Löding C. 2010. Obliging games. CONCUR: Concurrency Theory, LNCS, vol. 6269. 284–296.
Chatterjee, Krishnendu, et al. Obliging Games. Vol. 6269, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 284–96, doi:10.1007/978-3-642-15375-4_20.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar