Artikel
Mean-payoff games with ω-regular specifications
Multi-player mean-payoff games are a natural formalism for modelling the behaviour of concurrent and multi-agent systems with self-interested players. Players in such a game traverse a graph, while attempting to maximise a (mean-)payoff function that depends on the play generated. As with all games, the equilibria that could arise may have undesirable properties. However, as system designers, we typically wish to ensure that equilibria in such systems correspond to desirable system behaviours, for example, satisfying certain safety or liveness properties. One natural way to do this would be to specify such desirable properties using temporal logic. Unfortunately, the use of temporal logic specifications causes game theoretic verification problems to have very high computational complexity. To address this issue, we consider ω-regular specifications. These offer a concise and intuitive way of specifying system behaviours with a comparatively low computational overhead. The main results of this work are characterisation and complexity bounds for the problem of determining if there are equilibria that satisfy a given ω-regular specification in a multi-player mean-payoff game in a number of computationally relevant game-theoretic settings.
- Sprache
-
Englisch
- Erschienen in
-
Journal: Games ; ISSN: 2073-4336 ; Volume: 13 ; Year: 2022 ; Issue: 1 ; Pages: 1-37 ; Basel: MDPI
- Klassifikation
-
Wirtschaft
- Thema
-
automated verification
equilibria
game theory
mean-payoff games
multi-agent systems
multi-player games
temporal logic
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Gutierrez, Julian
Steeples, Thomas
Wooldridge, Michael J.
- Ereignis
-
Veröffentlichung
- (wer)
-
MDPI
- (wo)
-
Basel
- (wann)
-
2022
- DOI
-
doi:10.3390/g13010019
- Handle
- Letzte Aktualisierung
-
10.03.2025, 11:43 MEZ
Datenpartner
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Artikel
Beteiligte
- Gutierrez, Julian
- Steeples, Thomas
- Wooldridge, Michael J.
- MDPI
Entstanden
- 2022
Ähnliche Objekte (12)
Solving Mean-Payoff Games via Quasi Dominions
Tropical convexity, mean payoff games and nonarchimedean convex programming
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games
Conflict games with payoff uncertainty
Payoff Continuity in Incomplete Information Games
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions
Pure Saddle Points and Symmetric Relative Payoff Games
Pure saddle points and symmetric relative payoff games
Pure Saddle Points and Symmetric Relative Payoff Games
When is the individually rational payoff in a repeated game equal to the minmax payoff?
The maximal payoff and coalition formation in coalitional games
Solving Mean-Payoff Games via Quasi Dominions
Tropical convexity, mean payoff games and nonarchimedean convex programming
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games
Conflict games with payoff uncertainty
Payoff Continuity in Incomplete Information Games
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions
Pure Saddle Points and Symmetric Relative Payoff Games
Pure saddle points and symmetric relative payoff games
Pure Saddle Points and Symmetric Relative Payoff Games
When is the individually rational payoff in a repeated game equal to the minmax payoff?
The maximal payoff and coalition formation in coalitional games
Solving Mean-Payoff Games via Quasi Dominions
Tropical convexity, mean payoff games and nonarchimedean convex programming
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games
Conflict games with payoff uncertainty
Payoff Continuity in Incomplete Information Games
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions
Pure Saddle Points and Symmetric Relative Payoff Games
Pure saddle points and symmetric relative payoff games
Pure Saddle Points and Symmetric Relative Payoff Games
When is the individually rational payoff in a repeated game equal to the minmax payoff?