2020/08/12 by Julián Gutiérrez, Aniello Murano, Gutierrez, Julian +9
Computer Science · Economics, Econometrics and Finance · #Logic, Reasoning, and Knowledge #Game Theory and Voting Systems #Advanced Algebra and Logic
paper · pdf · doi:10.48550/arxiv.2008.05643
The overall aim of our research is to develop techniques to reason about the\nequilibrium properties of multi-agent systems. We model multi-agent systems as\nconcurrent games, in which each player is a process that is assumed to act\nindependently and strategically in pursuit of personal preferences. In this\narticle, we study these games in the context of finite-memory strategies, and\nwe assume players' preferences are defined by a qualitative and a quantitative\nobjective, which are related by a lexicographic order: a player first prefers\nto satisfy its qualitative objective (given as a formula of Linear Temporal\nLogic) and then prefers to minimise costs (given by a mean-payoff function).\nOur main result is that deciding the existence of a strict epsilon Nash\nequilibrium in such games is 2ExpTime-complete (and hence decidable), even if\nplayers' deviations are implemented as infinite-memory strategies.\n