# Strategy logic

Chatterjee K, Henzinger TA, Piterman N. 2010. Strategy logic. Information and Computation. 208(6), 677–693.

Download
IST-2012-56-v1+1_Strategy_logic.pdf 189.12 KB

Journal Article | Published | English

Scopus indexed
Department
Abstract
We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL*, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula).
Publishing Year
Date Published
2010-06-01
Journal Title
Information and Computation
Volume
208
Issue
6
Page
677 - 693
IST-REx-ID

### Cite this

Chatterjee K, Henzinger TA, Piterman N. Strategy logic. Information and Computation. 2010;208(6):677-693. doi:10.1016/j.ic.2009.07.004
Chatterjee, K., Henzinger, T. A., & Piterman, N. (2010). Strategy logic. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2009.07.004
Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “Strategy Logic.” Information and Computation. Elsevier, 2010. https://doi.org/10.1016/j.ic.2009.07.004.
K. Chatterjee, T. A. Henzinger, and N. Piterman, “Strategy logic,” Information and Computation, vol. 208, no. 6. Elsevier, pp. 677–693, 2010.
Chatterjee K, Henzinger TA, Piterman N. 2010. Strategy logic. Information and Computation. 208(6), 677–693.
Chatterjee, Krishnendu, et al. “Strategy Logic.” Information and Computation, vol. 208, no. 6, Elsevier, 2010, pp. 677–93, doi:10.1016/j.ic.2009.07.004.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
13bff93f3c2a014e2908145a4517f177

Material in ISTA:
Earlier Version

### Export

Marked Publications

Open Data ISTA Research Explorer