Title: Graded modalities in Strategy Logic
Language: English
Authors: Aminof, Benjamin
Malvone, Vadim 
Murano, Aniello
Rubin, Sasha
Category: Research Article
Forschungsartikel
Keywords: Strategic logics; Graded modalities; Nash equilibria
Issue Date: 2018
Journal: Information and Computation
Abstract: 
Strategy Logic (SL) is a logical formalism for strategic reasoning in multi-agent systems. Its main feature is that it has variables for strategies that are associated to specific agents using a binding operator. In this paper we introduce Graded Strategy Logic (GradedSL), an extension of SL by graded quantifiers over tuples of strategy variables, i.e., “there exist at least g different tuples (x1,...,xn) of strategies” where g is a cardinal from the set N∪{ℵ0,ℵ1,2ℵ0}. We prove that the model-checking problem of GradedSL is decidable. We then turn to the complexity of fragments of GradedSL. When the g's are restricted to finite cardinals, written GradedNSL, the complexity of model-checking is no harder than for SL, i.e., it is non-elementary in the quantifier-block rank. We illustrate our formalism by showing how to count the number of different strategy profiles that are Nash equilibria (NE). By analysing the structure of the specific formulas involved, we conclude that the important problem of checking for the existence of a unique NE can be solved in 2ExpTime, which is not harder than merely checking for the existence of such an equilibrium.
DOI: 10.1016/j.ic.2018.02.022
Library ID: AC15150648
URN: urn:nbn:at:at-ubtuw:3-3817
ISSN: 0890-5401
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Article
Artikel
Appears in Collections:Article

Files in this item:

File Description SizeFormat
Graded modalities in Strategy Logic.pdf485 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

120
checked on Feb 26, 2021

Download(s)

153
checked on Feb 26, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.