On computational tractability for rational verification

Julian Gutierrez, Muhammad Najib, Giuseppe Perelli, Michael Wooldridge

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)

Abstract

Rational verification involves checking which temporal logic properties hold of a concurrent/multiagent system, under the assumption that agents in the system choose strategies in game theoretic equilibrium. Rational verification can be understood as a counterpart of model checking for multiagent systems, but while model checking can be done in polynomial time for some temporal logic specification languages such as CTL, and polynomial space with LTL specifications, rational verification is much more intractable: 2EXPTIME-complete with LTL specifications, even when using explicit-state system representations. In this paper we show that the complexity of rational verification can be greatly reduced by restricting specifications to GR(1), a fragment of LTL that can represent most response properties of reactive systems. We also provide improved complexity results for rational verification when considering players' goals given by mean-payoff utility functions-arguably the most widely used quantitative objective for agents in concurrent and multiagent systems. In particular, we show that for a number of relevant settings, rational verification can be done in polynomial space or even in polynomial time.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)
EditorsSarit Kraus
PublisherIJCAI
Pages329-335
Number of pages7
ISBN (Electronic)9780999241141
DOIs
Publication statusPublished - 2019
Event28th International Joint Conference on Artificial Intelligence 2019 - Macao, China
Duration: 10 Aug 201916 Aug 2019
https://ijcai19.org/

Conference

Conference28th International Joint Conference on Artificial Intelligence 2019
Abbreviated titleIJCAI 2019
Country/TerritoryChina
CityMacao
Period10/08/1916/08/19
Internet address

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'On computational tractability for rational verification'. Together they form a unique fingerprint.

Cite this