Equilibria for games with combined qualitative and quantitative objectives

DOI10.1007/S00236-020-00385-4zbMATH Open1483.68193arXiv2008.05643OpenAlexW3034407568MaRDI QIDQ824280FDOQ824280

Authors: Julian Gutiérrez, Aniello Murano, Giuseppe Perelli, Sasha Rubin, Thomas Steeples, M. J. Wooldridge 

Publication date: 15 December 2021

Published in: Acta Informatica (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/2008.05643

Recommendations

• On equilibria in quantitative games with reachability/safety objectives
• Equilibria in quantitative reachability games
• Reasoning about equilibria in game-like concurrent systems
• The complexity of Nash equilibria in stochastic multiplayer games
• Nash equilibria in concurrent games with Büchi objectives

Mathematics Subject Classification ID

Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60) Agent technology and artificial intelligence (68T42) Temporal logic (03B44)

Cites Work

• The complexity of mean payoff games on graphs
• Title not available (Why is that?)
• Alternating-time temporal logic
• Depth-First Search and Linear Graph Algorithms
• A course in game theory.
• Multiagent Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Positional strategies for mean payoff games
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Better Quality in Synthesis through Quantitative Objectives
• The complexity of decision problems about equilibria in two-player Boolean games
• Incentive engineering for Boolean games
• On total functions, existence theorems and computational complexity
• Pure Nash equilibria in concurrent deterministic games
• Synthesis with rational environments
• Rational synthesis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Understanding and using linear programming
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• Iterated Boolean games
• The Complexity of Nash Equilibria in Limit-Average Games
• Strategy logic
• Secure equilibria in weighted games
• Energy parity games
• Title not available (Why is that?)
• Model-checking for resource-bounded ATL with production and consumption of resources
• How to be both rich and happy: combining quantitative and qualitative strategic reasoning about multi-player games (extended abstract)
• The complexity of multi-mean-payoff and multi-energy games
• From model checking to equilibrium checking: reactive modules for rational verification
• On the complexity of planning for agent teams and its implications for single agent planning
• Temporal logics in computer science. Finite-state systems
• Title not available (Why is that?)

Cited In (9)

• Multi-player games with LDL goals over finite traces
• How to be both rich and happy: combining quantitative and qualitative strategic reasoning about multi-player games (extended abstract)
• Incentive Engineering for Concurrent Games
• Quantitative games with interval objectives
• On equilibria in quantitative games with reachability/safety objectives
• Reasoning about equilibria in game-like concurrent systems
• Mean-payoff games with \(\omega\)-regular specifications
• A characterization of mixed-strategy Nash equilibria in PCTL augmented with a cost quantifier
• Existence and verification of Nash equilibria in non-cooperative contribution games with resource contention

This page was built for publication: Equilibria for games with combined qualitative and quantitative objectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q824280)