---
_id: '3854'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Florian
  full_name: Horn, Florian
  id: 37327ACE-F248-11E8-B48F-1D18A9856A87
  last_name: Horn
- first_name: Christof
  full_name: Löding, Christof
  last_name: Löding
citation:
  ama: 'Chatterjee K, Horn F, Löding C. Obliging games. In: Vol 6269. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2010:284-296. doi:<a href="https://doi.org/10.1007/978-3-642-15375-4_20">10.1007/978-3-642-15375-4_20</a>'
  apa: 'Chatterjee, K., Horn, F., &#38; 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. <a href="https://doi.org/10.1007/978-3-642-15375-4_20">https://doi.org/10.1007/978-3-642-15375-4_20</a>'
  chicago: Chatterjee, Krishnendu, Florian Horn, and Christof Löding. “Obliging Games,”
    6269:284–96. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. <a href="https://doi.org/10.1007/978-3-642-15375-4_20">https://doi.org/10.1007/978-3-642-15375-4_20</a>.
  ieee: 'K. Chatterjee, F. Horn, and C. Löding, “Obliging games,” presented at the
    CONCUR: Concurrency Theory, Paris, France, 2010, vol. 6269, pp. 284–296.'
  ista: 'Chatterjee K, Horn F, Löding C. 2010. Obliging games. CONCUR: Concurrency
    Theory, LNCS, vol. 6269, 284–296.'
  mla: Chatterjee, Krishnendu, et al. <i>Obliging Games</i>. Vol. 6269, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2010, pp. 284–96, doi:<a href="https://doi.org/10.1007/978-3-642-15375-4_20">10.1007/978-3-642-15375-4_20</a>.
  short: K. Chatterjee, F. Horn, C. Löding, in:, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2010, pp. 284–296.
conference:
  end_date: 2010-09-03
  location: Paris, France
  name: 'CONCUR: Concurrency Theory'
  start_date: 2010-08-31
corr_author: '1'
date_created: 2018-12-11T12:05:32Z
date_published: 2010-09-08T00:00:00Z
date_updated: 2024-10-09T20:54:07Z
day: '08'
department:
- _id: KrCh
doi: 10.1007/978-3-642-15375-4_20
intvolume: '      6269'
language:
- iso: eng
month: '09'
oa_version: None
page: 284 - 296
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2327'
quality_controlled: '1'
scopus_import: 1
status: public
title: Obliging games
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6269
year: '2010'
...