[{"acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), FWF Grant No P23499- N23, FWF NFN Grant No S114","oa":1,"quality_controlled":"1","publisher":"IEEE","publication":"Proceedings of the 31st Annual ACM/IEEE Symposium","day":"05","year":"2016","date_created":"2018-12-11T11:50:21Z","doi":"10.1145/2933575.2933588","date_published":"2016-07-05T00:00:00Z","page":"76 - 85","project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"The Wittgenstein Prize"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative automata under probabilistic semantics. Proceedings of the 31st Annual ACM/IEEE Symposium. LICS: Logic in Computer Science, 76–85.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Quantitative Automata under Probabilistic Semantics.” In Proceedings of the 31st Annual ACM/IEEE Symposium, 76–85. IEEE, 2016. https://doi.org/10.1145/2933575.2933588.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Quantitative automata under probabilistic semantics,” in Proceedings of the 31st Annual ACM/IEEE Symposium, New York, NY, USA, 2016, pp. 76–85.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings of the 31st Annual ACM/IEEE Symposium, IEEE, 2016, pp. 76–85.","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2016). Quantitative automata under probabilistic semantics. In Proceedings of the 31st Annual ACM/IEEE Symposium (pp. 76–85). New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2933588","ama":"Chatterjee K, Henzinger TA, Otop J. Quantitative automata under probabilistic semantics. In: Proceedings of the 31st Annual ACM/IEEE Symposium. IEEE; 2016:76-85. doi:10.1145/2933575.2933588","mla":"Chatterjee, Krishnendu, et al. “Quantitative Automata under Probabilistic Semantics.” Proceedings of the 31st Annual ACM/IEEE Symposium, IEEE, 2016, pp. 76–85, doi:10.1145/2933575.2933588."},"title":"Quantitative automata under probabilistic semantics","external_id":{"arxiv":["1604.06764"]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"publist_id":"6220","oa_version":"Preprint","abstract":[{"lang":"eng","text":"Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider. © 2016 ACM."}],"month":"07","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.06764"}],"scopus_import":1,"language":[{"iso":"eng"}],"publication_status":"published","ec_funded":1,"_id":"1138","status":"public","conference":{"name":"LICS: Logic in Computer Science","end_date":"2016-07-08","location":"New York, NY, USA","start_date":"2016-07-05"},"type":"conference","date_updated":"2021-01-12T06:48:34Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}]},{"day":"05","publication":"Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science","year":"2016","date_published":"2016-07-05T00:00:00Z","doi":"10.1145/2933575.2935304","date_created":"2018-12-11T11:50:22Z","page":"197 - 206","acknowledgement":"K. C., M. H., and W. D. are partially supported by the Vienna\r\nScience and Technology Fund (WWTF) through project ICT15-003.\r\nK. C. is partially supported by the Austrian Science Fund (FWF)\r\nNFN Grant No S11407-N23 (RiSE/SHiNE) and an ERC Start grant\r\n(279307: Graph Games). For W. D., M. H., and V. L. the research\r\nleading to these results has received funding from the European\r\nResearch Council under the European Union’s Seventh Framework\r\nProgramme (FP/2007-2013) / ERC Grant Agreement no. 340506.","quality_controlled":"1","publisher":"IEEE","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, Wolfgang Dvoák, Monika H Henzinger, and Veronika Loitzenbauer. “Model and Objective Separation with Conditional Lower Bounds: Disjunction Is Harder than Conjunction.” In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 197–206. IEEE, 2016. https://doi.org/10.1145/2933575.2935304.","ista":"Chatterjee K, Dvoák W, Henzinger MH, Loitzenbauer V. 2016. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, , 197–206.","mla":"Chatterjee, Krishnendu, et al. “Model and Objective Separation with Conditional Lower Bounds: Disjunction Is Harder than Conjunction.” Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206, doi:10.1145/2933575.2935304.","short":"K. Chatterjee, W. Dvoák, M.H. Henzinger, V. Loitzenbauer, in:, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206.","ieee":"K. Chatterjee, W. Dvoák, M. H. Henzinger, and V. Loitzenbauer, “Model and objective separation with conditional lower bounds: disjunction is harder than conjunction,” in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, New York, NY, USA, 2016, pp. 197–206.","apa":"Chatterjee, K., Dvoák, W., Henzinger, M. H., & Loitzenbauer, V. (2016). Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 197–206). New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2935304","ama":"Chatterjee K, Dvoák W, Henzinger MH, Loitzenbauer V. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2016:197-206. doi:10.1145/2933575.2935304"},"title":"Model and objective separation with conditional lower bounds: disjunction is harder than conjunction","publist_id":"6219","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Dvoák, Wolfgang","last_name":"Dvoák","first_name":"Wolfgang"},{"last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Loitzenbauer","full_name":"Loitzenbauer, Veronika","first_name":"Veronika"}],"article_processing_charge":"No","external_id":{"arxiv":["1602.02670"]},"project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"}],"language":[{"iso":"eng"}],"publication_status":"published","oa_version":"Preprint","abstract":[{"lang":"eng","text":"Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, graphs and Markov Decision Processes (MDPs), with respect to several fundamental -regular objectives, e.g., Rabin and Streett objectives. For many of these problems the best-known upper bounds are quadratic or cubic, yet no super-linear lower bounds are known. In this work our contributions are two-fold: First, we present several improved algorithms, and second, we present the first conditional super-linear lower bounds based on widely believed assumptions about the complexity of CNF-SAT and combinatorial Boolean matrix multiplication. A separation result for two models with respect to an objective means a conditional lower bound for one model that is strictly higher than the existing upper bound for the other model, and similarly for two objectives with respect to a model. Our results establish the following separation results: (1) A separation of models (graphs and MDPs) for disjunctive queries of reachability and Büchi objectives. (2) Two kinds of separations of objectives, both for graphs and MDPs, namely, (2a) the separation of dual objectives such as Streett/Rabin objectives, and (2b) the separation of conjunction and disjunction of multiple objectives of the same type such as safety, Büchi, and coBüchi. In summary, our results establish the first model and objective separation results for graphs and MDPs for various classical -regular objectives. Quite strikingly, we establish conditional lower bounds for the disjunction of objectives that are strictly higher than the existing upper bounds for the conjunction of the same objectives. © 2016 ACM."}],"month":"07","alternative_title":["Proceedings Symposium on Logic in Computer Science"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.02670"}],"date_updated":"2022-09-09T11:46:17Z","department":[{"_id":"KrCh"}],"_id":"1140","status":"public","type":"conference","conference":{"name":"LICS: Logic in Computer Science","location":"New York, NY, USA","end_date":"2016-07-08","start_date":"2016-07-05"}},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-21T10:04:26Z","citation":{"mla":"Chatterjee, Krishnendu, et al. Robust Draws in Balanced Knockout Tournaments. Vol. 2016–January, AAAI Press, 2016, pp. 172–79.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Tkadlec, J. (2016). Robust draws in balanced knockout tournaments (Vol. 2016–January, pp. 172–179). Presented at the IJCAI: International Joint Conference on Artificial Intelligence, New York, NY, USA: AAAI Press.","ama":"Chatterjee K, Ibsen-Jensen R, Tkadlec J. Robust draws in balanced knockout tournaments. In: Vol 2016-January. AAAI Press; 2016:172-179.","short":"K. Chatterjee, R. Ibsen-Jensen, J. Tkadlec, in:, AAAI Press, 2016, pp. 172–179.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and J. Tkadlec, “Robust draws in balanced knockout tournaments,” presented at the IJCAI: International Joint Conference on Artificial Intelligence, New York, NY, USA, 2016, vol. 2016–January, pp. 172–179.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Josef Tkadlec. “Robust Draws in Balanced Knockout Tournaments,” 2016–January:172–79. AAAI Press, 2016.","ista":"Chatterjee K, Ibsen-Jensen R, Tkadlec J. 2016. Robust draws in balanced knockout tournaments. IJCAI: International Joint Conference on Artificial Intelligence vol. 2016–January, 172–179."},"department":[{"_id":"KrCh"}],"title":"Robust draws in balanced knockout tournaments","publist_id":"6171","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684"}],"_id":"1182","project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Quantitative Reactive Modeling","grant_number":"267989","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"status":"public","conference":{"name":"IJCAI: International Joint Conference on Artificial Intelligence","location":"New York, NY, USA","end_date":"2016-07-15","start_date":"2016-07-09"},"type":"conference","language":[{"iso":"eng"}],"day":"01","publication_status":"published","year":"2016","ec_funded":1,"date_created":"2018-12-11T11:50:35Z","date_published":"2016-01-01T00:00:00Z","volume":"2016-January","related_material":{"link":[{"url":"https://www.ijcai.org/proceedings/2016","relation":"table_of_contents"}]},"page":"172 - 179","oa_version":"Preprint","abstract":[{"lang":"eng","text":"Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decisionmaking and elections. The traditional computational question, that asks to compute a draw (optimal draw) that maximizes the winning probability for a distinguished player, has received a lot of attention. Previous works consider the problem where the pairwise winning probabilities are known precisely, while we study how robust is the winning probability with respect to small errors in the pairwise winning probabilities. First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws."}],"month":"01","main_file_link":[{"url":"https://arxiv.org/abs/1604.05090v1","open_access":"1"}],"oa":1,"publisher":"AAAI Press","quality_controlled":"1","scopus_import":1},{"_id":"1200","type":"journal_article","tmp":{"short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png"},"status":"public","pubrep_id":"798","date_updated":"2021-01-12T06:49:03Z","ddc":["530"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:44:39Z","oa_version":"Submitted Version","scopus_import":1,"month":"12","intvolume":" 19","publication_status":"published","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"95e6dc78278334b99dacbf8822509364","file_id":"4855","creator":"system","date_updated":"2020-07-14T12:44:39Z","file_size":171352,"date_created":"2018-12-12T10:11:02Z","file_name":"IST-2017-798-v1+1_comment_adami.pdf"}],"language":[{"iso":"eng"}],"volume":19,"ec_funded":1,"license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"citation":{"ista":"Hilbe C, Traulsen A. 2016. Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze. Physics of Life Reviews. 19, 29–31.","chicago":"Hilbe, Christian, and Arne Traulsen. “Only the Combination of Mathematics and Agent Based Simulations Can Leverage the Full Potential of Evolutionary Modeling: Comment on ‘Evolutionary Game Theory Using Agent-Based Methods’ by C. Adami, J. Schossau and A. Hintze.” Physics of Life Reviews. Elsevier, 2016. https://doi.org/10.1016/j.plrev.2016.10.004.","ieee":"C. Hilbe and A. Traulsen, “Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on ‘Evolutionary game theory using agent-based methods’ by C. Adami, J. Schossau and A. Hintze,” Physics of Life Reviews, vol. 19. Elsevier, pp. 29–31, 2016.","short":"C. Hilbe, A. Traulsen, Physics of Life Reviews 19 (2016) 29–31.","ama":"Hilbe C, Traulsen A. Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze. Physics of Life Reviews. 2016;19:29-31. doi:10.1016/j.plrev.2016.10.004","apa":"Hilbe, C., & Traulsen, A. (2016). Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze. Physics of Life Reviews. Elsevier. https://doi.org/10.1016/j.plrev.2016.10.004","mla":"Hilbe, Christian, and Arne Traulsen. “Only the Combination of Mathematics and Agent Based Simulations Can Leverage the Full Potential of Evolutionary Modeling: Comment on ‘Evolutionary Game Theory Using Agent-Based Methods’ by C. Adami, J. Schossau and A. Hintze.” Physics of Life Reviews, vol. 19, Elsevier, 2016, pp. 29–31, doi:10.1016/j.plrev.2016.10.004."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Hilbe","full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","first_name":"Christian","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Arne","last_name":"Traulsen","full_name":"Traulsen, Arne"}],"publist_id":"6150","title":"Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze","acknowledgement":"C.H. acknowledges generous support from the ISTFELLOW program.","publisher":"Elsevier","quality_controlled":"1","oa":1,"has_accepted_license":"1","year":"2016","day":"01","publication":"Physics of Life Reviews","page":"29 - 31","date_published":"2016-12-01T00:00:00Z","doi":"10.1016/j.plrev.2016.10.004","date_created":"2018-12-11T11:50:40Z"},{"title":"Game-theoretic models identify useful principles for peer collaboration in online learning platforms","author":[{"full_name":"Pandey, Vineet","last_name":"Pandey","first_name":"Vineet"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"}],"publist_id":"6083","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Pandey, Vineet, and Krishnendu Chatterjee. “Game-Theoretic Models Identify Useful Principles for Peer Collaboration in Online Learning Platforms.” In Proceedings of the ACM Conference on Computer Supported Cooperative Work, 26:365–68. ACM, 2016. https://doi.org/10.1145/2818052.2869122.","ista":"Pandey V, Chatterjee K. 2016. Game-theoretic models identify useful principles for peer collaboration in online learning platforms. Proceedings of the ACM Conference on Computer Supported Cooperative Work. CSCW: Computer Supported Cooperative Work and Social Computing vol. 26, 365–368.","mla":"Pandey, Vineet, and Krishnendu Chatterjee. “Game-Theoretic Models Identify Useful Principles for Peer Collaboration in Online Learning Platforms.” Proceedings of the ACM Conference on Computer Supported Cooperative Work, vol. 26, no. Februar-2016, ACM, 2016, pp. 365–68, doi:10.1145/2818052.2869122.","short":"V. Pandey, K. Chatterjee, in:, Proceedings of the ACM Conference on Computer Supported Cooperative Work, ACM, 2016, pp. 365–368.","ieee":"V. Pandey and K. Chatterjee, “Game-theoretic models identify useful principles for peer collaboration in online learning platforms,” in Proceedings of the ACM Conference on Computer Supported Cooperative Work, San Francisco, CA, USA, 2016, vol. 26, no. Februar-2016, pp. 365–368.","ama":"Pandey V, Chatterjee K. Game-theoretic models identify useful principles for peer collaboration in online learning platforms. In: Proceedings of the ACM Conference on Computer Supported Cooperative Work. Vol 26. ACM; 2016:365-368. doi:10.1145/2818052.2869122","apa":"Pandey, V., & Chatterjee, K. (2016). Game-theoretic models identify useful principles for peer collaboration in online learning platforms. In Proceedings of the ACM Conference on Computer Supported Cooperative Work (Vol. 26, pp. 365–368). San Francisco, CA, USA: ACM. https://doi.org/10.1145/2818052.2869122"},"project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"date_created":"2018-12-11T11:50:55Z","date_published":"2016-02-27T00:00:00Z","doi":"10.1145/2818052.2869122","page":"365 - 368","publication":"Proceedings of the ACM Conference on Computer Supported Cooperative Work","day":"27","year":"2016","publisher":"ACM","quality_controlled":"1","acknowledgement":"ERC Start Grant Graph Games 279307 supported this research. ","department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T06:49:22Z","status":"public","conference":{"start_date":"2016-02-26","location":"San Francisco, CA, USA","end_date":"2016-03-02","name":"CSCW: Computer Supported Cooperative Work and Social Computing"},"type":"conference","_id":"1245","ec_funded":1,"issue":"Februar-2016","volume":26,"language":[{"iso":"eng"}],"publication_status":"published","intvolume":" 26","month":"02","scopus_import":1,"oa_version":"None","abstract":[{"text":"To facilitate collaboration in massive online classrooms, instructors must make many decisions. For instance, the following parameters need to be decided when designing a peer-feedback system where students review each others' essays: the number of students each student must provide feedback to, an algorithm to map feedback providers to receivers, constraints that ensure students do not become free-riders (receiving feedback but not providing it), the best times to receive feedback to improve learning etc. While instructors can answer these questions by running experiments or invoking past experience, game-theoretic models with data from online learning platforms can identify better initial designs for further improvements. As an example, we explore the design space of a peer feedback system by modeling it using game theory. Our simulations show that incentivizing students to provide feedback requires the value obtained from receiving a feedback to exceed the cost of providing it by a large factor (greater than 7). Furthermore, hiding feedback from low-effort students incentivizes them to provide more feedback.","lang":"eng"}]},{"acknowledgement":"The work has been supported by the Czech Science Foundation, grant No. 15-17564S, by EPSRC grant\r\nEP/M023656/1, and by the People Programme (Marie Curie Actions) of the European Union’s Seventh\r\nFramework Programme (FP7/2007-2013) under REA grant agreement no [291734]","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","year":"2016","has_accepted_license":"1","day":"01","date_created":"2018-12-11T11:51:23Z","doi":"10.4230/LIPIcs.CONCUR.2016.10","date_published":"2016-08-01T00:00:00Z","article_number":"10","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"citation":{"chicago":"Brázdil, Tomáš, Vojtěch Forejt, Antonín Kučera, and Petr Novotný. “Stability in Graphs and Games,” Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPIcs.CONCUR.2016.10.","ista":"Brázdil T, Forejt V, Kučera A, Novotný P. 2016. Stability in graphs and games. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 10.","mla":"Brázdil, Tomáš, et al. Stability in Graphs and Games. Vol. 59, 10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.CONCUR.2016.10.","apa":"Brázdil, T., Forejt, V., Kučera, A., & Novotný, P. (2016). Stability in graphs and games (Vol. 59). Presented at the CONCUR: Concurrency Theory, Quebec City, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2016.10","ama":"Brázdil T, Forejt V, Kučera A, Novotný P. Stability in graphs and games. In: Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPIcs.CONCUR.2016.10","ieee":"T. Brázdil, V. Forejt, A. Kučera, and P. Novotný, “Stability in graphs and games,” presented at the CONCUR: Concurrency Theory, Quebec City, Canada, 2016, vol. 59.","short":"T. Brázdil, V. Forejt, A. Kučera, P. Novotný, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Brázdil","full_name":"Brázdil, Tomáš","first_name":"Tomáš"},{"last_name":"Forejt","full_name":"Forejt, Vojtěch","first_name":"Vojtěch"},{"full_name":"Kučera, Antonín","last_name":"Kučera","first_name":"Antonín"},{"full_name":"Novotny, Petr","last_name":"Novotny","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"5944","title":"Stability in graphs and games","abstract":[{"text":"We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.","lang":"eng"}],"oa_version":"Published Version","scopus_import":1,"alternative_title":["LIPIcs"],"intvolume":" 59","month":"08","publication_status":"published","language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5229","checksum":"3c2dc6ab0358f8aa8f7aa7d6c1293159","creator":"system","date_updated":"2020-07-14T12:44:44Z","file_size":553648,"date_created":"2018-12-12T10:16:40Z","file_name":"IST-2016-665-v1+1_Forejt_et_al__Stability_in_graphs_and_games.pdf"}],"ec_funded":1,"license":"https://creativecommons.org/licenses/by/4.0/","volume":59,"_id":"1325","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"CONCUR: Concurrency Theory","location":"Quebec City, Canada","end_date":"2016-08-26","start_date":"2016-08-23"},"type":"conference","pubrep_id":"665","status":"public","date_updated":"2021-01-12T06:49:53Z","ddc":["004"],"file_date_updated":"2020-07-14T12:44:44Z","department":[{"_id":"KrCh"}]},{"oa_version":"None","abstract":[{"lang":"eng","text":"DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. Copyright "}],"month":"01","main_file_link":[{"url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/12999"}],"scopus_import":1,"quality_controlled":"1","publisher":"AAAI Press","publication":"Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling","language":[{"iso":"eng"}],"day":"01","year":"2016","publication_status":"published","date_created":"2018-12-11T11:51:22Z","ec_funded":1,"volume":"2016-January","date_published":"2016-01-01T00:00:00Z","page":"88 - 96","_id":"1324","status":"public","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"conference":{"start_date":"2016-06-12","location":"London, United Kingdom","end_date":"2016-06-17","name":"ICAPS: International Conference on Automated Planning and Scheduling"},"type":"conference","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, and Martin Chmelik. “Indefinite-Horizon Reachability in Goal-DEC-POMDPs.” In Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, 2016–January:88–96. AAAI Press, 2016.","ista":"Chatterjee K, Chmelik M. 2016. Indefinite-horizon reachability in Goal-DEC-POMDPs. Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling. ICAPS: International Conference on Automated Planning and Scheduling vol. 2016–January, 88–96.","mla":"Chatterjee, Krishnendu, and Martin Chmelik. “Indefinite-Horizon Reachability in Goal-DEC-POMDPs.” Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, vol. 2016–January, AAAI Press, 2016, pp. 88–96.","apa":"Chatterjee, K., & Chmelik, M. (2016). Indefinite-horizon reachability in Goal-DEC-POMDPs. In Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling (Vol. 2016–January, pp. 88–96). London, United Kingdom: AAAI Press.","ama":"Chatterjee K, Chmelik M. Indefinite-horizon reachability in Goal-DEC-POMDPs. In: Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling. Vol 2016-January. AAAI Press; 2016:88-96.","ieee":"K. Chatterjee and M. Chmelik, “Indefinite-horizon reachability in Goal-DEC-POMDPs,” in Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, London, United Kingdom, 2016, vol. 2016–January, pp. 88–96.","short":"K. Chatterjee, M. Chmelik, in:, Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, 2016, pp. 88–96."},"date_updated":"2021-01-12T06:49:53Z","department":[{"_id":"KrCh"}],"title":"Indefinite-horizon reachability in Goal-DEC-POMDPs","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik","full_name":"Chmelik, Martin"}],"publist_id":"5946"},{"date_created":"2018-12-11T11:51:23Z","ec_funded":1,"date_published":"2016-01-01T00:00:00Z","page":"1465 - 1466","language":[{"iso":"eng"}],"publication":"Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems","day":"01","publication_status":"published","year":"2016","month":"01","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1602.07565","open_access":"1"}],"quality_controlled":"1","publisher":"ACM","scopus_import":1,"oa_version":"Preprint","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels. ","lang":"eng"}],"title":"Stochastic shortest path with energy constraints in POMDPs","department":[{"_id":"KrCh"}],"author":[{"last_name":"Brázdil","full_name":"Brázdil, Tomáš","first_name":"Tomáš"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Chmelik","full_name":"Chmelik, Martin","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Anchit","full_name":"Gupta, Anchit","last_name":"Gupta"},{"full_name":"Novotny, Petr","last_name":"Novotny","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr"}],"publist_id":"5942","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:49:54Z","citation":{"ista":"Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. 2016. Stochastic shortest path with energy constraints in POMDPs. Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. AAMAS: Autonomous Agents & Multiagent Systems, 1465–1466.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Anchit Gupta, and Petr Novotný. “Stochastic Shortest Path with Energy Constraints in POMDPs.” In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, 1465–66. ACM, 2016.","short":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.","ieee":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, and P. Novotný, “Stochastic shortest path with energy constraints in POMDPs,” in Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, Singapore, 2016, pp. 1465–1466.","ama":"Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. Stochastic shortest path with energy constraints in POMDPs. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. ACM; 2016:1465-1466.","apa":"Brázdil, T., Chatterjee, K., Chmelik, M., Gupta, A., & Novotný, P. (2016). Stochastic shortest path with energy constraints in POMDPs. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (pp. 1465–1466). Singapore: ACM.","mla":"Brázdil, Tomáš, et al. “Stochastic Shortest Path with Energy Constraints in POMDPs.” Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–66."},"status":"public","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"conference":{"location":"Singapore","end_date":"2016-05-13","start_date":"2016-05-09","name":"AAMAS: Autonomous Agents & Multiagent Systems"},"type":"conference","_id":"1327"},{"date_updated":"2021-01-12T06:49:53Z","department":[{"_id":"KrCh"}],"_id":"1326","status":"public","type":"conference","conference":{"name":"ATVA: Automated Technology for Verification and Analysis","start_date":"2016-10-17","end_date":"2016-10-20","location":"Chiba, Japan"},"language":[{"iso":"eng"}],"publication_status":"published","volume":9938,"ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff. "}],"month":"09","intvolume":" 9938","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://arxiv.org/abs/1607.00678","open_access":"1"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Brázdil, Tomáš, et al. Optimizing the Expected Mean Payoff in Energy Markov Decision Processes. Vol. 9938, Springer, 2016, pp. 32–49, doi:10.1007/978-3-319-46520-3_3.","short":"T. Brázdil, A. Kučera, P. Novotný, in:, Springer, 2016, pp. 32–49.","ieee":"T. Brázdil, A. Kučera, and P. Novotný, “Optimizing the expected mean payoff in Energy Markov Decision Processes,” presented at the ATVA: Automated Technology for Verification and Analysis, Chiba, Japan, 2016, vol. 9938, pp. 32–49.","apa":"Brázdil, T., Kučera, A., & Novotný, P. (2016). Optimizing the expected mean payoff in Energy Markov Decision Processes (Vol. 9938, pp. 32–49). Presented at the ATVA: Automated Technology for Verification and Analysis, Chiba, Japan: Springer. https://doi.org/10.1007/978-3-319-46520-3_3","ama":"Brázdil T, Kučera A, Novotný P. Optimizing the expected mean payoff in Energy Markov Decision Processes. In: Vol 9938. Springer; 2016:32-49. doi:10.1007/978-3-319-46520-3_3","chicago":"Brázdil, Tomáš, Antonín Kučera, and Petr Novotný. “Optimizing the Expected Mean Payoff in Energy Markov Decision Processes,” 9938:32–49. Springer, 2016. https://doi.org/10.1007/978-3-319-46520-3_3.","ista":"Brázdil T, Kučera A, Novotný P. 2016. Optimizing the expected mean payoff in Energy Markov Decision Processes. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 9938, 32–49."},"title":"Optimizing the expected mean payoff in Energy Markov Decision Processes","author":[{"full_name":"Brázdil, Tomáš","last_name":"Brázdil","first_name":"Tomáš"},{"full_name":"Kučera, Antonín","last_name":"Kučera","first_name":"Antonín"},{"last_name":"Novotny","full_name":"Novotny, Petr","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"5943","project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"day":"22","year":"2016","doi":"10.1007/978-3-319-46520-3_3","date_published":"2016-09-22T00:00:00Z","date_created":"2018-12-11T11:51:23Z","page":"32 - 49","acknowledgement":"The research was funded by the Czech Science Foundation Grant No. P202/12/G061 and by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].","quality_controlled":"1","publisher":"Springer","oa":1},{"pubrep_id":"661","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","_id":"1333","file_date_updated":"2020-07-14T12:44:44Z","department":[{"_id":"KrCh"}],"ddc":["519","530","599"],"date_updated":"2021-01-12T06:49:57Z","intvolume":" 7","month":"03","scopus_import":1,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Social dilemmas force players to balance between personal and collective gain. In many dilemmas, such as elected governments negotiating climate-change mitigation measures, the decisions are made not by individual players but by their representatives. However, the behaviour of representatives in social dilemmas has not been investigated experimentally. Here inspired by the negotiations for greenhouse-gas emissions reductions, we experimentally study a collective-risk social dilemma that involves representatives deciding on behalf of their fellow group members. Representatives can be re-elected or voted out after each consecutive collective-risk game. Selfish players are preferentially elected and are hence found most frequently in the "representatives" treatment. Across all treatments, we identify the selfish players as extortioners. As predicted by our mathematical model, their steadfast strategies enforce cooperation from fair players who finally compensate almost completely the deficit caused by the extortionate co-players. Everybody gains, but the extortionate representatives and their groups gain the most."}],"volume":7,"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"9ea0d7ce59a555a1cb8353d5559407cb","file_id":"4834","creator":"system","file_size":1432577,"date_updated":"2020-07-14T12:44:44Z","file_name":"IST-2016-661-v1+1_ncomms10915.pdf","date_created":"2018-12-12T10:10:44Z"}],"publication_status":"published","article_number":"10915","title":"Humans choose representatives who enforce cooperation in social dilemmas through extortion","publist_id":"5935","author":[{"last_name":"Milinski","full_name":"Milinski, Manfred","first_name":"Manfred"},{"last_name":"Hilbe","orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian"},{"first_name":"Dirk","last_name":"Semmann","full_name":"Semmann, Dirk"},{"full_name":"Sommerfeld, Ralf","last_name":"Sommerfeld","first_name":"Ralf"},{"first_name":"Jochem","full_name":"Marotzke, Jochem","last_name":"Marotzke"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Milinski M, Hilbe C, Semmann D, Sommerfeld R, Marotzke J. 2016. Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature Communications. 7, 10915.","chicago":"Milinski, Manfred, Christian Hilbe, Dirk Semmann, Ralf Sommerfeld, and Jochem Marotzke. “Humans Choose Representatives Who Enforce Cooperation in Social Dilemmas through Extortion.” Nature Communications. Nature Publishing Group, 2016. https://doi.org/10.1038/ncomms10915.","apa":"Milinski, M., Hilbe, C., Semmann, D., Sommerfeld, R., & Marotzke, J. (2016). Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature Communications. Nature Publishing Group. https://doi.org/10.1038/ncomms10915","ama":"Milinski M, Hilbe C, Semmann D, Sommerfeld R, Marotzke J. Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature Communications. 2016;7. doi:10.1038/ncomms10915","ieee":"M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, and J. Marotzke, “Humans choose representatives who enforce cooperation in social dilemmas through extortion,” Nature Communications, vol. 7. Nature Publishing Group, 2016.","short":"M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, J. Marotzke, Nature Communications 7 (2016).","mla":"Milinski, Manfred, et al. “Humans Choose Representatives Who Enforce Cooperation in Social Dilemmas through Extortion.” Nature Communications, vol. 7, 10915, Nature Publishing Group, 2016, doi:10.1038/ncomms10915."},"oa":1,"quality_controlled":"1","publisher":"Nature Publishing Group","acknowledgement":"We thank the students for participation; H.-J. Krambeck for writing the software for the game; H. Arndt, T. Bakker, L. Becks, H. Brendelberger, S. Dobler and T. Reusch for support; and the Max Planck Society for the Advancement of Science for funding.","date_created":"2018-12-11T11:51:25Z","date_published":"2016-03-07T00:00:00Z","doi":"10.1038/ncomms10915","publication":"Nature Communications","day":"07","year":"2016","has_accepted_license":"1"},{"project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"name":"The Wittgenstein Prize","grant_number":"Z211","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"}],"title":"Quantitative monitor automata","publist_id":"5932","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger"},{"full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Quantitative monitor automata,” presented at the SAS: Static Analysis Symposium, Edinburgh, United Kingdom, 2016, vol. 9837, pp. 23–38.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 23–38.","ama":"Chatterjee K, Henzinger TA, Otop J. Quantitative monitor automata. In: Vol 9837. Springer; 2016:23-38. doi:10.1007/978-3-662-53413-7_2","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2016). Quantitative monitor automata (Vol. 9837, pp. 23–38). Presented at the SAS: Static Analysis Symposium, Edinburgh, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-53413-7_2","mla":"Chatterjee, Krishnendu, et al. Quantitative Monitor Automata. Vol. 9837, Springer, 2016, pp. 23–38, doi:10.1007/978-3-662-53413-7_2.","ista":"Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative monitor automata. SAS: Static Analysis Symposium, LNCS, vol. 9837, 23–38.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Quantitative Monitor Automata,” 9837:23–38. Springer, 2016. https://doi.org/10.1007/978-3-662-53413-7_2."},"oa":1,"quality_controlled":"1","publisher":"Springer","date_created":"2018-12-11T11:51:26Z","date_published":"2016-08-31T00:00:00Z","doi":"10.1007/978-3-662-53413-7_2","page":"23 - 38","day":"31","year":"2016","status":"public","conference":{"name":"SAS: Static Analysis Symposium","start_date":"2016-09-08","location":"Edinburgh, United Kingdom","end_date":"2016-09-10"},"type":"conference","_id":"1335","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_updated":"2021-01-12T06:49:58Z","intvolume":" 9837","month":"08","main_file_link":[{"url":"https://arxiv.org/abs/1604.06764","open_access":"1"}],"scopus_import":1,"alternative_title":["LNCS"],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"In this paper we review various automata-theoretic formalisms for expressing quantitative properties. We start with finite-state Boolean automata that express the traditional regular properties. We then consider weighted ω-automata that can measure the average density of events, which finite-state Boolean automata cannot. However, even weighted ω-automata cannot express basic performance properties like average response time. We finally consider two formalisms of weighted ω-automata with monitors, where the monitors are either (a) counters or (b) weighted automata themselves. We present a translation result to establish that these two formalisms are equivalent. Weighted ω-automata with monitors generalize weighted ω-automata, and can express average response time property. They present a natural, robust, and expressive framework for quantitative specifications, with important decidable properties."}],"ec_funded":1,"volume":9837,"language":[{"iso":"eng"}],"publication_status":"published"},{"citation":{"ista":"Hansen K, Ibsen-Jensen R, Koucký M. 2016. The big match in small space. SAGT: Symposium on Algorithmic Game Theory, LNCS, vol. 9928, 64–76.","chicago":"Hansen, Kristoffer, Rasmus Ibsen-Jensen, and Michal Koucký. “The Big Match in Small Space,” 9928:64–76. Springer, 2016. https://doi.org/10.1007/978-3-662-53354-3_6.","apa":"Hansen, K., Ibsen-Jensen, R., & Koucký, M. (2016). The big match in small space (Vol. 9928, pp. 64–76). Presented at the SAGT: Symposium on Algorithmic Game Theory, Liverpool, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-53354-3_6","ama":"Hansen K, Ibsen-Jensen R, Koucký M. The big match in small space. In: Vol 9928. Springer; 2016:64-76. doi:10.1007/978-3-662-53354-3_6","short":"K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 64–76.","ieee":"K. Hansen, R. Ibsen-Jensen, and M. Koucký, “The big match in small space,” presented at the SAGT: Symposium on Algorithmic Game Theory, Liverpool, United Kingdom, 2016, vol. 9928, pp. 64–76.","mla":"Hansen, Kristoffer, et al. The Big Match in Small Space. Vol. 9928, Springer, 2016, pp. 64–76, doi:10.1007/978-3-662-53354-3_6."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"5927","author":[{"last_name":"Hansen","full_name":"Hansen, Kristoffer","first_name":"Kristoffer"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"first_name":"Michal","full_name":"Koucký, Michal","last_name":"Koucký"}],"title":"The big match in small space","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"year":"2016","day":"01","page":"64 - 76","date_created":"2018-12-11T11:51:28Z","doi":"10.1007/978-3-662-53354-3_6","date_published":"2016-09-01T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"Springer","date_updated":"2021-01-12T06:50:00Z","department":[{"_id":"KrCh"}],"_id":"1340","conference":{"name":"SAGT: Symposium on Algorithmic Game Theory","end_date":"2016-09-21","location":"Liverpool, United Kingdom","start_date":"2016-09-19"},"type":"conference","status":"public","publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"volume":9928,"abstract":[{"text":"We study repeated games with absorbing states, a type of two-player, zero-sum concurrent mean-payoff games with the prototypical example being the Big Match of Gillete (1957). These games may not allow optimal strategies but they always have ε-optimal strategies. In this paper we design ε-optimal strategies for Player 1 in these games that use only O(log log T) space. Furthermore, we construct strategies for Player 1 that use space s(T), for an arbitrary small unbounded non-decreasing function s, and which guarantee an ε-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Ω(log T) and it was known that no strategy can use constant space if it is ε-optimal even in the limit superior sense. We also give a complementary lower bound. Furthermore, we also show that no Markov strategy, even extended with finite memory, can ensure value greater than 0 in the Big Match, answering a question posed by Neyman [11].","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1604.07634","open_access":"1"}],"scopus_import":1,"alternative_title":["LNCS"],"intvolume":" 9928","month":"09"},{"doi":"10.1145/2857050","date_published":"2016-06-01T00:00:00Z","volume":63,"issue":"3","date_created":"2018-12-11T11:51:41Z","publication_status":"published","year":"2016","day":"01","publication":"Journal of the ACM","language":[{"iso":"eng"}],"scopus_import":1,"publisher":"ACM","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1303.2981"}],"oa":1,"month":"06","intvolume":" 63","abstract":[{"lang":"eng","text":"We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem - determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NPRP."}],"oa_version":"Preprint","author":[{"id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","first_name":"Ventsislav K","last_name":"Chonev","full_name":"Chonev, Ventsislav K"},{"first_name":"Joël","full_name":"Ouaknine, Joël","last_name":"Ouaknine"},{"first_name":"James","full_name":"Worrell, James","last_name":"Worrell"}],"publist_id":"5831","title":"On the complexity of the orbit problem","department":[{"_id":"KrCh"}],"citation":{"chicago":"Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On the Complexity of the Orbit Problem.” Journal of the ACM. ACM, 2016. https://doi.org/10.1145/2857050.","ista":"Chonev VK, Ouaknine J, Worrell J. 2016. On the complexity of the orbit problem. Journal of the ACM. 63(3), 23.","mla":"Chonev, Ventsislav K., et al. “On the Complexity of the Orbit Problem.” Journal of the ACM, vol. 63, no. 3, 23, ACM, 2016, doi:10.1145/2857050.","ieee":"V. K. Chonev, J. Ouaknine, and J. Worrell, “On the complexity of the orbit problem,” Journal of the ACM, vol. 63, no. 3. ACM, 2016.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, Journal of the ACM 63 (2016).","ama":"Chonev VK, Ouaknine J, Worrell J. On the complexity of the orbit problem. Journal of the ACM. 2016;63(3). doi:10.1145/2857050","apa":"Chonev, V. K., Ouaknine, J., & Worrell, J. (2016). On the complexity of the orbit problem. Journal of the ACM. ACM. https://doi.org/10.1145/2857050"},"date_updated":"2021-01-12T06:50:17Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","type":"journal_article","status":"public","_id":"1380","article_number":"23"},{"oa_version":"Preprint","abstract":[{"text":"The continuous evolution of a wide variety of systems, including continous-time Markov chains and linear hybrid automata, can be\r\ndescribed in terms of linear differential equations. In this paper we study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target halfspace infinitely often. This recurrent reachability problem can\r\nequivalently be formulated as the following Infinite Zeros Problem: does a real-valued function f:R≥0 --> R satisfying a given linear\r\ndifferential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most 7, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.","lang":"eng"}],"month":"07","scopus_import":1,"publisher":"IEEE","quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1507.03632"}],"day":"05","publication":"LICS '16","language":[{"iso":"eng"}],"year":"2016","publication_status":"published","date_published":"2016-07-05T00:00:00Z","doi":"10.1145/2933575.2934548","date_created":"2018-12-11T11:51:44Z","ec_funded":1,"page":"515 - 524","_id":"1389","project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Quantitative Reactive Modeling","grant_number":"267989","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"status":"public","type":"conference","conference":{"start_date":"2018-07-05","end_date":"2018-07-08","location":"New York, NY, USA","name":"LICS: Logic in Computer Science"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” In LICS ’16, 515–24. IEEE, 2016. https://doi.org/10.1145/2933575.2934548.","ista":"Chonev VK, Ouaknine J, Worrell J. 2016. On recurrent reachability for continuous linear dynamical systems. LICS ’16. LICS: Logic in Computer Science, 515–524.","mla":"Chonev, Ventsislav K., et al. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” LICS ’16, IEEE, 2016, pp. 515–24, doi:10.1145/2933575.2934548.","apa":"Chonev, V. K., Ouaknine, J., & Worrell, J. (2016). On recurrent reachability for continuous linear dynamical systems. In LICS ’16 (pp. 515–524). New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2934548","ama":"Chonev VK, Ouaknine J, Worrell J. On recurrent reachability for continuous linear dynamical systems. In: LICS ’16. IEEE; 2016:515-524. doi:10.1145/2933575.2934548","ieee":"V. K. Chonev, J. Ouaknine, and J. Worrell, “On recurrent reachability for continuous linear dynamical systems,” in LICS ’16, New York, NY, USA, 2016, pp. 515–524.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, in:, LICS ’16, IEEE, 2016, pp. 515–524."},"date_updated":"2021-01-12T06:50:20Z","department":[{"_id":"KrCh"}],"title":"On recurrent reachability for continuous linear dynamical systems","author":[{"first_name":"Ventsislav K","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","last_name":"Chonev","full_name":"Chonev, Ventsislav K"},{"first_name":"Joël","last_name":"Ouaknine","full_name":"Ouaknine, Joël"},{"last_name":"Worrell","full_name":"Worrell, James","first_name":"James"}],"publist_id":"5820"},{"acknowledgement":"C.H. gratefully acknowledges funding by the Schrödinger scholarship of the Austrian Science Fund (FWF) J3475.","quality_controlled":"1","publisher":"Royal Society, The","oa":1,"has_accepted_license":"1","year":"2016","day":"01","publication":"Royal Society Open Science","doi":"10.1098/rsos.160036","date_published":"2016-05-01T00:00:00Z","date_created":"2018-12-11T11:51:57Z","article_number":"160036","citation":{"apa":"Chakra, M., Hilbe, C., & Traulsen, A. (2016). Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. Royal Society Open Science. Royal Society, The. https://doi.org/10.1098/rsos.160036","ama":"Chakra M, Hilbe C, Traulsen A. Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. Royal Society Open Science. 2016;3(5). doi:10.1098/rsos.160036","ieee":"M. Chakra, C. Hilbe, and A. Traulsen, “Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites,” Royal Society Open Science, vol. 3, no. 5. Royal Society, The, 2016.","short":"M. Chakra, C. Hilbe, A. Traulsen, Royal Society Open Science 3 (2016).","mla":"Chakra, Maria, et al. “Coevolutionary Interactions between Farmers and Mafia Induce Host Acceptance of Avian Brood Parasites.” Royal Society Open Science, vol. 3, no. 5, 160036, Royal Society, The, 2016, doi:10.1098/rsos.160036.","ista":"Chakra M, Hilbe C, Traulsen A. 2016. Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. Royal Society Open Science. 3(5), 160036.","chicago":"Chakra, Maria, Christian Hilbe, and Arne Traulsen. “Coevolutionary Interactions between Farmers and Mafia Induce Host Acceptance of Avian Brood Parasites.” Royal Society Open Science. Royal Society, The, 2016. https://doi.org/10.1098/rsos.160036."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"5776","author":[{"first_name":"Maria","full_name":"Chakra, Maria","last_name":"Chakra"},{"id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian","orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian","last_name":"Hilbe"},{"first_name":"Arne","last_name":"Traulsen","full_name":"Traulsen, Arne"}],"title":"Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites","abstract":[{"text":"Brood parasites exploit their host in order to increase their own fitness. Typically, this results in an arms race between parasite trickery and host defence. Thus, it is puzzling to observe hosts that accept parasitism without any resistance. The ‘mafia’ hypothesis suggests that these hosts accept parasitism to avoid retaliation. Retaliation has been shown to evolve when the hosts condition their response to mafia parasites, who use depredation as a targeted response to rejection. However, it is unclear if acceptance would also emerge when ‘farming’ parasites are present in the population. Farming parasites use depredation to synchronize the timing with the host, destroying mature clutches to force the host to re-nest. Herein, we develop an evolutionary model to analyse the interaction between depredatory parasites and their hosts. We show that coevolutionary cycles between farmers and mafia can still induce host acceptance of brood parasites. However, this equilibrium is unstable and in the long-run the dynamics of this host–parasite interaction exhibits strong oscillations: when farmers are the majority, accepters conditional to mafia (the host will reject first and only accept after retaliation by the parasite) have a higher fitness than unconditional accepters (the host always accepts parasitism). This leads to an increase in mafia parasites’ fitness and in turn induce an optimal environment for accepter hosts.","lang":"eng"}],"oa_version":"Published Version","scopus_import":1,"month":"05","intvolume":" 3","publication_status":"published","file":[{"date_created":"2018-12-12T10:14:49Z","file_name":"IST-2016-589-v1+1_160036.full.pdf","date_updated":"2020-07-14T12:44:53Z","file_size":937002,"creator":"system","checksum":"bf84211b31fe87451e738ba301d729c3","file_id":"5104","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"volume":3,"issue":"5","_id":"1426","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","pubrep_id":"589","date_updated":"2021-01-12T06:50:39Z","ddc":["000"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:44:53Z"},{"acknowledgement":"C.H. acknowledges generous funding from the Schrödinger scholarship of the Austrian Science Fund (FWF), J3475.","publisher":"Nature Publishing Group","quality_controlled":"1","oa":1,"day":"10","publication":"Scientific Reports","has_accepted_license":"1","year":"2016","date_published":"2016-05-10T00:00:00Z","doi":"10.1038/srep25676","date_created":"2018-12-11T11:51:56Z","article_number":"25676","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Baek S, Jeong H, Hilbe C, Nowak M. 2016. Comparing reactive and memory-one strategies of direct reciprocity. Scientific Reports. 6, 25676.","chicago":"Baek, Seung, Hyeongchai Jeong, Christian Hilbe, and Martin Nowak. “Comparing Reactive and Memory-One Strategies of Direct Reciprocity.” Scientific Reports. Nature Publishing Group, 2016. https://doi.org/10.1038/srep25676.","ama":"Baek S, Jeong H, Hilbe C, Nowak M. Comparing reactive and memory-one strategies of direct reciprocity. Scientific Reports. 2016;6. doi:10.1038/srep25676","apa":"Baek, S., Jeong, H., Hilbe, C., & Nowak, M. (2016). Comparing reactive and memory-one strategies of direct reciprocity. Scientific Reports. Nature Publishing Group. https://doi.org/10.1038/srep25676","short":"S. Baek, H. Jeong, C. Hilbe, M. Nowak, Scientific Reports 6 (2016).","ieee":"S. Baek, H. Jeong, C. Hilbe, and M. Nowak, “Comparing reactive and memory-one strategies of direct reciprocity,” Scientific Reports, vol. 6. Nature Publishing Group, 2016.","mla":"Baek, Seung, et al. “Comparing Reactive and Memory-One Strategies of Direct Reciprocity.” Scientific Reports, vol. 6, 25676, Nature Publishing Group, 2016, doi:10.1038/srep25676."},"title":"Comparing reactive and memory-one strategies of direct reciprocity","publist_id":"5784","author":[{"full_name":"Baek, Seung","last_name":"Baek","first_name":"Seung"},{"last_name":"Jeong","full_name":"Jeong, Hyeongchai","first_name":"Hyeongchai"},{"first_name":"Christian","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","last_name":"Hilbe","orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Direct reciprocity is a mechanism for the evolution of cooperation based on repeated interactions. When individuals meet repeatedly, they can use conditional strategies to enforce cooperative outcomes that would not be feasible in one-shot social dilemmas. Direct reciprocity requires that individuals keep track of their past interactions and find the right response. However, there are natural bounds on strategic complexity: Humans find it difficult to remember past interactions accurately, especially over long timespans. Given these limitations, it is natural to ask how complex strategies need to be for cooperation to evolve. Here, we study stochastic evolutionary game dynamics in finite populations to systematically compare the evolutionary performance of reactive strategies, which only respond to the co-player's previous move, and memory-one strategies, which take into account the own and the co-player's previous move. In both cases, we compare deterministic strategy and stochastic strategy spaces. For reactive strategies and small costs, we find that stochasticity benefits cooperation, because it allows for generous-tit-for-tat. For memory one strategies and small costs, we find that stochasticity does not increase the propensity for cooperation, because the deterministic rule of win-stay, lose-shift works best. For memory one strategies and large costs, however, stochasticity can augment cooperation."}],"month":"05","intvolume":" 6","scopus_import":1,"file":[{"date_created":"2018-12-12T10:18:08Z","file_name":"IST-2016-590-v1+1_srep25676.pdf","date_updated":"2020-07-14T12:44:53Z","file_size":1349915,"creator":"system","checksum":"ee17c482370d2e1b3add393710d3c696","file_id":"5327","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"publication_status":"published","volume":6,"_id":"1423","status":"public","pubrep_id":"590","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"],"date_updated":"2021-01-12T06:50:38Z","file_date_updated":"2020-07-14T12:44:53Z","department":[{"_id":"KrCh"}]},{"acknowledgement":"We thank Lynsey Bunnefeld for discussions throughout the project and Joshua Schraiber and one anonymous reviewer\r\nfor constructive comments on an earlier version of this manuscript. This work was supported by funding from the\r\nUnited Kingdom Natural Environment Research Council (to K.L.) (NE/I020288/1) and a grant from the European\r\nResearch Council (250152) (to N.H.B.).","oa":1,"publisher":"Genetics Society of America","quality_controlled":"1","publication":"Genetics","day":"01","year":"2016","has_accepted_license":"1","date_created":"2018-12-11T11:52:29Z","doi":"10.1534/genetics.115.183814","date_published":"2016-02-01T00:00:00Z","page":"775 - 786","project":[{"_id":"25B07788-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Limits to selection in biology and in evolutionary computation","grant_number":"250152"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Lohse K, Chmelik M, Martin S, Barton NH. 2016. Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics. 202(2), 775–786.","chicago":"Lohse, Konrad, Martin Chmelik, Simon Martin, and Nicholas H Barton. “Efficient Strategies for Calculating Blockwise Likelihoods under the Coalescent.” Genetics. Genetics Society of America, 2016. https://doi.org/10.1534/genetics.115.183814.","ama":"Lohse K, Chmelik M, Martin S, Barton NH. Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics. 2016;202(2):775-786. doi:10.1534/genetics.115.183814","apa":"Lohse, K., Chmelik, M., Martin, S., & Barton, N. H. (2016). Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics. Genetics Society of America. https://doi.org/10.1534/genetics.115.183814","short":"K. Lohse, M. Chmelik, S. Martin, N.H. Barton, Genetics 202 (2016) 775–786.","ieee":"K. Lohse, M. Chmelik, S. Martin, and N. H. Barton, “Efficient strategies for calculating blockwise likelihoods under the coalescent,” Genetics, vol. 202, no. 2. Genetics Society of America, pp. 775–786, 2016.","mla":"Lohse, Konrad, et al. “Efficient Strategies for Calculating Blockwise Likelihoods under the Coalescent.” Genetics, vol. 202, no. 2, Genetics Society of America, 2016, pp. 775–86, doi:10.1534/genetics.115.183814."},"title":"Efficient strategies for calculating blockwise likelihoods under the coalescent","article_processing_charge":"No","external_id":{"pmid":["26715666"]},"publist_id":"5658","author":[{"first_name":"Konrad","full_name":"Lohse, Konrad","last_name":"Lohse"},{"full_name":"Chmelik, Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin"},{"last_name":"Martin","full_name":"Martin, Simon","first_name":"Simon"},{"last_name":"Barton","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"pmid":1,"oa_version":"Preprint","abstract":[{"text":"The inference of demographic history from genome data is hindered by a lack of efficient computational approaches. In particular, it has proved difficult to exploit the information contained in the distribution of genealogies across the genome. We have previously shown that the generating function (GF) of genealogies can be used to analytically compute likelihoods of demographic models from configurations of mutations in short sequence blocks (Lohse et al. 2011). Although the GF has a simple, recursive form, the size of such likelihood calculations explodes quickly with the number of individuals and applications of this framework have so far been mainly limited to small samples (pairs and triplets) for which the GF can be written by hand. Here we investigate several strategies for exploiting the inherent symmetries of the coalescent. In particular, we show that the GF of genealogies can be decomposed into a set of equivalence classes that allows likelihood calculations from nontrivial samples. Using this strategy, we automated blockwise likelihood calculations for a general set of demographic scenarios in Mathematica. These histories may involve population size changes, continuous migration, discrete divergence, and admixture between multiple populations. To give a concrete example, we calculate the likelihood for a model of isolation with migration (IM), assuming two diploid samples without phase and outgroup information. We demonstrate the new inference scheme with an analysis of two individual butterfly genomes from the sister species Heliconius melpomene rosina and H. cydno.","lang":"eng"}],"intvolume":" 202","month":"02","scopus_import":"1","language":[{"iso":"eng"}],"file":[{"date_created":"2018-12-12T10:16:51Z","file_name":"IST-2016-561-v1+1_Lohse_et_al_Genetics_2015.pdf","date_updated":"2020-07-14T12:45:00Z","file_size":957466,"creator":"system","checksum":"41c9b5d72e7fe4624dd22dfe622337d5","file_id":"5241","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"publication_status":"published","ec_funded":1,"volume":202,"issue":"2","_id":"1518","pubrep_id":"561","status":"public","type":"journal_article","article_type":"original","ddc":["570"],"date_updated":"2022-05-24T09:16:22Z","file_date_updated":"2020-07-14T12:45:00Z","department":[{"_id":"KrCh"},{"_id":"NiBa"}]},{"author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"}],"publist_id":"7342","title":"The complexity of deciding legality of a single step of magic: The gathering","citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Deciding Legality of a Single Step of Magic: The Gathering,” 285:1432–39. IOS Press, 2016. https://doi.org/10.3233/978-1-61499-672-9-1432.","ista":"Chatterjee K, Ibsen-Jensen R. 2016. The complexity of deciding legality of a single step of magic: The gathering. ECAI: European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, vol. 285, 1432–1439.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Deciding Legality of a Single Step of Magic: The Gathering. Vol. 285, IOS Press, 2016, pp. 1432–39, doi:10.3233/978-1-61499-672-9-1432.","short":"K. Chatterjee, R. Ibsen-Jensen, in:, IOS Press, 2016, pp. 1432–1439.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The complexity of deciding legality of a single step of magic: The gathering,” presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands, 2016, vol. 285, pp. 1432–1439.","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2016). The complexity of deciding legality of a single step of magic: The gathering (Vol. 285, pp. 1432–1439). Presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands: IOS Press. https://doi.org/10.3233/978-1-61499-672-9-1432","ama":"Chatterjee K, Ibsen-Jensen R. The complexity of deciding legality of a single step of magic: The gathering. In: Vol 285. IOS Press; 2016:1432-1439. doi:10.3233/978-1-61499-672-9-1432"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publisher":"IOS Press","oa":1,"page":"1432 - 1439","date_published":"2016-01-01T00:00:00Z","doi":"10.3233/978-1-61499-672-9-1432","date_created":"2018-12-11T11:46:41Z","has_accepted_license":"1","year":"2016","day":"01","type":"conference","conference":{"name":"ECAI: European Conference on Artificial Intelligence","end_date":"2016-09-02","location":"The Hague, Netherlands","start_date":"2016-08-29"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"status":"public","pubrep_id":"950","_id":"478","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:35Z","date_updated":"2021-01-12T08:00:54Z","ddc":["004"],"alternative_title":["Frontiers in Artificial Intelligence and Applications"],"scopus_import":1,"month":"01","intvolume":" 285","abstract":[{"text":"Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic.","lang":"eng"}],"oa_version":"Published Version","volume":285,"license":"https://creativecommons.org/licenses/by-nc/4.0/","publication_status":"published","file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"848043c812ace05e459579c923f3d3cf","file_id":"4658","file_size":2116225,"date_updated":"2020-07-14T12:46:35Z","creator":"system","file_name":"IST-2018-950-v1+1_2016_Chatterjee_The_complexity.pdf","date_created":"2018-12-12T10:07:59Z"}],"language":[{"iso":"eng"}]},{"language":[{"iso":"eng"}],"publication_status":"published","volume":"05-08-July-2016","ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements."}],"month":"07","alternative_title":["Proceedings Symposium on Logic in Computer Science"],"scopus_import":1,"main_file_link":[{"url":"https://arxiv.org/abs/1604.06376","open_access":"1"}],"date_updated":"2021-01-12T08:00:56Z","department":[{"_id":"KrCh"}],"_id":"480","status":"public","type":"conference","conference":{"name":"LICS: Logic in Computer Science","location":"New York, NY, USA","end_date":"2016-07-08","start_date":"2016-07-05"},"day":"05","year":"2016","doi":"10.1145/2933575.2934513","date_published":"2016-07-05T00:00:00Z","date_created":"2018-12-11T11:46:42Z","page":"247 - 256","quality_controlled":"1","publisher":"IEEE","oa":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Doyen L. 2016. Perfect-information stochastic games with generalized mean-payoff objectives. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, vol. 05-08-July-2016, 247–256.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives,” 05-08-July-2016:247–56. IEEE, 2016. https://doi.org/10.1145/2933575.2934513.","ieee":"K. Chatterjee and L. Doyen, “Perfect-information stochastic games with generalized mean-payoff objectives,” presented at the LICS: Logic in Computer Science, New York, NY, USA, 2016, vol. 05-08-July-2016, pp. 247–256.","short":"K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256.","ama":"Chatterjee K, Doyen L. Perfect-information stochastic games with generalized mean-payoff objectives. In: Vol 05-08-July-2016. IEEE; 2016:247-256. doi:10.1145/2933575.2934513","apa":"Chatterjee, K., & Doyen, L. (2016). Perfect-information stochastic games with generalized mean-payoff objectives (Vol. 05-08-July-2016, pp. 247–256). Presented at the LICS: Logic in Computer Science, New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2934513","mla":"Chatterjee, Krishnendu, and Laurent Doyen. Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives. Vol. 05-08-July-2016, IEEE, 2016, pp. 247–56, doi:10.1145/2933575.2934513."},"title":"Perfect-information stochastic games with generalized mean-payoff objectives","publist_id":"7340","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Doyen","full_name":"Doyen, Laurent","first_name":"Laurent"}],"project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"}]},{"ec_funded":1,"issue":"5","volume":82,"related_material":{"record":[{"status":"public","id":"2295","relation":"earlier_version"},{"status":"public","id":"5400","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"publication_status":"published","intvolume":" 82","month":"08","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1309.2802"}],"scopus_import":1,"oa_version":"Preprint","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples.","lang":"eng"}],"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:24:38Z","status":"public","type":"journal_article","_id":"1477","date_created":"2018-12-11T11:52:15Z","doi":"10.1016/j.jcss.2016.02.009","date_published":"2016-08-01T00:00:00Z","page":"878 - 911","publication":"Journal of Computer and System Sciences","day":"01","year":"2016","oa":1,"publisher":"Elsevier","quality_controlled":"1","title":"What is decidable about partially observable Markov decision processes with ω-regular objectives","external_id":{"arxiv":["1309.2802"]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Chmelik, Martin","last_name":"Chmelik"},{"last_name":"Tracol","full_name":"Tracol, Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","first_name":"Mathieu"}],"publist_id":"5718","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Chmelik M, Tracol M. 2016. What is decidable about partially observable Markov decision processes with ω-regular objectives. Journal of Computer and System Sciences. 82(5), 878–911.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives.” Journal of Computer and System Sciences. Elsevier, 2016. https://doi.org/10.1016/j.jcss.2016.02.009.","apa":"Chatterjee, K., Chmelik, M., & Tracol, M. (2016). What is decidable about partially observable Markov decision processes with ω-regular objectives. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2016.02.009","ama":"Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable Markov decision processes with ω-regular objectives. Journal of Computer and System Sciences. 2016;82(5):878-911. doi:10.1016/j.jcss.2016.02.009","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially observable Markov decision processes with ω-regular objectives,” Journal of Computer and System Sciences, vol. 82, no. 5. Elsevier, pp. 878–911, 2016.","short":"K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.","mla":"Chatterjee, Krishnendu, et al. “What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives.” Journal of Computer and System Sciences, vol. 82, no. 5, Elsevier, 2016, pp. 878–911, doi:10.1016/j.jcss.2016.02.009."},"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}]}]