Abstract
An energy game is played between two players, modeling a resourcebounded system and its environment. The players take turns moving a token along a finite graph. Each edge of the graph is labeled by an integer, describing an update to the energy level of the system that occurs whenever the edge is traversed. The system wins the game if it never runs out of energy. Different applications have led to extensions of the above basic setting. For example, addressing a combination of the energy requirement with behavioral specifications, researchers have studied richer winning conditions, and addressing systems with several bounded resources, researchers have studied games with multidimensional energy updates. All extensions, however, assume that the environment has no bounded resources.
We introduce and study bothbounded energy games (BBEGs), in which both the system and the environment have multidimensional energy bounds. In BBEGs, each edge in the game graph is labeled by two integer vectors, describing updates to the multidimensional energy levels of the system and the environment. A system wins a BBEG if it never runs out of energy or if its environment runs out of energy. We show that BBEGs are determined, and that the problem of determining the winner in a given BBEG is decidable iff both the system and the environment have energy vectors of dimension 1. We also study how restrictions on the memory of the system and/or the environment as well as upper bounds on their energy levels influence the winner and the complexity of the problem.
BibTeX  Entry
@InProceedings{kupferman_et_al:LIPIcs.CONCUR.2022.19,
author = {Kupferman, Orna and Shamash Halevy, Naama},
title = {{Energy Games with ResourceBounded Environments}},
booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)},
pages = {19:119:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772464},
ISSN = {18688969},
year = {2022},
volume = {243},
editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17082},
URN = {urn:nbn:de:0030drops170823},
doi = {10.4230/LIPIcs.CONCUR.2022.19},
annote = {Keywords: Energy Games, InfiniteState Systems, Decidability}
}
Keywords: 

Energy Games, InfiniteState Systems, Decidability 
Collection: 

33rd International Conference on Concurrency Theory (CONCUR 2022) 
Issue Date: 

2022 
Date of publication: 

06.09.2022 