--- _id: '9402' abstract: - lang: eng text: Direct and indirect reciprocity are key mechanisms for the evolution of cooperation. Direct reciprocity means that individuals use their own experience to decide whether to cooperate with another person. Indirect reciprocity means that they also consider the experiences of others. Although these two mechanisms are intertwined, they are typically studied in isolation. Here, we introduce a mathematical framework that allows us to explore both kinds of reciprocity simultaneously. We show that the well-known ‘generous tit-for-tat’ strategy of direct reciprocity has a natural analogue in indirect reciprocity, which we call ‘generous scoring’. Using an equilibrium analysis, we characterize under which conditions either of the two strategies can maintain cooperation. With simulations, we additionally explore which kind of reciprocity evolves when members of a population engage in social learning to adapt to their environment. Our results draw unexpected connections between direct and indirect reciprocity while highlighting important differences regarding their evolvability. acknowledgement: 'This work was supported by the European Research Council CoG 863818 (ForM-SMArt) (to K.C.), the European Research Council Start Grant 279307: Graph Games (to K.C.), and the European Research Council Starting Grant 850529: E-DIRECT (to C.H.). The funders had no role in study design, data collection and analysis, decision to publish or preparation of the manuscript.' article_processing_charge: No article_type: original author: - first_name: Laura full_name: Schmid, Laura id: 38B437DE-F248-11E8-B48F-1D18A9856A87 last_name: Schmid orcid: 0000-0002-6978-7329 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Christian full_name: Hilbe, Christian id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87 last_name: Hilbe orcid: 0000-0001-5116-955X - first_name: Martin A. full_name: Nowak, Martin A. last_name: Nowak citation: ama: Schmid L, Chatterjee K, Hilbe C, Nowak MA. A unified framework of direct and indirect reciprocity. Nature Human Behaviour. 2021;5(10):1292–1302. doi:10.1038/s41562-021-01114-8 apa: Schmid, L., Chatterjee, K., Hilbe, C., & Nowak, M. A. (2021). A unified framework of direct and indirect reciprocity. Nature Human Behaviour. Springer Nature. https://doi.org/10.1038/s41562-021-01114-8 chicago: Schmid, Laura, Krishnendu Chatterjee, Christian Hilbe, and Martin A. Nowak. “A Unified Framework of Direct and Indirect Reciprocity.” Nature Human Behaviour. Springer Nature, 2021. https://doi.org/10.1038/s41562-021-01114-8. ieee: L. Schmid, K. Chatterjee, C. Hilbe, and M. A. Nowak, “A unified framework of direct and indirect reciprocity,” Nature Human Behaviour, vol. 5, no. 10. Springer Nature, pp. 1292–1302, 2021. ista: Schmid L, Chatterjee K, Hilbe C, Nowak MA. 2021. A unified framework of direct and indirect reciprocity. Nature Human Behaviour. 5(10), 1292–1302. mla: Schmid, Laura, et al. “A Unified Framework of Direct and Indirect Reciprocity.” Nature Human Behaviour, vol. 5, no. 10, Springer Nature, 2021, pp. 1292–1302, doi:10.1038/s41562-021-01114-8. short: L. Schmid, K. Chatterjee, C. Hilbe, M.A. Nowak, Nature Human Behaviour 5 (2021) 1292–1302. date_created: 2021-05-18T16:56:57Z date_published: 2021-05-13T00:00:00Z date_updated: 2024-03-27T23:30:44Z day: '13' ddc: - '000' department: - _id: KrCh - _id: GradSch doi: 10.1038/s41562-021-01114-8 ec_funded: 1 external_id: isi: - '000650304000002' pmid: - '33986519' file: - access_level: open_access checksum: 34f55e173f90dc1dab731063458ac780 content_type: application/pdf creator: dernst date_created: 2023-11-07T08:27:23Z date_updated: 2023-11-07T08:27:23Z file_id: '14496' file_name: 2021_NatureHumanBehaviour_Schmid_accepted.pdf file_size: 5232761 relation: main_file success: 1 file_date_updated: 2023-11-07T08:27:23Z has_accepted_license: '1' intvolume: ' 5' isi: 1 issue: '10' language: - iso: eng month: '05' oa: 1 oa_version: Submitted Version page: 1292–1302 pmid: 1 project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' publication: Nature Human Behaviour publication_identifier: eissn: - 2397-3374 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: link: - description: News on IST Homepage relation: press_release url: https://ist.ac.at/en/news/the-emergence-of-cooperation/ record: - id: '10293' relation: dissertation_contains status: public scopus_import: '1' status: public title: A unified framework of direct and indirect reciprocity type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 5 year: '2021' ... --- _id: '7346' abstract: - lang: eng text: 'The Price of Anarchy (PoA) is a well-established game-theoretic concept to shed light on coordination issues arising in open distributed systems. Leaving agents to selfishly optimize comes with the risk of ending up in sub-optimal states (in terms of performance and/or costs), compared to a centralized system design. However, the PoA relies on strong assumptions about agents'' rationality (e.g., resources and information) and interactions, whereas in many distributed systems agents interact locally with bounded resources. They do so repeatedly over time (in contrast to "one-shot games"), and their strategies may evolve. Using a more realistic evolutionary game model, this paper introduces a realized evolutionary Price of Anarchy (ePoA). The ePoA allows an exploration of equilibrium selection in dynamic distributed systems with multiple equilibria, based on local interactions of simple memoryless agents. Considering a fundamental game related to virus propagation on networks, we present analytical bounds on the ePoA in basic network topologies and for different strategy update dynamics. In particular, deriving stationary distributions of the stochastic evolutionary process, we find that the Nash equilibria are not always the most abundant states, and that different processes can feature significant off-equilibrium behavior, leading to a significantly higher ePoA compared to the PoA studied traditionally in the literature. ' alternative_title: - LIPIcs article_number: '21' article_processing_charge: No author: - first_name: Laura full_name: Schmid, Laura id: 38B437DE-F248-11E8-B48F-1D18A9856A87 last_name: Schmid orcid: 0000-0002-6978-7329 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'Schmid L, Chatterjee K, Schmid S. The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game. In: Proceedings of the 23rd International Conference on Principles of Distributed Systems. Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.OPODIS.2019.21' apa: 'Schmid, L., Chatterjee, K., & Schmid, S. (2020). The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game. In Proceedings of the 23rd International Conference on Principles of Distributed Systems (Vol. 153). Neuchâtel, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2019.21' chicago: 'Schmid, Laura, Krishnendu Chatterjee, and Stefan Schmid. “The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game.” In Proceedings of the 23rd International Conference on Principles of Distributed Systems, Vol. 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.OPODIS.2019.21.' ieee: 'L. Schmid, K. Chatterjee, and S. Schmid, “The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game,” in Proceedings of the 23rd International Conference on Principles of Distributed Systems, Neuchâtel, Switzerland, 2020, vol. 153.' ista: 'Schmid L, Chatterjee K, Schmid S. 2020. The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game. Proceedings of the 23rd International Conference on Principles of Distributed Systems. OPODIS: International Conference on Principles of Distributed Systems, LIPIcs, vol. 153, 21.' mla: 'Schmid, Laura, et al. “The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game.” Proceedings of the 23rd International Conference on Principles of Distributed Systems, vol. 153, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.OPODIS.2019.21.' short: L. Schmid, K. Chatterjee, S. Schmid, in:, Proceedings of the 23rd International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2019-12-19 location: Neuchâtel, Switzerland name: 'OPODIS: International Conference on Principles of Distributed Systems' start_date: 2019-12-17 date_created: 2020-01-21T16:00:26Z date_published: 2020-02-10T00:00:00Z date_updated: 2023-02-23T13:05:49Z day: '10' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.OPODIS.2019.21 external_id: arxiv: - '1906.00110' file: - access_level: open_access checksum: 9a91916ac2c21ab42458fcda39ef0b8d content_type: application/pdf creator: dernst date_created: 2020-03-23T09:14:06Z date_updated: 2020-07-14T12:47:56Z file_id: '7608' file_name: 2019_LIPIcS_Schmid.pdf file_size: 630752 relation: main_file file_date_updated: 2020-07-14T12:47:56Z has_accepted_license: '1' intvolume: ' 153' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '02' oa: 1 oa_version: Preprint project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering publication: Proceedings of the 23rd International Conference on Principles of Distributed Systems publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 153 year: '2020' ... --- _id: '8600' abstract: - lang: eng text: 'A vector addition system with states (VASS) consists of a finite set of states and counters. A transition changes the current state to the next state, and every counter is either incremented, or decremented, or left unchanged. A state and value for each counter is a configuration; and a computation is an infinite sequence of configurations with transitions between successive configurations. A probabilistic VASS consists of a VASS along with a probability distribution over the transitions for each state. Qualitative properties such as state and configuration reachability have been widely studied for VASS. In this work we consider multi-dimensional long-run average objectives for VASS and probabilistic VASS. For a counter, the cost of a configuration is the value of the counter; and the long-run average value of a computation for the counter is the long-run average of the costs of the configurations in the computation. The multi-dimensional long-run average problem given a VASS and a threshold value for each counter, asks whether there is a computation such that for each counter the long-run average value for the counter does not exceed the respective threshold. For probabilistic VASS, instead of the existence of a computation, we consider whether the expected long-run average value for each counter does not exceed the respective threshold. Our main results are as follows: we show that the multi-dimensional long-run average problem (a) is NP-complete for integer-valued VASS; (b) is undecidable for natural-valued VASS (i.e., nonnegative counters); and (c) can be solved in polynomial time for probabilistic integer-valued VASS, and probabilistic natural-valued VASS when all computations are non-terminating.' alternative_title: - LIPIcs article_number: '23' article_processing_charge: No author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop citation: ama: 'Chatterjee K, Henzinger TA, Otop J. Multi-dimensional long-run average problems for vector addition systems with states. In: 31st International Conference on Concurrency Theory. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.CONCUR.2020.23' apa: 'Chatterjee, K., Henzinger, T. A., & Otop, J. (2020). Multi-dimensional long-run average problems for vector addition systems with states. In 31st International Conference on Concurrency Theory (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23' chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” In 31st International Conference on Concurrency Theory, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23. ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, “Multi-dimensional long-run average problems for vector addition systems with states,” in 31st International Conference on Concurrency Theory, Virtual, 2020, vol. 171. ista: 'Chatterjee K, Henzinger TA, Otop J. 2020. Multi-dimensional long-run average problems for vector addition systems with states. 31st International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 171, 23.' mla: Chatterjee, Krishnendu, et al. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” 31st International Conference on Concurrency Theory, vol. 171, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.CONCUR.2020.23. short: K. Chatterjee, T.A. Henzinger, J. Otop, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-09-04 location: Virtual name: 'CONCUR: Conference on Concurrency Theory' start_date: 2020-09-01 date_created: 2020-10-04T22:01:36Z date_published: 2020-08-06T00:00:00Z date_updated: 2021-01-12T08:20:15Z day: '06' ddc: - '000' department: - _id: KrCh - _id: ToHe doi: 10.4230/LIPIcs.CONCUR.2020.23 external_id: arxiv: - '2007.08917' file: - access_level: open_access checksum: 5039752f644c4b72b9361d21a5e31baf content_type: application/pdf creator: dernst date_created: 2020-10-05T14:04:25Z date_updated: 2020-10-05T14:04:25Z file_id: '8610' file_name: 2020_LIPIcsCONCUR_Chatterjee.pdf file_size: 601231 relation: main_file success: 1 file_date_updated: 2020-10-05T14:04:25Z has_accepted_license: '1' intvolume: ' 171' language: - iso: eng license: https://creativecommons.org/licenses/by/3.0/ month: '08' oa: 1 oa_version: Published Version project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25F2ACDE-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Rigorous Systems Engineering - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize publication: 31st International Conference on Concurrency Theory publication_identifier: isbn: - '9783959771603' issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Multi-dimensional long-run average problems for vector addition systems with states tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode name: Creative Commons Attribution 3.0 Unported (CC BY 3.0) short: CC BY (3.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 171 year: '2020' ... --- _id: '8533' abstract: - lang: eng text: Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp., overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e.g., configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete. acknowledgement: "Krishnendu Chatterjee: The research was partially supported by the Vienna Science and\r\nTechnology Fund (WWTF) Project ICT15-003.\r\nIsmaël Jecker: This project has received funding from the European Union’s Horizon 2020 research\r\nand innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411." alternative_title: - LIPIcs article_number: 22:1-22:13 article_processing_charge: No author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Ismael R full_name: Jecker, Ismael R id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425 last_name: Jecker - first_name: Jakub full_name: Svoboda, Jakub id: 130759D2-D7DD-11E9-87D2-DE0DE6697425 last_name: Svoboda citation: ama: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Simplified game of life: Algorithms and complexity. In: 45th International Symposium on Mathematical Foundations of Computer Science. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.MFCS.2020.22' apa: 'Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., & Svoboda, J. (2020). Simplified game of life: Algorithms and complexity. In 45th International Symposium on Mathematical Foundations of Computer Science (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2020.22' chicago: 'Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub Svoboda. “Simplified Game of Life: Algorithms and Complexity.” In 45th International Symposium on Mathematical Foundations of Computer Science, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.MFCS.2020.22.' ieee: 'K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Simplified game of life: Algorithms and complexity,” in 45th International Symposium on Mathematical Foundations of Computer Science, Prague, Czech Republic, 2020, vol. 170.' ista: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2020. Simplified game of life: Algorithms and complexity. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 22:1-22:13.' mla: 'Chatterjee, Krishnendu, et al. “Simplified Game of Life: Algorithms and Complexity.” 45th International Symposium on Mathematical Foundations of Computer Science, vol. 170, 22:1-22:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.MFCS.2020.22.' short: K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-08-28 location: Prague, Czech Republic name: 'MFCS: Symposium on Mathematical Foundations of Computer Science' start_date: 2020-08-24 date_created: 2020-09-20T22:01:36Z date_published: 2020-08-18T00:00:00Z date_updated: 2021-01-12T08:19:55Z day: '18' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.MFCS.2020.22 ec_funded: 1 external_id: arxiv: - '2007.02894' file: - access_level: open_access checksum: bbd7c4f55d45f2ff2a0a4ef0e10a77b1 content_type: application/pdf creator: dernst date_created: 2020-09-21T13:57:34Z date_updated: 2020-09-21T13:57:34Z file_id: '8550' file_name: 2020_LIPIcs_Chatterjee.pdf file_size: 491374 relation: main_file success: 1 file_date_updated: 2020-09-21T13:57:34Z has_accepted_license: '1' intvolume: ' 170' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 25892FC0-B435-11E9-9278-68D0E5697425 grant_number: ICT15-003 name: Efficient Algorithms for Computer Aided Verification - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: 45th International Symposium on Mathematical Foundations of Computer Science publication_identifier: isbn: - '9783959771597' issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Simplified game of life: Algorithms and complexity' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode name: Creative Commons Attribution 3.0 Unported (CC BY 3.0) short: CC BY (3.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 170 year: '2020' ... --- _id: '8534' abstract: - lang: eng text: A regular language L of finite words is composite if there are regular languages L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise, L is prime. Primality of regular languages was introduced and studied in [O. Kupferman and J. Mosheiff, 2015], where the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. We study primality for unary regular languages, namely regular languages with a singleton alphabet. A unary language corresponds to a subset of ℕ, making the study of unary prime languages closer to that of primality in number theory. We show that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for primality checking of unary DFAs. acknowledgement: "Ismaël Jecker: This project has received funding from the European Union’s Horizon\r\n2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.\r\n754411. Nicolas Mazzocchi: PhD fellowship FRIA from the F.R.S.-FNRS." alternative_title: - LIPIcs article_number: 51:1-51:12 article_processing_charge: No author: - first_name: Ismael R full_name: Jecker, Ismael R id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425 last_name: Jecker - first_name: Orna full_name: Kupferman, Orna last_name: Kupferman - first_name: Nicolas full_name: Mazzocchi, Nicolas last_name: Mazzocchi citation: ama: 'Jecker IR, Kupferman O, Mazzocchi N. Unary prime languages. In: 45th International Symposium on Mathematical Foundations of Computer Science. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.MFCS.2020.51' apa: 'Jecker, I. R., Kupferman, O., & Mazzocchi, N. (2020). Unary prime languages. In 45th International Symposium on Mathematical Foundations of Computer Science (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2020.51' chicago: Jecker, Ismael R, Orna Kupferman, and Nicolas Mazzocchi. “Unary Prime Languages.” In 45th International Symposium on Mathematical Foundations of Computer Science, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.MFCS.2020.51. ieee: I. R. Jecker, O. Kupferman, and N. Mazzocchi, “Unary prime languages,” in 45th International Symposium on Mathematical Foundations of Computer Science, Prague, Czech Republic, 2020, vol. 170. ista: 'Jecker IR, Kupferman O, Mazzocchi N. 2020. Unary prime languages. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 51:1-51:12.' mla: Jecker, Ismael R., et al. “Unary Prime Languages.” 45th International Symposium on Mathematical Foundations of Computer Science, vol. 170, 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.MFCS.2020.51. short: I.R. Jecker, O. Kupferman, N. Mazzocchi, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-08-28 location: Prague, Czech Republic name: 'MFCS: Symposium on Mathematical Foundations of Computer Science' start_date: 2020-08-24 date_created: 2020-09-20T22:01:36Z date_published: 2020-08-18T00:00:00Z date_updated: 2021-01-12T08:19:56Z day: '18' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.MFCS.2020.51 ec_funded: 1 file: - access_level: open_access checksum: 2dc9e2fad6becd4563aef3e27a473f70 content_type: application/pdf creator: dernst date_created: 2020-09-21T14:17:08Z date_updated: 2020-09-21T14:17:08Z file_id: '8552' file_name: 2020_LIPIcsMFCS_Jecker.pdf file_size: 597977 relation: main_file success: 1 file_date_updated: 2020-09-21T14:17:08Z has_accepted_license: '1' intvolume: ' 170' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: 45th International Symposium on Mathematical Foundations of Computer Science publication_identifier: isbn: - '9783959771597' issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Unary prime languages tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode name: Creative Commons Attribution 3.0 Unported (CC BY 3.0) short: CC BY (3.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 170 year: '2020' ... --- _id: '7955' abstract: - lang: eng text: Simple stochastic games are turn-based 2½-player games with a reachability objective. The basic question asks whether one player can ensure reaching a given target with at least a given probability. A natural extension is games with a conjunction of such conditions as objective. Despite a plethora of recent results on the analysis of systems with multiple objectives, the decidability of this basic problem remains open. In this paper, we present an algorithm approximating the Pareto frontier of the achievable values to a given precision. Moreover, it is an anytime algorithm, meaning it can be stopped at any time returning the current approximation and its error bound. acknowledgement: "Pranav Ashok, Jan Křetínský and Maximilian Weininger were funded in part by TUM IGSSE Grant 10.06 (PARSEC) and the German Research Foundation (DFG) project KR 4890/2-1\r\n“Statistical Unbounded Verification”. Krishnendu Chatterjee was supported by the ERC CoG 863818 (ForM-SMArt) and Vienna Science and Technology Fund (WWTF) Project ICT15-\r\n003. Tobias Winkler was supported by the RTG 2236 UnRAVe." article_processing_charge: No author: - first_name: Pranav full_name: Ashok, Pranav last_name: Ashok - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Jan full_name: Kretinsky, Jan last_name: Kretinsky - first_name: Maximilian full_name: Weininger, Maximilian last_name: Weininger - first_name: Tobias full_name: Winkler, Tobias last_name: Winkler citation: ama: 'Ashok P, Chatterjee K, Kretinsky J, Weininger M, Winkler T. Approximating values of generalized-reachability stochastic games. In: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science . Association for Computing Machinery; 2020:102-115. doi:10.1145/3373718.3394761' apa: 'Ashok, P., Chatterjee, K., Kretinsky, J., Weininger, M., & Winkler, T. (2020). Approximating values of generalized-reachability stochastic games. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 102–115). Saarbrücken, Germany: Association for Computing Machinery. https://doi.org/10.1145/3373718.3394761' chicago: Ashok, Pranav, Krishnendu Chatterjee, Jan Kretinsky, Maximilian Weininger, and Tobias Winkler. “Approximating Values of Generalized-Reachability Stochastic Games.” In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , 102–15. Association for Computing Machinery, 2020. https://doi.org/10.1145/3373718.3394761. ieee: P. Ashok, K. Chatterjee, J. Kretinsky, M. Weininger, and T. Winkler, “Approximating values of generalized-reachability stochastic games,” in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , Saarbrücken, Germany, 2020, pp. 102–115. ista: 'Ashok P, Chatterjee K, Kretinsky J, Weininger M, Winkler T. 2020. Approximating values of generalized-reachability stochastic games. Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science . LICS: Symposium on Logic in Computer Science, 102–115.' mla: Ashok, Pranav, et al. “Approximating Values of Generalized-Reachability Stochastic Games.” Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , Association for Computing Machinery, 2020, pp. 102–15, doi:10.1145/3373718.3394761. short: P. Ashok, K. Chatterjee, J. Kretinsky, M. Weininger, T. Winkler, in:, Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , Association for Computing Machinery, 2020, pp. 102–115. conference: end_date: 2020-07-11 location: Saarbrücken, Germany name: 'LICS: Symposium on Logic in Computer Science' start_date: 2020-07-08 date_created: 2020-06-14T22:00:48Z date_published: 2020-07-08T00:00:00Z date_updated: 2023-08-21T08:24:36Z day: '08' ddc: - '000' department: - _id: KrCh doi: 10.1145/3373718.3394761 ec_funded: 1 external_id: arxiv: - '1908.05106' isi: - '000665014900010' file: - access_level: open_access checksum: d0d0288fe991dd16cf5f02598b794240 content_type: application/pdf creator: dernst date_created: 2020-11-25T09:38:14Z date_updated: 2020-11-25T09:38:14Z file_id: '8804' file_name: 2020_LICS_Ashok.pdf file_size: 1001395 relation: main_file success: 1 file_date_updated: 2020-11-25T09:38:14Z has_accepted_license: '1' isi: 1 language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 102-115 project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' - _id: 25892FC0-B435-11E9-9278-68D0E5697425 grant_number: ICT15-003 name: Efficient Algorithms for Computer Aided Verification publication: 'Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science ' publication_identifier: isbn: - '9781450371049' publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: Approximating values of generalized-reachability stochastic games type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 year: '2020' ... --- _id: '8767' abstract: - lang: eng text: Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a color. A green node is rich in resources while a red node is poorer. More colors can represent a broader spectrum of resource qualities. For a population evolving according to the birth-death Moran model, the first question we address is which structures, identified by graph connectivity and graph coloring, are evolutionarily equivalent. We prove that all properly two-colored, undirected, regular graphs are evolutionarily equivalent (where “properly colored” means that no two neighbors have the same color). We then compare the effects of background heterogeneity on properly two-colored graphs to those with alternative schemes in which the colors are permuted. Finally, we discuss dynamic coloring as a model for spatiotemporal resource fluctuations, and we illustrate that random dynamic colorings often diminish the effects of background heterogeneity relative to a proper two-coloring. acknowledgement: 'We thank Igor Erovenko for many helpful comments on an earlier version of this paper. : Army Research Laboratory (grant W911NF-18-2-0265) (M.A.N.); the Bill & Melinda Gates Foundation (grant OPP1148627) (M.A.N.); the NVIDIA Corporation (A.M.). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.' article_number: e1008402 article_processing_charge: No article_type: original author: - first_name: Kamran full_name: Kaveh, Kamran last_name: Kaveh - first_name: Alex full_name: McAvoy, Alex last_name: McAvoy - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin A. full_name: Nowak, Martin A. last_name: Nowak citation: ama: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. The Moran process on 2-chromatic graphs. PLOS Computational Biology. 2020;16(11). doi:10.1371/journal.pcbi.1008402 apa: Kaveh, K., McAvoy, A., Chatterjee, K., & Nowak, M. A. (2020). The Moran process on 2-chromatic graphs. PLOS Computational Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1008402 chicago: Kaveh, Kamran, Alex McAvoy, Krishnendu Chatterjee, and Martin A. Nowak. “The Moran Process on 2-Chromatic Graphs.” PLOS Computational Biology. Public Library of Science, 2020. https://doi.org/10.1371/journal.pcbi.1008402. ieee: K. Kaveh, A. McAvoy, K. Chatterjee, and M. A. Nowak, “The Moran process on 2-chromatic graphs,” PLOS Computational Biology, vol. 16, no. 11. Public Library of Science, 2020. ista: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. 2020. The Moran process on 2-chromatic graphs. PLOS Computational Biology. 16(11), e1008402. mla: Kaveh, Kamran, et al. “The Moran Process on 2-Chromatic Graphs.” PLOS Computational Biology, vol. 16, no. 11, e1008402, Public Library of Science, 2020, doi:10.1371/journal.pcbi.1008402. short: K. Kaveh, A. McAvoy, K. Chatterjee, M.A. Nowak, PLOS Computational Biology 16 (2020). date_created: 2020-11-18T07:20:23Z date_published: 2020-11-05T00:00:00Z date_updated: 2023-08-22T12:49:18Z day: '05' ddc: - '000' department: - _id: KrCh doi: 10.1371/journal.pcbi.1008402 external_id: isi: - '000591317200004' file: - access_level: open_access checksum: 555456dd0e47bcf9e0994bcb95577e88 content_type: application/pdf creator: dernst date_created: 2020-11-18T07:26:10Z date_updated: 2020-11-18T07:26:10Z file_id: '8768' file_name: 2020_PlosCompBio_Kaveh.pdf file_size: 2498594 relation: main_file success: 1 file_date_updated: 2020-11-18T07:26:10Z has_accepted_license: '1' intvolume: ' 16' isi: 1 issue: '11' keyword: - Ecology - Modelling and Simulation - Computational Theory and Mathematics - Genetics - Ecology - Evolution - Behavior and Systematics - Molecular Biology - Cellular and Molecular Neuroscience language: - iso: eng month: '11' oa: 1 oa_version: Published Version publication: PLOS Computational Biology publication_identifier: eissn: - 1553-7358 issn: - 1553-734X publication_status: published publisher: Public Library of Science quality_controlled: '1' scopus_import: '1' status: public title: The Moran process on 2-chromatic graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 16 year: '2020' ... --- _id: '8789' abstract: - lang: eng text: Cooperation is a ubiquitous and beneficial behavioural trait despite being prone to exploitation by free-riders. Hence, cooperative populations are prone to invasions by selfish individuals. However, a population consisting of only free-riders typically does not survive. Thus, cooperators and free-riders often coexist in some proportion. An evolutionary version of a Snowdrift Game proved its efficiency in analysing this phenomenon. However, what if the system has already reached its stable state but was perturbed due to a change in environmental conditions? Then, individuals may have to re-learn their effective strategies. To address this, we consider behavioural mistakes in strategic choice execution, which we refer to as incompetence. Parametrising the propensity to make such mistakes allows for a mathematical description of learning. We compare strategies based on their relative strategic advantage relying on both fitness and learning factors. When strategies are learned at distinct rates, allowing learning according to a prescribed order is optimal. Interestingly, the strategy with the lowest strategic advantage should be learnt first if we are to optimise fitness over the learning path. Then, the differences between strategies are balanced out in order to minimise the effect of behavioural uncertainty. acknowledgement: "This work was supported by the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie Grant Agreement #754411, the Australian Research Council Discovery Grants DP160101236 and DP150100618, and the European Research Council Consolidator Grant 863818 (FoRM-SMArt).\r\nAuthors would like to thank Patrick McKinlay for his work on the preliminary results for this paper." article_number: '1945' article_processing_charge: No article_type: original author: - first_name: Maria full_name: Kleshnina, Maria id: 4E21749C-F248-11E8-B48F-1D18A9856A87 last_name: Kleshnina - first_name: Sabrina full_name: Streipert, Sabrina last_name: Streipert - first_name: Jerzy full_name: Filar, Jerzy last_name: Filar - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X citation: ama: Kleshnina M, Streipert S, Filar J, Chatterjee K. Prioritised learning in snowdrift-type games. Mathematics. 2020;8(11). doi:10.3390/math8111945 apa: Kleshnina, M., Streipert, S., Filar, J., & Chatterjee, K. (2020). Prioritised learning in snowdrift-type games. Mathematics. MDPI. https://doi.org/10.3390/math8111945 chicago: Kleshnina, Maria, Sabrina Streipert, Jerzy Filar, and Krishnendu Chatterjee. “Prioritised Learning in Snowdrift-Type Games.” Mathematics. MDPI, 2020. https://doi.org/10.3390/math8111945. ieee: M. Kleshnina, S. Streipert, J. Filar, and K. Chatterjee, “Prioritised learning in snowdrift-type games,” Mathematics, vol. 8, no. 11. MDPI, 2020. ista: Kleshnina M, Streipert S, Filar J, Chatterjee K. 2020. Prioritised learning in snowdrift-type games. Mathematics. 8(11), 1945. mla: Kleshnina, Maria, et al. “Prioritised Learning in Snowdrift-Type Games.” Mathematics, vol. 8, no. 11, 1945, MDPI, 2020, doi:10.3390/math8111945. short: M. Kleshnina, S. Streipert, J. Filar, K. Chatterjee, Mathematics 8 (2020). date_created: 2020-11-22T23:01:24Z date_published: 2020-11-04T00:00:00Z date_updated: 2023-08-22T13:25:45Z day: '04' ddc: - '000' department: - _id: KrCh doi: 10.3390/math8111945 ec_funded: 1 external_id: isi: - '000593962100001' file: - access_level: open_access checksum: 61cfcc3b35760656ce7a9385a4ace5d2 content_type: application/pdf creator: dernst date_created: 2020-11-23T13:06:30Z date_updated: 2020-11-23T13:06:30Z file_id: '8797' file_name: 2020_Mathematics_Kleshnina.pdf file_size: 565191 relation: main_file success: 1 file_date_updated: 2020-11-23T13:06:30Z has_accepted_license: '1' intvolume: ' 8' isi: 1 issue: '11' language: - iso: eng month: '11' oa: 1 oa_version: Published Version project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: Mathematics publication_identifier: eissn: - '22277390' publication_status: published publisher: MDPI quality_controlled: '1' scopus_import: '1' status: public title: Prioritised learning in snowdrift-type games tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 8 year: '2020' ... --- _id: '8788' abstract: - lang: eng text: 'We consider a real-time setting where an environment releases sequences of firm-deadline tasks, and an online scheduler chooses on-the-fly the ones to execute on a single processor so as to maximize cumulated utility. The competitive ratio is a well-known performance measure for the scheduler: it gives the worst-case ratio, among all possible choices for the environment, of the cumulated utility of the online scheduler versus an offline scheduler that knows these choices in advance. Traditionally, competitive analysis is performed by hand, while automated techniques are rare and only handle static environments with independent tasks. We present a quantitative-verification framework for precedence-aware competitive analysis, where task releases may depend on preceding scheduling choices, i.e., the environment can respond to scheduling decisions dynamically . We consider two general classes of precedences: 1) follower precedences force the release of a dependent task upon the completion of a set of precursor tasks, while and 2) pairing precedences modify the characteristics of a dependent task provided the completion of a set of precursor tasks. Precedences make competitive analysis challenging, as the online and offline schedulers operate on diverging sequences. We make a formal presentation of our framework, and use a GPU-based implementation to analyze ten well-known schedulers on precedence-based application examples taken from the existing literature: 1) a handshake protocol (HP); 2) network packet-switching; 3) query scheduling (QS); and 4) a sporadic-interrupt setting. Our experimental results show that precedences and task parameters can vary drastically the best scheduler. Our framework thus supports application designers in choosing the best scheduler among a given set automatically.' acknowledgement: 'This work was supported by the Austrian Science Foundation (FWF) under the NFN RiSE/SHiNE under Grant S11405 and Grant S11407. This article was presented in the International Conference on Embedded Software 2020 and appears as part of the ESWEEK-TCAD special issue. ' article_processing_charge: No article_type: original author: - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 - first_name: Nico full_name: Schaumberger, Nico last_name: Schaumberger - first_name: Ulrich full_name: Schmid, Ulrich last_name: Schmid - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X citation: ama: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. Precedence-aware automated competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2020;39(11):3981-3992. doi:10.1109/TCAD.2020.3012803 apa: Pavlogiannis, A., Schaumberger, N., Schmid, U., & Chatterjee, K. (2020). Precedence-aware automated competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. IEEE. https://doi.org/10.1109/TCAD.2020.3012803 chicago: Pavlogiannis, Andreas, Nico Schaumberger, Ulrich Schmid, and Krishnendu Chatterjee. “Precedence-Aware Automated Competitive Analysis of Real-Time Scheduling.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. IEEE, 2020. https://doi.org/10.1109/TCAD.2020.3012803. ieee: A. Pavlogiannis, N. Schaumberger, U. Schmid, and K. Chatterjee, “Precedence-aware automated competitive analysis of real-time scheduling,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 11. IEEE, pp. 3981–3992, 2020. ista: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. 2020. Precedence-aware automated competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 39(11), 3981–3992. mla: Pavlogiannis, Andreas, et al. “Precedence-Aware Automated Competitive Analysis of Real-Time Scheduling.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 11, IEEE, 2020, pp. 3981–92, doi:10.1109/TCAD.2020.3012803. short: A. Pavlogiannis, N. Schaumberger, U. Schmid, K. Chatterjee, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 3981–3992. date_created: 2020-11-22T23:01:24Z date_published: 2020-11-01T00:00:00Z date_updated: 2023-08-22T13:27:05Z day: '01' department: - _id: KrCh doi: 10.1109/TCAD.2020.3012803 external_id: isi: - '000587712700069' intvolume: ' 39' isi: 1 issue: '11' language: - iso: eng month: '11' oa_version: None page: 3981-3992 project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory publication: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems publication_identifier: eissn: - '19374151' issn: - '02780070' publication_status: published publisher: IEEE quality_controlled: '1' scopus_import: '1' status: public title: Precedence-aware automated competitive analysis of real-time scheduling type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 39 year: '2020' ... --- _id: '9197' abstract: - lang: eng text: In this paper we introduce and study all-pay bidding games, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in the graph and assign budgets to the two players. Each turn, each player submits a sealed legal bid (non-negative and below their remaining budget), which is deducted from their budget and the highest bidder moves the token onto an adjacent vertex. The game ends once a sink is reached, and Player 1 pays Player 2 the outcome that is associated with the sink. The players attempt to maximize their expected outcome. Our games model settings where effort (of no inherent value) needs to be invested in an ongoing and stateful manner. On the negative side, we show that even in simple games on DAGs, optimal strategies may require a distribution over bids with infinite support. A central quantity in bidding games is the ratio of the players budgets. On the positive side, we show a simple FPTAS for DAGs, that, for each budget ratio, outputs an approximation for the optimal strategy for that ratio. We also implement it, show that it performs well, and suggests interesting properties of these games. Then, given an outcome c, we show an algorithm for finding the necessary and sufficient initial ratio for guaranteeing outcome c with probability 1 and a strategy ensuring such. Finally, while the general case has not previously been studied, solving the specific game in which Player 1 wins iff he wins the first two auctions, has been long stated as an open question, which we solve. acknowledgement: This research was supported by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship). article_processing_charge: No article_type: original author: - first_name: Guy full_name: Avni, Guy id: 463C8BC2-F248-11E8-B48F-1D18A9856A87 last_name: Avni orcid: 0000-0001-5588-8287 - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Josef full_name: Tkadlec, Josef id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87 last_name: Tkadlec orcid: 0000-0002-1097-9684 citation: ama: Avni G, Ibsen-Jensen R, Tkadlec J. All-pay bidding games on graphs. Proceedings of the AAAI Conference on Artificial Intelligence. 2020;34(02):1798-1805. doi:10.1609/aaai.v34i02.5546 apa: 'Avni, G., Ibsen-Jensen, R., & Tkadlec, J. (2020). All-pay bidding games on graphs. Proceedings of the AAAI Conference on Artificial Intelligence. New York, NY, United States: Association for the Advancement of Artificial Intelligence. https://doi.org/10.1609/aaai.v34i02.5546' chicago: Avni, Guy, Rasmus Ibsen-Jensen, and Josef Tkadlec. “All-Pay Bidding Games on Graphs.” Proceedings of the AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence, 2020. https://doi.org/10.1609/aaai.v34i02.5546. ieee: G. Avni, R. Ibsen-Jensen, and J. Tkadlec, “All-pay bidding games on graphs,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 02. Association for the Advancement of Artificial Intelligence, pp. 1798–1805, 2020. ista: Avni G, Ibsen-Jensen R, Tkadlec J. 2020. All-pay bidding games on graphs. Proceedings of the AAAI Conference on Artificial Intelligence. 34(02), 1798–1805. mla: Avni, Guy, et al. “All-Pay Bidding Games on Graphs.” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 02, Association for the Advancement of Artificial Intelligence, 2020, pp. 1798–805, doi:10.1609/aaai.v34i02.5546. short: G. Avni, R. Ibsen-Jensen, J. Tkadlec, Proceedings of the AAAI Conference on Artificial Intelligence 34 (2020) 1798–1805. conference: end_date: 2020-02-12 location: New York, NY, United States name: 'AAAI: Conference on Artificial Intelligence' start_date: 2020-02-07 date_created: 2021-02-25T09:05:18Z date_published: 2020-04-03T00:00:00Z date_updated: 2023-09-05T12:40:00Z day: '03' department: - _id: ToHe - _id: KrCh doi: 10.1609/aaai.v34i02.5546 external_id: arxiv: - '1911.08360' intvolume: ' 34' issue: '02' language: - iso: eng month: '04' oa_version: Preprint page: 1798-1805 project: - _id: 25F2ACDE-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Rigorous Systems Engineering - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize - _id: 264B3912-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02369 name: Formal Methods meets Algorithmic Game Theory publication: Proceedings of the AAAI Conference on Artificial Intelligence publication_identifier: eissn: - 2374-3468 isbn: - '9781577358350' issn: - 2159-5399 publication_status: published publisher: Association for the Advancement of Artificial Intelligence quality_controlled: '1' scopus_import: '1' status: public title: All-pay bidding games on graphs type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 34 year: '2020' ... --- _id: '7343' abstract: - lang: eng text: Coinfections with multiple pathogens can result in complex within‐host dynamics affecting virulence and transmission. While multiple infections are intensively studied in solitary hosts, it is so far unresolved how social host interactions interfere with pathogen competition, and if this depends on coinfection diversity. We studied how the collective disease defences of ants – their social immunity – influence pathogen competition in coinfections of same or different fungal pathogen species. Social immunity reduced virulence for all pathogen combinations, but interfered with spore production only in different‐species coinfections. Here, it decreased overall pathogen sporulation success while increasing co‐sporulation on individual cadavers and maintaining a higher pathogen diversity at the community level. Mathematical modelling revealed that host sanitary care alone can modulate competitive outcomes between pathogens, giving advantage to fast‐germinating, thus less grooming‐sensitive ones. Host social interactions can hence modulate infection dynamics in coinfected group members, thereby altering pathogen communities at the host level and population level. acknowledged_ssus: - _id: LifeSc acknowledgement: "We thank Bernhardt Steinwender and Jorgen Eilenberg for the fungal strains, Xavier Espadaler, Mireia Diaz, Christiane Wanke, Lumi Viljakainen and the Social Immunity Team at IST Austria, for help with ant collection, and Wanda Gorecka and Gertraud Stift of the IST Austria Life Science Facility for technical support. We are thankful to Dieter Ebert for input at all stages of the project, Roger Mundry for statistical advice, Hinrich Schulenburg, Paul Schmid-Hempel, Yuko\r\nUlrich and Joachim Kurtz for project discussion, Bor Kavcic for advice on growth curves, Marcus Roper for advice on modelling work and comments on the manuscript, as well as Marjon de Vos, Weini Huang and the Social Immunity Team for comments on the manuscript.\r\nThis study was funded by the German Research Foundation (DFG) within the Priority Programme 1399 Host-parasite Coevolution (CR 118/3 to S.C.) and the People Programme\r\n(Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no 291734 (ISTFELLOW to B.M.). " article_processing_charge: Yes (via OA deal) article_type: letter_note author: - first_name: Barbara full_name: Milutinovic, Barbara id: 2CDC32B8-F248-11E8-B48F-1D18A9856A87 last_name: Milutinovic orcid: 0000-0002-8214-4758 - first_name: Miriam full_name: Stock, Miriam id: 42462816-F248-11E8-B48F-1D18A9856A87 last_name: Stock - first_name: Anna V full_name: Grasse, Anna V id: 406F989C-F248-11E8-B48F-1D18A9856A87 last_name: Grasse - first_name: Elisabeth full_name: Naderlinger, Elisabeth id: 31757262-F248-11E8-B48F-1D18A9856A87 last_name: Naderlinger - first_name: Christian full_name: Hilbe, Christian id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87 last_name: Hilbe orcid: 0000-0001-5116-955X - first_name: Sylvia full_name: Cremer, Sylvia id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87 last_name: Cremer orcid: 0000-0002-2193-3868 citation: ama: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. Social immunity modulates competition between coinfecting pathogens. Ecology Letters. 2020;23(3):565-574. doi:10.1111/ele.13458 apa: Milutinovic, B., Stock, M., Grasse, A. V., Naderlinger, E., Hilbe, C., & Cremer, S. (2020). Social immunity modulates competition between coinfecting pathogens. Ecology Letters. Wiley. https://doi.org/10.1111/ele.13458 chicago: Milutinovic, Barbara, Miriam Stock, Anna V Grasse, Elisabeth Naderlinger, Christian Hilbe, and Sylvia Cremer. “Social Immunity Modulates Competition between Coinfecting Pathogens.” Ecology Letters. Wiley, 2020. https://doi.org/10.1111/ele.13458. ieee: B. Milutinovic, M. Stock, A. V. Grasse, E. Naderlinger, C. Hilbe, and S. Cremer, “Social immunity modulates competition between coinfecting pathogens,” Ecology Letters, vol. 23, no. 3. Wiley, pp. 565–574, 2020. ista: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. 2020. Social immunity modulates competition between coinfecting pathogens. Ecology Letters. 23(3), 565–574. mla: Milutinovic, Barbara, et al. “Social Immunity Modulates Competition between Coinfecting Pathogens.” Ecology Letters, vol. 23, no. 3, Wiley, 2020, pp. 565–74, doi:10.1111/ele.13458. short: B. Milutinovic, M. Stock, A.V. Grasse, E. Naderlinger, C. Hilbe, S. Cremer, Ecology Letters 23 (2020) 565–574. date_created: 2020-01-20T13:32:12Z date_published: 2020-03-01T00:00:00Z date_updated: 2023-09-05T16:04:49Z day: '01' ddc: - '570' department: - _id: SyCr - _id: KrCh doi: 10.1111/ele.13458 ec_funded: 1 external_id: isi: - '000507515900001' file: - access_level: open_access checksum: 0cd8be386fa219db02845b7c3991ce04 content_type: application/pdf creator: dernst date_created: 2020-11-19T11:27:10Z date_updated: 2020-11-19T11:27:10Z file_id: '8776' file_name: 2020_EcologyLetters_Milutinovic.pdf file_size: 561749 relation: main_file success: 1 file_date_updated: 2020-11-19T11:27:10Z has_accepted_license: '1' intvolume: ' 23' isi: 1 issue: '3' language: - iso: eng license: https://creativecommons.org/licenses/by-nc/4.0/ month: '03' oa: 1 oa_version: Published Version page: 565-574 project: - _id: 25681D80-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '291734' name: International IST Postdoc Fellowship Programme - _id: 25DAF0B2-B435-11E9-9278-68D0E5697425 grant_number: CR-118/3-1 name: Host-Parasite Coevolution publication: Ecology Letters publication_identifier: eissn: - 1461-0248 issn: - 1461-023X publication_status: published publisher: Wiley quality_controlled: '1' related_material: link: - description: News on IST Homepage relation: press_release url: https://ist.ac.at/en/news/social-ants-shapes-disease-outcome/ record: - id: '13060' relation: research_data status: public scopus_import: '1' status: public title: Social immunity modulates competition between coinfecting pathogens tmp: image: /images/cc_by_nc.png legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) short: CC BY-NC (4.0) type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 23 year: '2020' ... --- _id: '13060' abstract: - lang: eng text: Coinfections with multiple pathogens can result in complex within-host dynamics affecting virulence and transmission. Whilst multiple infections are intensively studied in solitary hosts, it is so far unresolved how social host interactions interfere with pathogen competition, and if this depends on coinfection diversity. We studied how the collective disease defenses of ants – their social immunity ­– influence pathogen competition in coinfections of same or different fungal pathogen species. Social immunity reduced virulence for all pathogen combinations, but interfered with spore production only in different-species coinfections. Here, it decreased overall pathogen sporulation success, whilst simultaneously increasing co-sporulation on individual cadavers and maintaining a higher pathogen diversity at the community-level. Mathematical modeling revealed that host sanitary care alone can modulate competitive outcomes between pathogens, giving advantage to fast-germinating, thus less grooming-sensitive ones. Host social interactions can hence modulate infection dynamics in coinfected group members, thereby altering pathogen communities at the host- and population-level. article_processing_charge: No author: - first_name: Barbara full_name: Milutinovic, Barbara id: 2CDC32B8-F248-11E8-B48F-1D18A9856A87 last_name: Milutinovic orcid: 0000-0002-8214-4758 - first_name: Miriam full_name: Stock, Miriam id: 42462816-F248-11E8-B48F-1D18A9856A87 last_name: Stock - first_name: Anna V full_name: Grasse, Anna V id: 406F989C-F248-11E8-B48F-1D18A9856A87 last_name: Grasse - first_name: Elisabeth full_name: Naderlinger, Elisabeth id: 31757262-F248-11E8-B48F-1D18A9856A87 last_name: Naderlinger - first_name: Christian full_name: Hilbe, Christian id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87 last_name: Hilbe orcid: 0000-0001-5116-955X - first_name: Sylvia full_name: Cremer, Sylvia id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87 last_name: Cremer orcid: 0000-0002-2193-3868 citation: ama: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. Social immunity modulates competition between coinfecting pathogens. 2020. doi:10.5061/DRYAD.CRJDFN318 apa: Milutinovic, B., Stock, M., Grasse, A. V., Naderlinger, E., Hilbe, C., & Cremer, S. (2020). Social immunity modulates competition between coinfecting pathogens. Dryad. https://doi.org/10.5061/DRYAD.CRJDFN318 chicago: Milutinovic, Barbara, Miriam Stock, Anna V Grasse, Elisabeth Naderlinger, Christian Hilbe, and Sylvia Cremer. “Social Immunity Modulates Competition between Coinfecting Pathogens.” Dryad, 2020. https://doi.org/10.5061/DRYAD.CRJDFN318. ieee: B. Milutinovic, M. Stock, A. V. Grasse, E. Naderlinger, C. Hilbe, and S. Cremer, “Social immunity modulates competition between coinfecting pathogens.” Dryad, 2020. ista: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. 2020. Social immunity modulates competition between coinfecting pathogens, Dryad, 10.5061/DRYAD.CRJDFN318. mla: Milutinovic, Barbara, et al. Social Immunity Modulates Competition between Coinfecting Pathogens. Dryad, 2020, doi:10.5061/DRYAD.CRJDFN318. short: B. Milutinovic, M. Stock, A.V. Grasse, E. Naderlinger, C. Hilbe, S. Cremer, (2020). date_created: 2023-05-23T16:11:22Z date_published: 2020-12-19T00:00:00Z date_updated: 2023-09-05T16:04:48Z day: '19' ddc: - '570' department: - _id: SyCr - _id: KrCh doi: 10.5061/DRYAD.CRJDFN318 license: https://creativecommons.org/publicdomain/zero/1.0/ main_file_link: - open_access: '1' url: https://doi.org/10.5061/dryad.crjdfn318 month: '12' oa: 1 oa_version: Published Version publisher: Dryad related_material: record: - id: '7343' relation: used_in_publication status: public status: public title: Social immunity modulates competition between coinfecting pathogens tmp: image: /images/cc_0.png legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode name: Creative Commons Public Domain Dedication (CC0 1.0) short: CC0 (1.0) type: research_data_reference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2020' ... --- _id: '8193' abstract: - lang: eng text: 'Multiple-environment Markov decision processes (MEMDPs) are MDPs equipped with not one, but multiple probabilistic transition functions, which represent the various possible unknown environments. While the previous research on MEMDPs focused on theoretical properties for long-run average payoff, we study them with discounted-sum payoff and focus on their practical advantages and applications. MEMDPs can be viewed as a special case of Partially observable and Mixed observability MDPs: the state of the system is perfectly observable, but not the environment. We show that the specific structure of MEMDPs allows for more efficient algorithmic analysis, in particular for faster belief updates. We demonstrate the applicability of MEMDPs in several domains. In particular, we formalize the sequential decision-making approach to contextual recommendation systems as MEMDPs and substantially improve over the previous MDP approach.' acknowledgement: Krishnendu Chatterjee is supported by the Austrian ScienceFund (FWF) NFN Grant No. S11407-N23 (RiSE/SHiNE),and COST Action GAMENET. Petr Novotn ́y is supported bythe Czech Science Foundation grant No. GJ19-15134Y. article_processing_charge: No author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik - first_name: Deep full_name: Karkhanis, Deep last_name: Karkhanis - first_name: Petr full_name: Novotný, Petr id: 3CC3B868-F248-11E8-B48F-1D18A9856A87 last_name: Novotný - first_name: Amélie full_name: Royer, Amélie id: 3811D890-F248-11E8-B48F-1D18A9856A87 last_name: Royer orcid: 0000-0002-8407-0705 citation: ama: 'Chatterjee K, Chmelik M, Karkhanis D, Novotný P, Royer A. Multiple-environment Markov decision processes: Efficient analysis and applications. In: Proceedings of the 30th International Conference on Automated Planning and Scheduling. Vol 30. Association for the Advancement of Artificial Intelligence; 2020:48-56.' apa: 'Chatterjee, K., Chmelik, M., Karkhanis, D., Novotný, P., & Royer, A. (2020). Multiple-environment Markov decision processes: Efficient analysis and applications. In Proceedings of the 30th International Conference on Automated Planning and Scheduling (Vol. 30, pp. 48–56). Nancy, France: Association for the Advancement of Artificial Intelligence.' chicago: 'Chatterjee, Krishnendu, Martin Chmelik, Deep Karkhanis, Petr Novotný, and Amélie Royer. “Multiple-Environment Markov Decision Processes: Efficient Analysis and Applications.” In Proceedings of the 30th International Conference on Automated Planning and Scheduling, 30:48–56. Association for the Advancement of Artificial Intelligence, 2020.' ieee: 'K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, and A. Royer, “Multiple-environment Markov decision processes: Efficient analysis and applications,” in Proceedings of the 30th International Conference on Automated Planning and Scheduling, Nancy, France, 2020, vol. 30, pp. 48–56.' ista: 'Chatterjee K, Chmelik M, Karkhanis D, Novotný P, Royer A. 2020. Multiple-environment Markov decision processes: Efficient analysis and applications. Proceedings of the 30th International Conference on Automated Planning and Scheduling. ICAPS: International Conference on Automated Planning and Scheduling vol. 30, 48–56.' mla: 'Chatterjee, Krishnendu, et al. “Multiple-Environment Markov Decision Processes: Efficient Analysis and Applications.” Proceedings of the 30th International Conference on Automated Planning and Scheduling, vol. 30, Association for the Advancement of Artificial Intelligence, 2020, pp. 48–56.' short: K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, A. Royer, in:, Proceedings of the 30th International Conference on Automated Planning and Scheduling, Association for the Advancement of Artificial Intelligence, 2020, pp. 48–56. conference: end_date: 2020-10-30 location: Nancy, France name: 'ICAPS: International Conference on Automated Planning and Scheduling' start_date: 2020-10-26 date_created: 2020-08-02T22:00:58Z date_published: 2020-06-01T00:00:00Z date_updated: 2023-09-07T13:16:18Z day: '01' department: - _id: KrCh intvolume: ' 30' language: - iso: eng month: '06' oa_version: None page: 48-56 project: - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory publication: Proceedings of the 30th International Conference on Automated Planning and Scheduling publication_identifier: eissn: - '23340843' issn: - '23340835' publication_status: published publisher: Association for the Advancement of Artificial Intelligence quality_controlled: '1' related_material: record: - id: '8390' relation: dissertation_contains status: public scopus_import: '1' status: public title: 'Multiple-environment Markov decision processes: Efficient analysis and applications' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 30 year: '2020' ... --- _id: '8272' abstract: - lang: eng text: We study turn-based stochastic zero-sum games with lexicographic preferences over reachability and safety objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as angelic and demonic non-determinism. Lexicographic order allows to consider multiple objectives with a strict preference order over the satisfaction of the objectives. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. We establish determinacy of such games and present strategy and computational complexity results. For strategy complexity, we show that lexicographically optimal strategies exist that are deterministic and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP , matching the current known bound for single objectives; and in general the decision problem is PSPACE -hard and can be solved in NEXPTIME∩coNEXPTIME . We present an algorithm that computes the lexicographically optimal strategies via a reduction to computation of optimal strategies in a sequence of single-objectives games. We have implemented our algorithm and report experimental results on various case studies. alternative_title: - LNCS article_processing_charge: No author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Joost P full_name: Katoen, Joost P id: 4524F760-F248-11E8-B48F-1D18A9856A87 last_name: Katoen - first_name: Maximilian full_name: Weininger, Maximilian last_name: Weininger - first_name: Tobias full_name: Winkler, Tobias last_name: Winkler citation: ama: 'Chatterjee K, Katoen JP, Weininger M, Winkler T. Stochastic games with lexicographic reachability-safety objectives. In: International Conference on Computer Aided Verification. Vol 12225. Springer Nature; 2020:398-420. doi:10.1007/978-3-030-53291-8_21' apa: Chatterjee, K., Katoen, J. P., Weininger, M., & Winkler, T. (2020). Stochastic games with lexicographic reachability-safety objectives. In International Conference on Computer Aided Verification (Vol. 12225, pp. 398–420). Springer Nature. https://doi.org/10.1007/978-3-030-53291-8_21 chicago: Chatterjee, Krishnendu, Joost P Katoen, Maximilian Weininger, and Tobias Winkler. “Stochastic Games with Lexicographic Reachability-Safety Objectives.” In International Conference on Computer Aided Verification, 12225:398–420. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-53291-8_21. ieee: K. Chatterjee, J. P. Katoen, M. Weininger, and T. Winkler, “Stochastic games with lexicographic reachability-safety objectives,” in International Conference on Computer Aided Verification, 2020, vol. 12225, pp. 398–420. ista: 'Chatterjee K, Katoen JP, Weininger M, Winkler T. 2020. Stochastic games with lexicographic reachability-safety objectives. International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 12225, 398–420.' mla: Chatterjee, Krishnendu, et al. “Stochastic Games with Lexicographic Reachability-Safety Objectives.” International Conference on Computer Aided Verification, vol. 12225, Springer Nature, 2020, pp. 398–420, doi:10.1007/978-3-030-53291-8_21. short: K. Chatterjee, J.P. Katoen, M. Weininger, T. Winkler, in:, International Conference on Computer Aided Verification, Springer Nature, 2020, pp. 398–420. conference: name: 'CAV: Computer Aided Verification' date_created: 2020-08-16T22:00:58Z date_published: 2020-07-14T00:00:00Z date_updated: 2023-10-03T11:36:13Z day: '14' ddc: - '000' department: - _id: KrCh doi: 10.1007/978-3-030-53291-8_21 ec_funded: 1 external_id: arxiv: - '2005.04018' isi: - '000695272500021' file: - access_level: open_access checksum: 093d4788d7d5b2ce0ffe64fbe7820043 content_type: application/pdf creator: dernst date_created: 2020-08-17T11:32:44Z date_updated: 2020-08-17T11:32:44Z file_id: '8276' file_name: 2020_LNCS_CAV_Chatterjee.pdf file_size: 625056 relation: main_file success: 1 file_date_updated: 2020-08-17T11:32:44Z has_accepted_license: '1' intvolume: ' 12225' isi: 1 language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 398-420 project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' - _id: 25892FC0-B435-11E9-9278-68D0E5697425 grant_number: ICT15-003 name: Efficient Algorithms for Computer Aided Verification publication: International Conference on Computer Aided Verification publication_identifier: eissn: - '16113349' isbn: - '9783030532901' issn: - '03029743' publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '12738' relation: later_version status: public scopus_import: '1' status: public title: Stochastic games with lexicographic reachability-safety objectives tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 12225 year: '2020' ... --- _id: '8671' abstract: - lang: eng text: 'We study relations between evidence theory and S-approximation spaces. Both theories have their roots in the analysis of Dempsterchr(''39'')s multivalued mappings and lower and upper probabilities, and have close relations to rough sets. We show that an S-approximation space, satisfying a monotonicity condition, can induce a natural belief structure which is a fundamental block in evidence theory. We also demonstrate that one can induce a natural belief structure on one set, given a belief structure on another set, if the two sets are related by a partial monotone S-approximation space. ' acknowledgement: We are very grateful to the anonymous reviewer for detailed comments and suggestions that significantly improved the presentation of this paper. The research was partially supported by a DOC fellowship of the Austrian Academy of Sciences. article_processing_charge: No article_type: original author: - first_name: A. full_name: Shakiba, A. last_name: Shakiba - first_name: Amir Kafshdar full_name: Goharshady, Amir Kafshdar id: 391365CE-F248-11E8-B48F-1D18A9856A87 last_name: Goharshady orcid: 0000-0003-1702-6584 - first_name: M.R. full_name: Hooshmandasl, M.R. last_name: Hooshmandasl - first_name: M. full_name: Alambardar Meybodi, M. last_name: Alambardar Meybodi citation: ama: Shakiba A, Goharshady AK, Hooshmandasl MR, Alambardar Meybodi M. A note on belief structures and s-approximation spaces. Iranian Journal of Mathematical Sciences and Informatics. 2020;15(2):117-128. doi:10.29252/ijmsi.15.2.117 apa: Shakiba, A., Goharshady, A. K., Hooshmandasl, M. R., & Alambardar Meybodi, M. (2020). A note on belief structures and s-approximation spaces. Iranian Journal of Mathematical Sciences and Informatics. Iranian Academic Center for Education, Culture and Research. https://doi.org/10.29252/ijmsi.15.2.117 chicago: Shakiba, A., Amir Kafshdar Goharshady, M.R. Hooshmandasl, and M. Alambardar Meybodi. “A Note on Belief Structures and S-Approximation Spaces.” Iranian Journal of Mathematical Sciences and Informatics. Iranian Academic Center for Education, Culture and Research, 2020. https://doi.org/10.29252/ijmsi.15.2.117. ieee: A. Shakiba, A. K. Goharshady, M. R. Hooshmandasl, and M. Alambardar Meybodi, “A note on belief structures and s-approximation spaces,” Iranian Journal of Mathematical Sciences and Informatics, vol. 15, no. 2. Iranian Academic Center for Education, Culture and Research, pp. 117–128, 2020. ista: Shakiba A, Goharshady AK, Hooshmandasl MR, Alambardar Meybodi M. 2020. A note on belief structures and s-approximation spaces. Iranian Journal of Mathematical Sciences and Informatics. 15(2), 117–128. mla: Shakiba, A., et al. “A Note on Belief Structures and S-Approximation Spaces.” Iranian Journal of Mathematical Sciences and Informatics, vol. 15, no. 2, Iranian Academic Center for Education, Culture and Research, 2020, pp. 117–28, doi:10.29252/ijmsi.15.2.117. short: A. Shakiba, A.K. Goharshady, M.R. Hooshmandasl, M. Alambardar Meybodi, Iranian Journal of Mathematical Sciences and Informatics 15 (2020) 117–128. date_created: 2020-10-18T22:01:36Z date_published: 2020-10-01T00:00:00Z date_updated: 2023-10-16T09:25:00Z day: '01' ddc: - '000' department: - _id: KrCh doi: 10.29252/ijmsi.15.2.117 external_id: arxiv: - '1805.10672' file: - access_level: open_access checksum: f299661a6d51cda6d255a76be696f48d content_type: application/pdf creator: dernst date_created: 2020-10-19T11:14:20Z date_updated: 2020-10-19T11:14:20Z file_id: '8676' file_name: 2020_ijmsi_Shakiba_accepted.pdf file_size: 261688 relation: main_file success: 1 file_date_updated: 2020-10-19T11:14:20Z has_accepted_license: '1' intvolume: ' 15' issue: '2' language: - iso: eng month: '10' oa: 1 oa_version: Submitted Version page: 117-128 project: - _id: 267066CE-B435-11E9-9278-68D0E5697425 name: Quantitative Analysis of Probablistic Systems with a focus on Crypto-currencies publication: Iranian Journal of Mathematical Sciences and Informatics publication_identifier: eissn: - 2008-9473 issn: - 1735-4463 publication_status: published publisher: Iranian Academic Center for Education, Culture and Research quality_controlled: '1' scopus_import: '1' status: public title: A note on belief structures and s-approximation spaces type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 15 year: '2020' ... --- _id: '7212' abstract: - lang: eng text: The fixation probability of a single mutant invading a population of residents is among the most widely-studied quantities in evolutionary dynamics. Amplifiers of natural selection are population structures that increase the fixation probability of advantageous mutants, compared to well-mixed populations. Extensive studies have shown that many amplifiers exist for the Birth-death Moran process, some of them substantially increasing the fixation probability or even guaranteeing fixation in the limit of large population size. On the other hand, no amplifiers are known for the death-Birth Moran process, and computer-assisted exhaustive searches have failed to discover amplification. In this work we resolve this disparity, by showing that any amplification under death-Birth updating is necessarily bounded and transient. Our boundedness result states that even if a population structure does amplify selection, the resulting fixation probability is close to that of the well-mixed population. Our transience result states that for any population structure there exists a threshold r⋆ such that the population structure ceases to amplify selection if the mutant fitness advantage r is larger than r⋆. Finally, we also extend the above results to δ-death-Birth updating, which is a combination of Birth-death and death-Birth updating. On the positive side, we identify population structures that maintain amplification for a wide range of values r and δ. These results demonstrate that amplification of natural selection depends on the specific mechanisms of the evolutionary process. article_number: e1007494 article_processing_charge: No article_type: original author: - first_name: Josef full_name: Tkadlec, Josef id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87 last_name: Tkadlec orcid: 0000-0002-1097-9684 - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin A. full_name: Nowak, Martin A. last_name: Nowak citation: ama: Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Limits on amplifiers of natural selection under death-Birth updating. PLoS computational biology. 2020;16. doi:10.1371/journal.pcbi.1007494 apa: Tkadlec, J., Pavlogiannis, A., Chatterjee, K., & Nowak, M. A. (2020). Limits on amplifiers of natural selection under death-Birth updating. PLoS Computational Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1007494 chicago: Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. “Limits on Amplifiers of Natural Selection under Death-Birth Updating.” PLoS Computational Biology. Public Library of Science, 2020. https://doi.org/10.1371/journal.pcbi.1007494. ieee: J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Limits on amplifiers of natural selection under death-Birth updating,” PLoS computational biology, vol. 16. Public Library of Science, 2020. ista: Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. 2020. Limits on amplifiers of natural selection under death-Birth updating. PLoS computational biology. 16, e1007494. mla: Tkadlec, Josef, et al. “Limits on Amplifiers of Natural Selection under Death-Birth Updating.” PLoS Computational Biology, vol. 16, e1007494, Public Library of Science, 2020, doi:10.1371/journal.pcbi.1007494. short: J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational Biology 16 (2020). date_created: 2019-12-23T13:45:11Z date_published: 2020-01-17T00:00:00Z date_updated: 2023-10-17T12:29:47Z day: '17' ddc: - '000' department: - _id: KrCh doi: 10.1371/journal.pcbi.1007494 ec_funded: 1 external_id: arxiv: - '1906.02785' isi: - '000510916500025' file: - access_level: open_access checksum: ce32ee2d2f53aed832f78bbd47e882df content_type: application/pdf creator: dernst date_created: 2020-02-03T07:32:42Z date_updated: 2020-07-14T12:47:53Z file_id: '7441' file_name: 2020_PlosCompBio_Tkadlec.pdf file_size: 1817531 relation: main_file file_date_updated: 2020-07-14T12:47:53Z has_accepted_license: '1' intvolume: ' 16' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version project: - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory publication: PLoS computational biology publication_identifier: eissn: - '15537358' publication_status: published publisher: Public Library of Science quality_controlled: '1' related_material: record: - id: '7196' relation: part_of_dissertation status: public scopus_import: '1' status: public title: Limits on amplifiers of natural selection under death-Birth updating tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 16 year: '2020' ... --- _id: '7196' abstract: - lang: eng text: 'In this thesis we study certain mathematical aspects of evolution. The two primary forces that drive an evolutionary process are mutation and selection. Mutation generates new variants in a population. Selection chooses among the variants depending on the reproductive rates of individuals. Evolutionary processes are intrinsically random – a new mutation that is initially present in the population at low frequency can go extinct, even if it confers a reproductive advantage. The overall rate of evolution is largely determined by two quantities: the probability that an invading advantageous mutation spreads through the population (called fixation probability) and the time until it does so (called fixation time). Both those quantities crucially depend not only on the strength of the invading mutation but also on the population structure. In this thesis, we aim to understand how the underlying population structure affects the overall rate of evolution. Specifically, we study population structures that increase the fixation probability of advantageous mutants (called amplifiers of selection). Broadly speaking, our results are of three different types: We present various strong amplifiers, we identify regimes under which only limited amplification is feasible, and we propose population structures that provide different tradeoffs between high fixation probability and short fixation time.' alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Josef full_name: Tkadlec, Josef id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87 last_name: Tkadlec orcid: 0000-0002-1097-9684 citation: ama: Tkadlec J. A role of graphs in evolutionary processes. 2020. doi:10.15479/AT:ISTA:7196 apa: Tkadlec, J. (2020). A role of graphs in evolutionary processes. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7196 chicago: Tkadlec, Josef. “A Role of Graphs in Evolutionary Processes.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7196. ieee: J. Tkadlec, “A role of graphs in evolutionary processes,” Institute of Science and Technology Austria, 2020. ista: Tkadlec J. 2020. A role of graphs in evolutionary processes. Institute of Science and Technology Austria. mla: Tkadlec, Josef. A Role of Graphs in Evolutionary Processes. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7196. short: J. Tkadlec, A Role of Graphs in Evolutionary Processes, Institute of Science and Technology Austria, 2020. date_created: 2019-12-20T12:26:36Z date_published: 2020-01-12T00:00:00Z date_updated: 2023-10-17T12:29:46Z day: '12' ddc: - '519' degree_awarded: PhD department: - _id: KrCh - _id: GradSch doi: 10.15479/AT:ISTA:7196 file: - access_level: closed checksum: 451f8e64b0eb26bf297644ac72bfcbe9 content_type: application/zip creator: jtkadlec date_created: 2020-01-12T11:49:49Z date_updated: 2020-07-14T12:47:52Z file_id: '7255' file_name: thesis.zip file_size: 21100497 relation: source_file - access_level: open_access checksum: d8c44cbc4f939c49a8efc9d4b8bb3985 content_type: application/pdf creator: dernst date_created: 2020-01-28T07:32:42Z date_updated: 2020-07-14T12:47:52Z file_id: '7367' file_name: 2020_Tkadlec_Thesis.pdf file_size: 11670983 relation: main_file file_date_updated: 2020-07-14T12:47:52Z has_accepted_license: '1' language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: '144' publication_identifier: eissn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '7210' relation: dissertation_contains status: public - id: '5751' relation: dissertation_contains status: public - id: '7212' relation: dissertation_contains status: public status: public supervisor: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X title: A role of graphs in evolutionary processes type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2020' ... --- _id: '9814' abstract: - lang: eng text: Data and mathematica notebooks for plotting figures from Language learning with communication between learners article_processing_charge: No author: - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Josef full_name: Tkadlec, Josef id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87 last_name: Tkadlec orcid: 0000-0002-1097-9684 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners. 2020. doi:10.6084/m9.figshare.5973013.v1 apa: Ibsen-Jensen, R., Tkadlec, J., Chatterjee, K., & Nowak, M. (2020). Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners. Royal Society. https://doi.org/10.6084/m9.figshare.5973013.v1 chicago: Ibsen-Jensen, Rasmus, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. “Data and Mathematica Notebooks for Plotting Figures from Language Learning with Communication between Learners from Language Acquisition with Communication between Learners.” Royal Society, 2020. https://doi.org/10.6084/m9.figshare.5973013.v1. ieee: R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, and M. Nowak, “Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners.” Royal Society, 2020. ista: Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. 2020. Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners, Royal Society, 10.6084/m9.figshare.5973013.v1. mla: Ibsen-Jensen, Rasmus, et al. Data and Mathematica Notebooks for Plotting Figures from Language Learning with Communication between Learners from Language Acquisition with Communication between Learners. Royal Society, 2020, doi:10.6084/m9.figshare.5973013.v1. short: R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, (2020). date_created: 2021-08-06T13:09:57Z date_published: 2020-10-15T00:00:00Z date_updated: 2023-10-18T06:36:00Z day: '15' department: - _id: KrCh doi: 10.6084/m9.figshare.5973013.v1 main_file_link: - open_access: '1' url: https://doi.org/10.6084/m9.figshare.5973013.v1 month: '10' oa: 1 oa_version: Published Version publisher: Royal Society related_material: record: - id: '198' relation: used_in_publication status: public status: public title: Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners type: research_data_reference user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf year: '2020' ... --- _id: '8324' abstract: - lang: eng text: The notion of program sensitivity (aka Lipschitz continuity) specifies that changes in the program input result in proportional changes to the program output. For probabilistic programs the notion is naturally extended to expected sensitivity. A previous approach develops a relational program logic framework for proving expected sensitivity of probabilistic while loops, where the number of iterations is fixed and bounded. In this work, we consider probabilistic while loops where the number of iterations is not fixed, but randomized and depends on the initial input values. We present a sound approach for proving expected sensitivity of such programs. Our sound approach is martingale-based and can be automated through existing martingale-synthesis algorithms. Furthermore, our approach is compositional for sequential composition of while loops under a mild side condition. We demonstrate the effectiveness of our approach on several classical examples from Gambler's Ruin, stochastic hybrid systems and stochastic gradient descent. We also present experimental results showing that our automated approach can handle various probabilistic programs in the literature. acknowledgement: We thank anonymous reviewers for helpful comments, especially for pointing to us a scenario of piecewise-linear approximation (Remark5). The research was partially supported by the National Natural Science Foundation of China (NSFC) under Grant No. 61802254, 61672229, 61832015,61772336,11871221 and Austrian Science Fund (FWF) NFN under Grant No. S11407-N23 (RiSE/SHiNE). We thank Prof. Yuxi Fu, director of the BASICS Lab at Shanghai Jiao Tong University, for his support. article_number: '25' article_processing_charge: No author: - first_name: Peixin full_name: Wang, Peixin last_name: Wang - first_name: Hongfei full_name: Fu, Hongfei last_name: Fu - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Yuxin full_name: Deng, Yuxin last_name: Deng - first_name: Ming full_name: Xu, Ming last_name: Xu citation: ama: 'Wang P, Fu H, Chatterjee K, Deng Y, Xu M. Proving expected sensitivity of probabilistic programs with randomized variable-dependent termination time. In: Proceedings of the ACM on Programming Languages. Vol 4. ACM; 2020. doi:10.1145/3371093' apa: Wang, P., Fu, H., Chatterjee, K., Deng, Y., & Xu, M. (2020). Proving expected sensitivity of probabilistic programs with randomized variable-dependent termination time. In Proceedings of the ACM on Programming Languages (Vol. 4). ACM. https://doi.org/10.1145/3371093 chicago: Wang, Peixin, Hongfei Fu, Krishnendu Chatterjee, Yuxin Deng, and Ming Xu. “Proving Expected Sensitivity of Probabilistic Programs with Randomized Variable-Dependent Termination Time.” In Proceedings of the ACM on Programming Languages, Vol. 4. ACM, 2020. https://doi.org/10.1145/3371093. ieee: P. Wang, H. Fu, K. Chatterjee, Y. Deng, and M. Xu, “Proving expected sensitivity of probabilistic programs with randomized variable-dependent termination time,” in Proceedings of the ACM on Programming Languages, 2020, vol. 4, no. POPL. ista: Wang P, Fu H, Chatterjee K, Deng Y, Xu M. 2020. Proving expected sensitivity of probabilistic programs with randomized variable-dependent termination time. Proceedings of the ACM on Programming Languages. vol. 4, 25. mla: Wang, Peixin, et al. “Proving Expected Sensitivity of Probabilistic Programs with Randomized Variable-Dependent Termination Time.” Proceedings of the ACM on Programming Languages, vol. 4, no. POPL, 25, ACM, 2020, doi:10.1145/3371093. short: P. Wang, H. Fu, K. Chatterjee, Y. Deng, M. Xu, in:, Proceedings of the ACM on Programming Languages, ACM, 2020. date_created: 2020-08-30T22:01:12Z date_published: 2020-01-01T00:00:00Z date_updated: 2024-02-22T15:16:45Z day: '01' ddc: - '004' department: - _id: KrCh doi: 10.1145/3371093 external_id: arxiv: - '1902.04744' file: - access_level: open_access checksum: c6193d109ff4ecb17e7a6513d8eb34c0 content_type: application/pdf creator: cziletti date_created: 2020-09-01T11:12:58Z date_updated: 2020-09-01T11:12:58Z file_id: '8328' file_name: 2019_ACM_POPL_Wang.pdf file_size: 564151 relation: main_file success: 1 file_date_updated: 2020-09-01T11:12:58Z has_accepted_license: '1' intvolume: ' 4' issue: POPL language: - iso: eng month: '01' oa: 1 oa_version: Published Version project: - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory publication: Proceedings of the ACM on Programming Languages publication_identifier: eissn: - 2475-1421 publication_status: published publisher: ACM quality_controlled: '1' related_material: link: - relation: software url: https://doi.org/10.5281/zenodo.3533633 scopus_import: '1' status: public title: Proving expected sensitivity of probabilistic programs with randomized variable-dependent termination time tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 4 year: '2020' ... --- _id: '15055' abstract: - lang: eng text: Markov decision processes (MDPs) are the defacto framework for sequential decision making in the presence of stochastic uncertainty. A classical optimization criterion for MDPs is to maximize the expected discounted-sum payoff, which ignores low probability catastrophic events with highly negative impact on the system. On the other hand, risk-averse policies require the probability of undesirable events to be below a given threshold, but they do not account for optimization of the expected payoff. We consider MDPs with discounted-sum payoff with failure states which represent catastrophic outcomes. The objective of risk-constrained planning is to maximize the expected discounted-sum payoff among risk-averse policies that ensure the probability to encounter a failure state is below a desired threshold. Our main contribution is an efficient risk-constrained planning algorithm that combines UCT-like search with a predictor learned through interaction with the MDP (in the style of AlphaZero) and with a risk-constrained action selection via linear programming. We demonstrate the effectiveness of our approach with experiments on classical MDPs from the literature, including benchmarks with an order of 106 states. acknowledgement: Krishnendu Chatterjee is supported by the Austrian Science Fund (FWF) NFN Grant No. S11407-N23 (RiSE/SHiNE), and COST Action GAMENET. Tomas Brazdil is supported by the Grant Agency of Masaryk University grant no. MUNI/G/0739/2017 and by the Czech Science Foundation grant No. 18-11193S. Petr Novotny and Jirı Vahala are supported by the Czech Science Foundation grant No. GJ19-15134Y. article_processing_charge: No article_type: original author: - first_name: Tomáš full_name: Brázdil, Tomáš last_name: Brázdil - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Petr full_name: Novotný, Petr last_name: Novotný - first_name: Jiří full_name: Vahala, Jiří last_name: Vahala citation: ama: Brázdil T, Chatterjee K, Novotný P, Vahala J. Reinforcement learning of risk-constrained policies in Markov decision processes. Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020;34(06):9794-9801. doi:10.1609/aaai.v34i06.6531 apa: 'Brázdil, T., Chatterjee, K., Novotný, P., & Vahala, J. (2020). Reinforcement learning of risk-constrained policies in Markov decision processes. Proceedings of the 34th AAAI Conference on Artificial Intelligence. New York, NY, United States: Association for the Advancement of Artificial Intelligence. https://doi.org/10.1609/aaai.v34i06.6531' chicago: Brázdil, Tomáš, Krishnendu Chatterjee, Petr Novotný, and Jiří Vahala. “Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes.” Proceedings of the 34th AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence, 2020. https://doi.org/10.1609/aaai.v34i06.6531. ieee: T. Brázdil, K. Chatterjee, P. Novotný, and J. Vahala, “Reinforcement learning of risk-constrained policies in Markov decision processes,” Proceedings of the 34th AAAI Conference on Artificial Intelligence, vol. 34, no. 06. Association for the Advancement of Artificial Intelligence, pp. 9794–9801, 2020. ista: Brázdil T, Chatterjee K, Novotný P, Vahala J. 2020. Reinforcement learning of risk-constrained policies in Markov decision processes. Proceedings of the 34th AAAI Conference on Artificial Intelligence. 34(06), 9794–9801. mla: Brázdil, Tomáš, et al. “Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes.” Proceedings of the 34th AAAI Conference on Artificial Intelligence, vol. 34, no. 06, Association for the Advancement of Artificial Intelligence, 2020, pp. 9794–801, doi:10.1609/aaai.v34i06.6531. short: T. Brázdil, K. Chatterjee, P. Novotný, J. Vahala, Proceedings of the 34th AAAI Conference on Artificial Intelligence 34 (2020) 9794–9801. conference: end_date: 2020-02-12 location: New York, NY, United States name: 'AAAI: Conference on Artificial Intelligence' start_date: 2020-02-07 date_created: 2024-03-04T08:07:22Z date_published: 2020-04-03T00:00:00Z date_updated: 2024-03-04T08:30:16Z day: '03' department: - _id: KrCh doi: 10.1609/aaai.v34i06.6531 external_id: arxiv: - '2002.12086' intvolume: ' 34' issue: '06' keyword: - General Medicine language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2002.12086 month: '04' oa: 1 oa_version: Preprint page: 9794-9801 project: - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory publication: Proceedings of the 34th AAAI Conference on Artificial Intelligence publication_identifier: issn: - 2374-3468 publication_status: published publisher: Association for the Advancement of Artificial Intelligence quality_controlled: '1' status: public title: Reinforcement learning of risk-constrained policies in Markov decision processes type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 34 year: '2020' ...