Characterization, verification and generation of strategies in games with resource constraints. (June 2022) - Liu, Chanjuan; Zhu, Enqiang; Zhang, Yuanke; Zhang, Qiang; Wei, Xiaopeng
Abstract: With an increasing demand for ensuring the reliability and efficiency of distributed and interactive systems, the model-checking technique has been studied extensively, for which a game-based modeling of the system and a logical specification of the desired properties are two essential parts. Existing studies mainly focused on ideal systems that always guarantee optimal responses and have not considered several realistic aspects, for instance, the fact that actions can only be performed under sufficient resources. In this paper, we propose a game model with resource constraints and thereby a novel logic named LRC for such games. This logic enables the strategic reasoning of the likely strategies of the other participating entities and thus supports not only the characterization of the equilibrium of games with limited resources, but also strategic exploitation in multi-agent systems in which the available resources are restricted. Interesting properties of this logic are investigated, and a model-checking algorithm is presented. Being built upon the alternating-time temporal logic (ATL), LRC is shown to be more expressive than ATL without bringing additional complexity. In addition to determining the existence or absence of a collaborative strategy, we explore the generation of the team plan when a certain protocol is supposed to be followed.