---
_id: '10904'
abstract:
- lang: eng
  text: Multi-dimensional mean-payoff and energy games provide the mathematical foundation
    for the quantitative study of reactive systems, and play a central role in the
    emerging quantitative theory of verification and synthesis. In this work, we study
    the strategy synthesis problem for games with such multi-dimensional objectives
    along with a parity condition, a canonical way to express ω-regular conditions.
    While in general, the winning strategies in such games may require infinite memory,
    for synthesis the most relevant problem is the construction of a finite-memory
    winning strategy (if one exists). Our main contributions are as follows. First,
    we show a tight exponential bound (matching upper and lower bounds) on the memory
    required for finite-memory winning strategies in both multi-dimensional mean-payoff
    and energy games along with parity objectives. This significantly improves the
    triple exponential upper bound for multi energy games (without parity) that could
    be derived from results in literature for games on VASS (vector addition systems
    with states). Second, we present an optimal symbolic and incremental algorithm
    to compute a finite-memory winning strategy (if one exists) in such games. Finally,
    we give a complete characterization of when finite memory of strategies can be
    traded off for randomness. In particular, we show that for one-dimension mean-payoff
    parity games, randomized memoryless strategies are as powerful as their pure finite-memory
    counterparts.
acknowledgement: 'Author supported by Austrian Science Fund (FWF) Grant No P 23499-N23,
  FWF NFN Grant No S11407 (RiSE), ERC Start Grant (279307: Graph Games), Microsoft
  faculty fellowship.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Mickael
  full_name: Randour, Mickael
  last_name: Randour
- first_name: Jean-François
  full_name: Raskin, Jean-François
  last_name: Raskin
citation:
  ama: 'Chatterjee K, Randour M, Raskin J-F. Strategy synthesis for multi-dimensional
    quantitative objectives. In: Koutny M, Ulidowski I, eds. <i>CONCUR 2012 - Concurrency
    Theory</i>. Vol 7454. Berlin, Heidelberg: Springer; 2012:115-131. doi:<a href="https://doi.org/10.1007/978-3-642-32940-1_10">10.1007/978-3-642-32940-1_10</a>'
  apa: 'Chatterjee, K., Randour, M., &#38; Raskin, J.-F. (2012). Strategy synthesis
    for multi-dimensional quantitative objectives. In M. Koutny &#38; I. Ulidowski
    (Eds.), <i>CONCUR 2012 - Concurrency Theory</i> (Vol. 7454, pp. 115–131). Berlin,
    Heidelberg: Springer. <a href="https://doi.org/10.1007/978-3-642-32940-1_10">https://doi.org/10.1007/978-3-642-32940-1_10</a>'
  chicago: 'Chatterjee, Krishnendu, Mickael Randour, and Jean-François Raskin. “Strategy
    Synthesis for Multi-Dimensional Quantitative Objectives.” In <i>CONCUR 2012 -
    Concurrency Theory</i>, edited by Maciej Koutny and Irek Ulidowski, 7454:115–31.
    Berlin, Heidelberg: Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-32940-1_10">https://doi.org/10.1007/978-3-642-32940-1_10</a>.'
  ieee: K. Chatterjee, M. Randour, and J.-F. Raskin, “Strategy synthesis for multi-dimensional
    quantitative objectives,” in <i>CONCUR 2012 - Concurrency Theory</i>, Newcastle
    upon Tyne, United Kingdom, 2012, vol. 7454, pp. 115–131.
  ista: 'Chatterjee K, Randour M, Raskin J-F. 2012. Strategy synthesis for multi-dimensional
    quantitative objectives. CONCUR 2012 - Concurrency Theory. CONCUR: Conference
    on Concurrency Theory, LNCS, vol. 7454, 115–131.'
  mla: Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative
    Objectives.” <i>CONCUR 2012 - Concurrency Theory</i>, edited by Maciej Koutny
    and Irek Ulidowski, vol. 7454, Springer, 2012, pp. 115–31, doi:<a href="https://doi.org/10.1007/978-3-642-32940-1_10">10.1007/978-3-642-32940-1_10</a>.
  short: K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.),
    CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.
conference:
  end_date: 2012-09-07
  location: Newcastle upon Tyne, United Kingdom
  name: 'CONCUR: Conference on Concurrency Theory'
  start_date: 2012-09-04
date_created: 2022-03-21T08:00:21Z
date_published: 2012-09-15T00:00:00Z
date_updated: 2023-02-23T10:55:06Z
day: '15'
department:
- _id: KrCh
doi: 10.1007/978-3-642-32940-1_10
ec_funded: 1
editor:
- first_name: Maciej
  full_name: Koutny, Maciej
  last_name: Koutny
- first_name: Irek
  full_name: Ulidowski, Irek
  last_name: Ulidowski
external_id:
  arxiv:
  - '1201.5073'
intvolume: '      7454'
language:
- iso: eng
month: '09'
oa_version: Preprint
page: 115-131
place: Berlin, Heidelberg
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: CONCUR 2012 - Concurrency Theory
publication_identifier:
  eisbn:
  - '9783642329401'
  isbn:
  - '9783642329395'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
  record:
  - id: '2716'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Strategy synthesis for multi-dimensional quantitative objectives
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7454
year: '2012'
...