Home » Publication » 23005

Dettaglio pubblicazione

2020, ACTA INFORMATICA, Pages -

Equilibria for Games with Combined Qualitative and Quantitative Objects (01a Articolo in rivista)

Gutierrez Juilan, Murano Aniello, Perelli Giuseppe, Rubin Sasha, Steeples Thomas, Wooldridge Michael

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.
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma