Conference item
Characterising and verifying the core in concurrent multi-player mean-payoff games
- Abstract:
- Concurrent multi-player mean-payoff games are important models for systems of agents with individual, non-dichotomous preferences. Whilst these games have been extensively studied in terms of their equilibria in non-cooperative settings, this paper explores an alternative solution concept: the core from cooperative game theory. This concept is particularly relevant for cooperative AI systems, as it enables the modelling of cooperation among agents, even when their goals are not fully aligned. Our contribution is twofold. First, we provide a characterisation of the core using discrete geometry techniques and establish a necessary and sufficient condition for its non-emptiness. We then use the characterisation to prove the existence of polynomial witnesses in the core. Second, we use the existence of such witnesses to solve key decision problems in rational verification and provide tight complexity bounds for the problem of checking whether some/every equilibrium in a game satisfies a given LTL or GR(1) specification. Our approach is general and can be adapted to handle other specifications expressed in various fragments of LTL without incurring additional computational costs.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 997.3KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.CSL.2024.32
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
- Pages:
- 32:1-32:25
- Series:
- Leibniz International Proceedings in Informatics (LIPIcs)
- Series number:
- 288
- Publication date:
- 2024-02-01
- Event title:
- 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
- Event location:
- Naples, Italy
- Event website:
- https://csl2024.github.io/Home/
- Event start date:
- 2026-02-19
- Event end date:
- 2026-02-23
- DOI:
- ISSN:
-
1868-8969
- Language:
-
English
- Keywords:
- Pubs id:
-
1713179
- Local pid:
-
pubs:1713179
- Deposit date:
-
2025-04-17
- ARK identifier:
Terms of use
- Copyright holder:
- Gutierrez et al
- Copyright date:
- 2024
- Rights statement:
- © Julian Gutierrez, Anthony W. Lin, Muhammad Najib, Thomas Steeples, and Michael Wooldridge; licensed under Creative Commons License CC-BY 4.0
- Notes:
- This conference paper was presented at the 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), 19th-23rd February 2024, Naples, Italy.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record