[{"volume":8704,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"3354"}]},"ec_funded":1,"language":[{}],"publication_status":"published","month":"09","intvolume":" 8704","alternative_title":[],"oa_version":"None","abstract":[{"lang":"eng"}],"department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"KrCh"}],"creator":{"login":"apreinsp","id":"4435EBFC-F248-11E8-B48F-1D18A9856A87"},"date_updated":"2023-02-23T11:23:36Z","status":"public","type":"conference","conference":{"end_date":"2014-09-05","location":"Rome, Italy","start_date":"2014-09-02","name":"CONCUR: Concurrency Theory"},"_id":"2054","date_published":"2014-09-01T00:00:00Z","date_created":"2018-12-11T11:55:27Z","page":"544 - 559","uri_base":"https://research-explorer.ista.ac.at","day":"01","publication":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","dc":{"source":["Chatterjee K. Qualitative concurrent parity games: Bounded rationality. In: Baldan P, Gorla D, eds. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 8704. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2014:544-559. doi:10.1007/978-3-662-44584-6_37"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-662-44584-6_37","info:eu-repo/grantAgreement/FWF//P 23499-N23","info:eu-repo/grantAgreement/FWF//S11407","info:eu-repo/grantAgreement/EC/FP7/279307"],"identifier":["https://research-explorer.ista.ac.at/record/2054"],"description":["We study two-player concurrent games on finite-state graphs played for an infinite number of rounds, where in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. The objectives are ω-regular winning conditions specified as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). While the qualitative analysis problem for concurrent parity games with infinite-memory, infinite-precision randomized strategies was studied before, we study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision, or infinite-precision; and in terms of memory, strategies can be memoryless, finite-memory, or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in (n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. Our symbolic algorithms are based on a characterization of the winning sets as μ-calculus formulas, however, our μ-calculus formulas are crucially different from the ones for concurrent parity games (without bounded rationality); and our memoryless witness strategy constructions are significantly different from the infinite-memory witness strategy constructions for concurrent parity games."],"date":["2014"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"publisher":["Schloss Dagstuhl - Leibniz-Zentrum für Informatik"],"language":["eng"],"rights":["info:eu-repo/semantics/closedAccess"],"creator":["Chatterjee, Krishnendu","Baldan, Paolo","Gorla, Daniele"],"title":["Qualitative concurrent parity games: Bounded rationality","LNCS"]},"quality_controlled":"1","editor":[{"first_name":"Paolo","last_name":"Baldan"},{"first_name":"Daniele","last_name":"Gorla"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"}],"publist_id":"4992","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","dini_type":"doc-type:conferenceObject","citation":{"apa":"Chatterjee, K. (2014). Qualitative concurrent parity games: Bounded rationality. In P. Baldan & D. Gorla (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8704, pp. 544–559). Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-662-44584-6_37","short":"K. Chatterjee, in:, P. Baldan, D. Gorla (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 544–559.","ieee":"K. Chatterjee, “Qualitative concurrent parity games: Bounded rationality,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Rome, Italy, 2014, vol. 8704, pp. 544–559.","mla":"Chatterjee, Krishnendu. “Qualitative Concurrent Parity Games: Bounded Rationality.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), edited by Paolo Baldan and Daniele Gorla, vol. 8704, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 544–59, doi:10.1007/978-3-662-44584-6_37.","ista":"Chatterjee K. 2014. Qualitative concurrent parity games: Bounded rationality. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). CONCUR: Concurrency Theory, LNCS, vol. 8704, 544–559.","chicago":"Chatterjee, Krishnendu. “Qualitative Concurrent Parity Games: Bounded Rationality.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), edited by Paolo Baldan and Daniele Gorla, 8704:544–59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. https://doi.org/10.1007/978-3-662-44584-6_37."},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}]}]