2019 · 21 citations · 29 references
ComputingComputer ScienceMathematicsFormal MethodsLogicProbability TheoryModel CheckingNash EquilibriumStochastic GamesTemporal LogicExponential SpaceFragment ExtensionNash Equilibrium ComputationNash Equilibrium ProblemsProbabilistic ComputationProbabilistic LogicProbabilistic Model Checking
We introduce Probabilistic Strategy Logic, an extension of Strategy Logic for stochastic systems. The logic has probabilistic terms that allow it to express many standard solution concepts, such as Nash equilibria in randomised strategies, as well as constraints on probabilities, such as independence. We study the model-checking problem for agents with perfect- and imperfect-recall. The former is undecidable, while the latter is decidable in space exponential in the system and triple-exponential in the formula. We identify a natural fragment of the logic, in which every temporal operator is immediately preceded by a probabilistic operator, and show that it is decidable in space exponential in the system and the formula, and double-exponential in the nesting depth of the probabilistic terms. Taking a fixed nesting depth, this gives a fragment that still captures many standard solution concepts, and is decidable in exponential space.
29
Artificial intelligence: A modern approach
Nils J. Nilsson · Artificial Intelligence · 1996 · 10.7K citations
The temporal logic of programs
Amir Pnueli · 1977 · 5.7K citations
Mathematical Social Sciences · 1994 · 3.6K citations
Alternating-time temporal logic
Rajeev Alur, Thomas A. Henzinger, Orna Kupferman · Journal of the ACM · 2002 · 1.4K citations
Automatic verification of probabilistic concurrent finite state programs
Moshe Y. Vardi · 1985 · 675 citations