{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T10:27:19Z","timestamp":1759400839433},"reference-count":62,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2021,5,17]],"date-time":"2021-05-17T00:00:00Z","timestamp":1621209600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,10,22]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The article compares two different approaches of incorporating probability into coalition logics. One is based on the semantics of games with stochastic transitions and the other on games with the stochastic failures. The work gives an example of a non-trivial property of coalition power for the first approach and a complete axiomatization for the second approach. It turns out that the logical properties of the coalition power modality under the second approach depend on whether the modal language allows the empty coalition. The main technical results for the games with stochastic failures are a strong completeness theorem for the logical system without the empty coalition and an incompleteness theorem which shows that there is no strongly complete logical system in the language with the empty coalition.<\/jats:p>","DOI":"10.1093\/logcom\/exab032","type":"journal-article","created":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T18:42:46Z","timestamp":1618339366000},"page":"1845-1867","source":"Crossref","is-referenced-by-count":1,"title":["Strategic coalitions in stochastic games"],"prefix":"10.1093","volume":"31","author":[{"given":"Pavel","family":"Naumov","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, King\u2019s College, Wilkes-Barre, PA 18711, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Ros","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,5,17]]},"reference":[{"key":"2021102214140048300_ref1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1994.1049","article-title":"Decidability and expressiveness for first-order logics of probability","volume":"112","author":"Abadi","year":"1994","journal-title":"Information and Computation"},{"key":"2021102214140048300_ref2","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1093\/logcom\/exv085","article-title":"Coalition logic with individual, distributed and common knowledge","volume":"29","author":"Agotnes","year":"2019","journal-title":"Journal of Logic and Computation"},{"key":"2021102214140048300_ref3","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.jal.2008.12.002","article-title":"Group announcement logic","volume":"8","author":"Agotnes","year":"2010","journal-title":"Journal of Applied Logic"},{"key":"2021102214140048300_ref4","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.artint.2008.08.004","article-title":"Reasoning about coalitional games","volume":"173","author":"Agotnes","year":"2009","journal-title":"Artificial Intelligence"},{"key":"2021102214140048300_ref5","first-page":"673","article-title":"Coalitions and announcements","volume-title":"Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems","author":"Agotnes","year":"2008"},{"key":"2021102214140048300_ref6","first-page":"1847","article-title":"Resource logics with a diminishing resource","volume-title":"Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems","author":"Alechina","year":"2018"},{"key":"2021102214140048300_ref7","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.jcss.2017.03.008","article-title":"Model-checking for resource-bounded ATL with production and consumption of resources","volume":"88","author":"Alechina","year":"2017","journal-title":"Journal of Computer and System Sciences"},{"key":"2021102214140048300_ref8","first-page":"1809","article-title":"Symbolic model-checking for resource-bounded ATL","volume-title":"Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems","author":"Alechina","year":"2015"},{"key":"2021102214140048300_ref9","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1093\/logcom\/exq032","article-title":"Logic for coalitions with bounded resources","volume":"21","author":"Alechina","year":"2011","journal-title":"Journal of Logic and Computation"},{"key":"2021102214140048300_ref10","volume-title":"Probability: A Graduate Course","author":"Allan","year":"2005"},{"key":"2021102214140048300_ref11","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1145\/585265.585270","article-title":"Alternating-time temporal logic","volume":"49","author":"Alur","year":"2002","journal-title":"Journal of the ACM"},{"key":"2021102214140048300_ref12","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1016\/j.ic.2018.02.022","article-title":"Graded modalities in strategy logic","volume":"261","author":"Aminof","year":"2018","journal-title":"Information and Computation"},{"key":"2021102214140048300_ref13","article-title":"Probabilistic strategy logic","author":"Aminof","year":"2019","journal-title":"Twenty-eighth International Joint Conference on Artificial Intelligence"},{"key":"2021102214140048300_ref14","first-page":"258","article-title":"Prompt alternating-time epistemic logics","author":"Aminof","year":"2016","journal-title":"KR\u201916"},{"key":"2021102214140048300_ref15","first-page":"27","article-title":"Reasoning about knowledge and strategies: epistemic strategy logic","volume-title":"Proceedings 2nd International Workshop on Strategic Reasoning, SR 2014, Grenoble, France, April 5\u20136, 2014","author":"Belardinelli","year":"2014"},{"key":"2021102214140048300_ref16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-94-009-0553-5_7","article-title":"Seeing to it that: acanonical form for agentives","volume-title":"Knowledge Representation and Defeasible Reasoning","author":"Belnap","year":"1990"},{"key":"2021102214140048300_ref17","first-page":"1250","article-title":"Decidability results for ATL$^{\\ast }$ with imperfect information and perfect recall","volume-title":"Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems","author":"Berthon","year":"2017"},{"key":"2021102214140048300_ref18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/LICS.2017.8005136","article-title":"Strategy logic with imperfect information","volume-title":"2017 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","author":"Berthon","year":"2017"},{"key":"2021102214140048300_ref19","first-page":"1822","article-title":"Coalitions in action logic","volume-title":"20th International Joint Conference on Artificial Intelligence","author":"Borgo","year":"2007"},{"key":"2021102214140048300_ref20","first-page":"92","article-title":"A normal simulation of coalition logic and an epistemic extension","volume-title":"Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge","author":"Broersen","year":"2007"},{"key":"2021102214140048300_ref21","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-1-4419-6984-2_5","article-title":"Model checking logics of strategic ability: complexity","author":"Bulling","year":"2010","journal-title":"Specification and Verification of Multi-Agent Systems"},{"key":"2021102214140048300_ref22","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/978-3-642-16867-3_2","article-title":"Expressing properties of resource-bounded systems: the logics RTL$^{\\ast }$ and RTL","volume-title":"Computational Logic in Multi-Agent Systems","author":"Bulling","year":"2010"},{"key":"2021102214140048300_ref23","first-page":"567","article-title":"On the (un-) decidability of model checking resource-bounded agents","author":"Bulling","year":"2010","journal-title":"ECAI"},{"key":"2021102214140048300_ref24","doi-asserted-by":"crossref","first-page":"81","DOI":"10.3233\/FI-2009-0089","article-title":"What agents can probably enforce","volume":"93","author":"Bulling","year":"2009","journal-title":"Fundamenta Informaticae"},{"key":"2021102214140048300_ref25","doi-asserted-by":"crossref","first-page":"103287","DOI":"10.1016\/j.artint.2020.103287","article-title":"Knowing the price of success","author":"Cao","year":"2020","journal-title":"Artificial Intelligence"},{"key":"2021102214140048300_ref26","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1016\/j.ic.2009.07.004","article-title":"Strategy logic","volume":"208","author":"Chatterjee","year":"2010","journal-title":"Information and Computation"},{"key":"2021102214140048300_ref27","first-page":"185","article-title":"PRISM-games: a model checker for stochastic multi-player games","volume-title":"International Conference on TOOLS and Algorithms for the Construction and Analysis of Systems","author":"Chen","year":"2013"},{"key":"2021102214140048300_ref28","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1109\/FSKD.2007.458","article-title":"Probabilistic alternating-time temporal logic and model checking algorithm","volume-title":"Fourth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2007)","author":"Chen","year":"2007"},{"key":"2021102214140048300_ref29","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.entcs.2011.10.017","article-title":"On a logic for coalitional games with priced-resource agents","volume":"278","author":"Monica","year":"2011","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"2021102214140048300_ref30","first-page":"742","article-title":"Readings in uncertain reasoning","volume-title":"Introduction to Possibilistic and Fuzzy Logics","author":"Dubois","year":"1990"},{"key":"2021102214140048300_ref31","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0890-5401(90)90060-U","article-title":"A logic for reasoning about probabilities","volume":"87","author":"Fagin","year":"1990","journal-title":"Information and Computation"},{"key":"2021102214140048300_ref32","first-page":"2948","article-title":"A logic for reasoning about justified uncertain beliefs","author":"Fan","year":"2015","journal-title":"IJCAI"},{"key":"2021102214140048300_ref33","first-page":"207","article-title":"Coalition and group announcement logic","volume-title":"Proceedings Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK) 2017, Liverpool, UK, 24\u201326 July 2017","author":"Galimullin","year":"2017"},{"key":"2021102214140048300_ref34","first-page":"259","article-title":"Coalition games and alternating temporal logics","volume-title":"Proceedings of the 8th Conference on Theoretical Aspects of Rationality and Knowledge","author":"Goranko","year":"2001"},{"key":"2021102214140048300_ref35","first-page":"372","article-title":"Socially friendly and group protecting coalition logics","volume-title":"Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems","author":"Goranko","year":"2018"},{"key":"2021102214140048300_ref36","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/s10458-012-9192-y","article-title":"Strategic games and truly playable effectivity functions","volume":"26","author":"Goranko","year":"2013","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"2021102214140048300_ref37","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.tcs.2005.07.043","article-title":"Complete axiomatization and decidability of alternating-time temporal logic","volume":"353","author":"Goranko","year":"2006","journal-title":"Theoretical Computer Science"},{"key":"2021102214140048300_ref38","first-page":"175","article-title":"The modal logic of probability","volume-title":"Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge","author":"Heifetz","year":"1998"},{"key":"2021102214140048300_ref39","first-page":"1","article-title":"Action types in STIT semantics","author":"Horty","year":"2017","journal-title":"The Review of Symbolic Logic"},{"key":"2021102214140048300_ref40","doi-asserted-by":"crossref","DOI":"10.1093\/0195134613.001.0001","volume-title":"Agency and Deontic Logic","author":"Horty","year":"2001"},{"key":"2021102214140048300_ref41","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/BF01306968","article-title":"The deliberative STIT: a study of action, omission, ability, and obligation","volume":"24","author":"Horty","year":"1995","journal-title":"Journal of Philosophical Logic"},{"key":"2021102214140048300_ref42","article-title":"Probabilistic alternating-time temporal logic of incomplete information and synchronous perfect recall","volume-title":"AAAI","author":"Huang","year":"2012"},{"key":"2021102214140048300_ref43","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/978-3-319-27683-0_13","article-title":"Probabilistic justification logic","volume-title":"International Symposium on Logical Foundations of Computer Science","author":"Kokkinis","year":"2016"},{"key":"2021102214140048300_ref44","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s10009-017-0476-z","article-title":"Prism-games: verification and strategy synthesis for stochastic multi-player games with multiple objectives","volume":"20","author":"Kwiatkowska","year":"2018","journal-title":"International Journal on Software Tools for Technology Transfer"},{"key":"2021102214140048300_ref45","first-page":"43","article-title":"Quantitative modal logic and possibilistic reasoning","volume-title":"Proceedings of the 10th European Conference on Artificial Intelligence","author":"Liau","year":"1992"},{"key":"2021102214140048300_ref46","volume-title":"Introduction to Mathematical Logic","author":"Mendelson","year":"2009"},{"key":"2021102214140048300_ref47","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/j.apal.2013.07.015","article-title":"The logic of uncertain justifications","volume":"165","author":"Milnikel","year":"2014","journal-title":"Annals of Pure and Applied Logic"},{"key":"2021102214140048300_ref48","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/2631917","article-title":"Reasoning about strategies: on the model-checking problem","volume":"15","author":"Mogavero","year":"2014","journal-title":"ACM Transactions on Computational Logic"},{"key":"2021102214140048300_ref49","doi-asserted-by":"crossref","first-page":"1821","DOI":"10.1007\/s11229-014-0655-3","article-title":"Logic of confidence","volume":"192","author":"Naumov","year":"2015","journal-title":"Synthese"},{"key":"2021102214140048300_ref50","first-page":"723","article-title":"Coalition power in epistemic transition systems","volume-title":"Proceedings of the 2017 International Conference on Autonomous Agents and Multiagent Systems (AAMAS)","author":"Naumov","year":"2017"},{"key":"2021102214140048300_ref51","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v32i1.11579","article-title":"Strategic coalitions with perfect recall","volume-title":"Proceedings of Thirty-Second AAAI Conference on Artificial Intelligence","author":"Naumov","year":"2018"},{"key":"2021102214140048300_ref52","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/j.artint.2018.06.007","article-title":"Together we know how to achieve: an epistemic logic of know-how","volume":"262","author":"Naumov","year":"2018","journal-title":"Artificial Intelligence"},{"key":"2021102214140048300_ref53","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.artint.2019.06.007","article-title":"Knowing-how under uncertainty","volume":"276","author":"Naumov","year":"2019","journal-title":"Artificial Intelligence"},{"key":"2021102214140048300_ref54","first-page":"521","article-title":"A probabilistic logic for resource-bounded multi-agent systems","volume-title":"IJCAI","author":"Nguyen","year":"2019"},{"key":"2021102214140048300_ref55","article-title":"Agents, actions and goals in dynamic environments","volume-title":"Twenty-Second International Joint Conference on Artificial Intelligence","author":"Nov\u00e1k","year":"2011"},{"key":"2021102214140048300_ref56","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/S0304-3975(98)00341-7","article-title":"Some first-order probability logics","volume":"247","author":"Ognjanovi\u0107","year":"2000","journal-title":"Theoretical Computer Science"},{"key":"2021102214140048300_ref57","first-page":"1","article-title":"Inference as doxastic agency. Part I: the basics of justification STIT logic","author":"Olkhovikov","year":"2018","journal-title":"Studia Logica"},{"key":"2021102214140048300_ref58","volume-title":"Logic for Social Software","author":"Pauly","year":"2001"},{"key":"2021102214140048300_ref59","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1093\/logcom\/12.1.149","article-title":"A modal logic for coalitional power in games","volume":"12","author":"Pauly","year":"2002","journal-title":"Journal of Logic and Computation"},{"key":"2021102214140048300_ref60","volume-title":"Probability Theory","author":"R\u00e9nyi","year":"1970"},{"key":"2021102214140048300_ref61","first-page":"185","article-title":"Reasoning about action and cooperation","volume-title":"Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS \u201906","author":"Sauro","year":"2006"},{"key":"2021102214140048300_ref62","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.artint.2005.01.003","article-title":"On the logic of cooperation and propositional control","volume":"164","author":"van der Hoek","year":"2005","journal-title":"Artificial Intelligence"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/7\/1845\/40820420\/exab032.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/7\/1845\/40820420\/exab032.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T06:00:49Z","timestamp":1671861649000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/31\/7\/1845\/6276022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,17]]},"references-count":62,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2021,5,17]]},"published-print":{"date-parts":[[2021,10,22]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exab032","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,10]]},"published":{"date-parts":[[2021,5,17]]}}}