---
_id: '3860'
abstract:
- lang: eng
text: 'In mean-payoff games, the objective of the protagonist is to ensure that
the limit average of an infinite sequence of numeric weights is nonnegative. In
energy games, the objective is to ensure that the running sum of weights is always
nonnegative. Generalized mean-payoff and energy games replace individual weights
by tuples, and the limit average (resp. running sum) of each coordinate must be
(resp. remain) nonnegative. These games have applications in the synthesis of
resource-bounded processes with multiple resources. We prove the finite-memory
determinacy of generalized energy games and show the inter- reducibility of generalized
mean-payoff and energy games for finite-memory strategies. We also improve the
computational complexity for solving both classes of games with finite-memory
strategies: while the previously best known upper bound was EXPSPACE, and no lower
bound was known, we give an optimal coNP-complete bound. For memoryless strategies,
we show that the problem of deciding the existence of a winning strategy for the
protagonist is NP-complete.'
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
citation:
ama: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. Generalized mean-payoff and
energy games. In: Vol 8. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:505-516.
doi:10.4230/LIPIcs.FSTTCS.2010.505'
apa: 'Chatterjee, K., Doyen, L., Henzinger, T. A., & Raskin, J. (2010). Generalized
mean-payoff and energy games (Vol. 8, pp. 505–516). Presented at the FSTTCS: Foundations
of Software Technology and Theoretical Computer Science, Chennai, India: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.505'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Thomas A Henzinger, and Jean Raskin.
“Generalized Mean-Payoff and Energy Games,” 8:505–16. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2010. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.505.
ieee: 'K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin, “Generalized mean-payoff
and energy games,” presented at the FSTTCS: Foundations of Software Technology
and Theoretical Computer Science, Chennai, India, 2010, vol. 8, pp. 505–516.'
ista: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. 2010. Generalized mean-payoff
and energy games. FSTTCS: Foundations of Software Technology and Theoretical Computer
Science, LIPIcs, vol. 8, 505–516.'
mla: Chatterjee, Krishnendu, et al. Generalized Mean-Payoff and Energy Games.
Vol. 8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 505–16, doi:10.4230/LIPIcs.FSTTCS.2010.505.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, J. Raskin, in:, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2010, pp. 505–516.
conference:
end_date: 2010-12-18
location: Chennai, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2010-12-15
date_created: 2018-12-11T12:05:34Z
date_published: 2010-12-13T00:00:00Z
date_updated: 2021-01-12T07:52:44Z
day: '13'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.FSTTCS.2010.505
file:
- access_level: open_access
checksum: 1caabd6319b979927208117a41192637
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:27Z
date_updated: 2020-07-14T12:46:18Z
file_id: '5147'
file_name: IST-2012-59-v1+1_Generalized_mean-payoff_and_energy_games.pdf
file_size: 178278
relation: main_file
- access_level: open_access
checksum: 3a59759ceeacdb5b578f3803d5e6769b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:28Z
date_updated: 2020-07-14T12:46:18Z
file_id: '5148'
file_name: IST-2016-59-v2+1_2_1_.pdf
file_size: 477976
relation: main_file
file_date_updated: 2020-07-14T12:46:18Z
has_accepted_license: '1'
intvolume: ' 8'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 505 - 516
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2321'
pubrep_id: '59'
quality_controlled: '1'
scopus_import: 1
status: public
title: Generalized mean-payoff and energy games
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8
year: '2010'
...