Equilibria for games with combined qualitative and quantitative objectives

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

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

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 ϵ Nash equilibrium in such games is 2ExpTime-complete (and hence decidable), even if players’ deviations are implemented as infinite-memory strategies.

Original languageEnglish
Number of pages26
JournalActa Informatica
Volume2020
DOIs
Publication statusPublished - 13 Jun 2020

Cite this