Mean-Payoff Games with ω -Regular Specifications

Julian Gutierrez, Thomas Steeples and Michael Wooldridge
Additional contact information
Julian Gutierrez: Monash Department of Data Science & AI, Monash Data Futures Institute, Green Chemical Futures Building, 13 Rainforest Walk, Monash University, Clayton, VIC 3800, Australia
Thomas Steeples: Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
Michael Wooldridge: Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK

Games, 2022, vol. 13, issue 1, 1-37

Abstract: 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.

Keywords: multi-player games; mean-payoff games; automated verification; temporal logic; game theory; equilibria; multi-agent systems (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/13/1/19/pdf (application/pdf)
https://www.mdpi.com/2073-4336/13/1/19/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:13:y:2022:i:1:p:19-:d:745650

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().