Multi-player games with LDL goals over finite traces
Lists
Only you see this
Abstract
Linear Dynamic Logic on finite traces (LDLF)<math><mo stretchy="false" is="true">(</mo><msub is="true"><mrow is="true"><mi mathvariant="normal" is="true">LDL</mi></mrow><mrow is="true"><mi mathvariant="normal" is="true">F</mi></mrow></msub><mo stretchy="false" is="true">)</mo></math> is a powerful logic for reasoning about the behaviour of concurrent and multi-agent systems. In this paper, we investigate techniques for both the characterisation and verification of equilibria in multi-player games with goals/objectives expressed using logics based on LDLF<math><msub is="true"><mrow is="true"><mi mathvariant="normal" is="true">LDL</mi></mrow><mrow is="true"><mi mathvariant="normal" is="true">F</mi></mrow></msub></math>. This study builds upon a generalisation of Boolean games, a logic-based game model of multi-agent systems where players have goals succinctly represented in a logical way. Because LDLF<math><msub is="true"><mrow is="true"><mi mathvariant="normal" is="true">LDL</mi></mrow><mrow is="true"><mi mathvariant="normal" is="true">F</mi></mrow></msub></math> goals are considered, in the settings we study—Reactive Modules games and iterated Boolean games with goals over finite traces—players' goals can be defined to be regular properties while achieved in a finite, but arbitrarily large, trace. In particular, using alternating automata, the paper investigates automata-theoretic approaches to the characterisation and verification of (pure strategy Nash) equilibria, shows that the set of Nash equilibria in multi-player games with LDLF<math><msub is="true"><mrow is="true"><mi mathvariant="normal" is="true">LDL</mi></mrow><mrow is="true"><mi mathvariant="normal" is="true">F</mi></mrow></msub></math> objectives is regular, and provides complexity results for the associated automata constructions.
BibTeX
@article{gutierrez2021multi,
author = {Julian Gutierrez and Giuseppe Perelli and Michael J. Wooldridge},
title = {{Multi-player games with LDL goals over finite traces}},
journal = {Inf. Comput.},
year = {2021},
doi = {10.1016/j.ic.2020.104555},
}