Equilibria for Games with Combined Qualitative and Quantitative Objectives
This provides a theoretical foundation for analyzing strategic interactions in systems like autonomous agents or distributed computing, though it is incremental as it builds on existing game theory frameworks.
The paper tackles the problem of determining equilibrium existence in multi-agent systems modeled as concurrent games with combined qualitative and quantitative objectives, showing that deciding strict epsilon Nash equilibrium existence is 2ExpTime-complete and decidable.
The overall aim of our research is to develop techniques to reason about the equilibrium properties of multi-agent systems. We model multi-agent systems as concurrent games, in which each player is a process that is assumed to act independently and strategically in pursuit of personal preferences. In this article, we study these games in the context of finite-memory strategies, and we assume players' preferences are defined by a qualitative and a quantitative objective, which are related by a lexicographic order: a player first prefers to satisfy its qualitative objective (given as a formula of Linear Temporal Logic) and then prefers to minimise costs (given by a mean-payoff function). Our main result is that deciding the existence of a strict epsilon Nash equilibrium in such games is 2ExpTime-complete (and hence decidable), even if players' deviations are implemented as infinite-memory strategies.