Graded modalities in Strategy Logic.

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 ( Graded SL), an extension of SL by graded quantifiers over tuples of strategy variables, i.e., “there exist at least g different tuples ( x 1 , . . . , x n ) of strategies” where g is a cardinal from the set N ∪ { ℵ 0 , ℵ 1 , 2 ℵ 0 } . We prove that the model-checking problem of Graded SL is decidable. We then turn to the complexity of fragments of Graded SL. When the g 's are restricted to finite cardinals, written Graded N SL, 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 2 ExpTime , which is not harder than merely checking for the existence of such an equilibrium. [ABSTRACT FROM AUTHOR]