Equilibria for games with combined qualitative and quantitative objectives
From MaRDI portal
(Redirected from Publication:824280)
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.
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
Cites work
- scientific article; zbMATH DE number 3835792 (Why is no real title available?)
- scientific article; zbMATH DE number 54099 (Why is no real title available?)
- scientific article; zbMATH DE number 4124989 (Why is no real title available?)
- scientific article; zbMATH DE number 1142326 (Why is no real title available?)
- scientific article; zbMATH DE number 1764950 (Why is no real title available?)
- scientific article; zbMATH DE number 7136658 (Why is no real title available?)
- scientific article; zbMATH DE number 7088727 (Why is no real title available?)
- A course in game theory.
- Alternating-time temporal logic
- Better Quality in Synthesis through Quantitative Objectives
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Depth-First Search and Linear Graph Algorithms
- Energy parity games
- From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
- From model checking to equilibrium checking: reactive modules for rational verification
- How to be both rich and happy: combining quantitative and qualitative strategic reasoning about multi-player games (extended abstract)
- Incentive engineering for Boolean games
- Iterated Boolean games
- Model-checking for resource-bounded ATL with production and consumption of resources
- Multiagent Systems
- On the complexity of planning for agent teams and its implications for single agent planning
- On total functions, existence theorems and computational complexity
- Positional strategies for mean payoff games
- Pure Nash equilibria in concurrent deterministic games
- Rational synthesis
- Secure equilibria in weighted games
- Strategy logic
- Synthesis with rational environments
- Temporal logics in computer science. Finite-state systems
- The Complexity of Nash Equilibria in Limit-Average Games
- The complexity of decision problems about equilibria in two-player Boolean games
- The complexity of mean payoff games on graphs
- The complexity of multi-mean-payoff and multi-energy games
- Understanding and using linear programming
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)
