[{"intvolume":" 5","month":"05","scopus_import":"1","oa_version":"Submitted Version","pmid":1,"abstract":[{"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.","lang":"eng"}],"ec_funded":1,"issue":"10","related_material":{"link":[{"description":"News on IST Homepage","url":"https://ist.ac.at/en/news/the-emergence-of-cooperation/","relation":"press_release"}],"record":[{"status":"public","id":"10293","relation":"dissertation_contains"}]},"volume":5,"language":[{"iso":"eng"}],"file":[{"file_name":"2021_NatureHumanBehaviour_Schmid_accepted.pdf","date_created":"2023-11-07T08:27:23Z","creator":"dernst","file_size":5232761,"date_updated":"2023-11-07T08:27:23Z","success":1,"file_id":"14496","checksum":"34f55e173f90dc1dab731063458ac780","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"publication_status":"published","publication_identifier":{"eissn":["2397-3374"]},"status":"public","type":"journal_article","article_type":"original","_id":"9402","file_date_updated":"2023-11-07T08:27:23Z","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"ddc":["000"],"date_updated":"2024-03-27T23:30:44Z","oa":1,"publisher":"Springer Nature","quality_controlled":"1","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.","date_created":"2021-05-18T16:56:57Z","doi":"10.1038/s41562-021-01114-8","date_published":"2021-05-13T00:00:00Z","page":"1292–1302","publication":"Nature Human Behaviour","day":"13","year":"2021","has_accepted_license":"1","isi":1,"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"title":"A unified framework of direct and indirect reciprocity","article_processing_charge":"No","external_id":{"isi":["000650304000002"],"pmid":["33986519"]},"author":[{"orcid":"0000-0002-6978-7329","full_name":"Schmid, Laura","last_name":"Schmid","first_name":"Laura","id":"38B437DE-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Hilbe","full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","first_name":"Christian","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin A.","full_name":"Nowak, Martin A.","last_name":"Nowak"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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.","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","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.","short":"L. Schmid, K. Chatterjee, C. Hilbe, M.A. Nowak, Nature Human Behaviour 5 (2021) 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."}},{"date_updated":"2023-02-23T13:05:49Z","ddc":["000"],"file_date_updated":"2020-07-14T12:47:56Z","department":[{"_id":"KrCh"}],"_id":"7346","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"OPODIS: International Conference on Principles of Distributed Systems","end_date":"2019-12-19","location":"Neuchâtel, Switzerland","start_date":"2019-12-17"},"status":"public","publication_status":"published","file":[{"date_created":"2020-03-23T09:14:06Z","file_name":"2019_LIPIcS_Schmid.pdf","creator":"dernst","date_updated":"2020-07-14T12:47:56Z","file_size":630752,"file_id":"7608","checksum":"9a91916ac2c21ab42458fcda39ef0b8d","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"volume":153,"license":"https://creativecommons.org/licenses/by/4.0/","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. "}],"oa_version":"Preprint","alternative_title":["LIPIcs"],"scopus_import":"1","month":"02","intvolume":" 153","citation":{"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.","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.","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.","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","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","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.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Laura","id":"38B437DE-F248-11E8-B48F-1D18A9856A87","last_name":"Schmid","orcid":"0000-0002-6978-7329","full_name":"Schmid, Laura"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"}],"external_id":{"arxiv":["1906.00110"]},"article_processing_charge":"No","title":"The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game","article_number":"21","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"has_accepted_license":"1","year":"2020","day":"10","publication":"Proceedings of the 23rd International Conference on Principles of Distributed Systems","doi":"10.4230/LIPIcs.OPODIS.2019.21","date_published":"2020-02-10T00:00:00Z","date_created":"2020-01-21T16:00:26Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1},{"title":"Multi-dimensional long-run average problems for vector addition systems with states","article_processing_charge":"No","external_id":{"arxiv":["2007.08917"]},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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.","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.","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"},"project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11402-N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z211"}],"article_number":"23","date_created":"2020-10-04T22:01:36Z","doi":"10.4230/LIPIcs.CONCUR.2020.23","date_published":"2020-08-06T00:00:00Z","publication":"31st International Conference on Concurrency Theory","day":"06","year":"2020","has_accepted_license":"1","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-10-05T14:04:25Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"ddc":["000"],"date_updated":"2021-01-12T08:20:15Z","status":"public","tmp":{"short":"CC BY (3.0)","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)"},"conference":{"end_date":"2020-09-04","location":"Virtual","start_date":"2020-09-01","name":"CONCUR: Conference on Concurrency Theory"},"type":"conference","_id":"8600","license":"https://creativecommons.org/licenses/by/3.0/","volume":171,"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"5039752f644c4b72b9361d21a5e31baf","file_id":"8610","success":1,"creator":"dernst","date_updated":"2020-10-05T14:04:25Z","file_size":601231,"date_created":"2020-10-05T14:04:25Z","file_name":"2020_LIPIcsCONCUR_Chatterjee.pdf"}],"publication_status":"published","publication_identifier":{"isbn":["9783959771603"],"issn":["18688969"]},"intvolume":" 171","month":"08","scopus_import":"1","alternative_title":["LIPIcs"],"oa_version":"Published Version","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."}]},{"citation":{"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.","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.","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","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","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.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2007.02894"]},"article_processing_charge":"No","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus"},{"full_name":"Jecker, Ismael R","last_name":"Jecker","first_name":"Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425"},{"last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub"}],"title":"Simplified game of life: Algorithms and complexity","article_number":"22:1-22:13","project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"year":"2020","has_accepted_license":"1","publication":"45th International Symposium on Mathematical Foundations of Computer Science","day":"18","date_created":"2020-09-20T22:01:36Z","date_published":"2020-08-18T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2020.22","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.","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","date_updated":"2021-01-12T08:19:55Z","ddc":["000"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-09-21T13:57:34Z","_id":"8533","conference":{"location":"Prague, Czech Republic","end_date":"2020-08-28","start_date":"2020-08-24","name":"MFCS: Symposium on Mathematical Foundations of Computer Science"},"tmp":{"short":"CC BY (3.0)","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)"},"type":"conference","status":"public","publication_status":"published","publication_identifier":{"issn":["18688969"],"isbn":["9783959771597"]},"language":[{"iso":"eng"}],"file":[{"creator":"dernst","file_size":491374,"date_updated":"2020-09-21T13:57:34Z","file_name":"2020_LIPIcs_Chatterjee.pdf","date_created":"2020-09-21T13:57:34Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"checksum":"bbd7c4f55d45f2ff2a0a4ef0e10a77b1","file_id":"8550"}],"ec_funded":1,"volume":170,"abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 170","month":"08"},{"month":"08","intvolume":" 170","alternative_title":["LIPIcs"],"scopus_import":"1","oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"volume":170,"ec_funded":1,"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"2dc9e2fad6becd4563aef3e27a473f70","file_id":"8552","success":1,"creator":"dernst","date_updated":"2020-09-21T14:17:08Z","file_size":597977,"date_created":"2020-09-21T14:17:08Z","file_name":"2020_LIPIcsMFCS_Jecker.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783959771597"],"issn":["18688969"]},"publication_status":"published","status":"public","type":"conference","tmp":{"short":"CC BY (3.0)","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)"},"conference":{"name":"MFCS: Symposium on Mathematical Foundations of Computer Science","start_date":"2020-08-24","location":"Prague, Czech Republic","end_date":"2020-08-28"},"_id":"8534","file_date_updated":"2020-09-21T14:17:08Z","department":[{"_id":"KrCh"}],"ddc":["000"],"date_updated":"2021-01-12T08:19:56Z","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"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.","date_published":"2020-08-18T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2020.51","date_created":"2020-09-20T22:01:36Z","day":"18","publication":"45th International Symposium on Mathematical Foundations of Computer Science","has_accepted_license":"1","year":"2020","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"article_number":"51:1-51:12","title":"Unary prime languages","author":[{"full_name":"Jecker, Ismael R","last_name":"Jecker","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","first_name":"Ismael R"},{"first_name":"Orna","last_name":"Kupferman","full_name":"Kupferman, Orna"},{"last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas","first_name":"Nicolas"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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","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","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.","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.","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.","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."}},{"_id":"7955","type":"conference","conference":{"start_date":"2020-07-08","end_date":"2020-07-11","location":"Saarbrücken, Germany","name":"LICS: Symposium on Logic in Computer Science"},"status":"public","date_updated":"2023-08-21T08:24:36Z","ddc":["000"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-11-25T09:38:14Z","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."}],"oa_version":"Published Version","scopus_import":"1","month":"07","publication_identifier":{"isbn":["9781450371049"]},"publication_status":"published","file":[{"success":1,"file_id":"8804","checksum":"d0d0288fe991dd16cf5f02598b794240","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2020_LICS_Ashok.pdf","date_created":"2020-11-25T09:38:14Z","file_size":1001395,"date_updated":"2020-11-25T09:38:14Z","creator":"dernst"}],"language":[{"iso":"eng"}],"ec_funded":1,"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"}],"citation":{"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.","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","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.","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.","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.","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."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"full_name":"Ashok, Pranav","last_name":"Ashok","first_name":"Pranav"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Kretinsky, Jan","last_name":"Kretinsky","first_name":"Jan"},{"first_name":"Maximilian","full_name":"Weininger, Maximilian","last_name":"Weininger"},{"first_name":"Tobias","last_name":"Winkler","full_name":"Winkler, Tobias"}],"external_id":{"arxiv":["1908.05106"],"isi":["000665014900010"]},"article_processing_charge":"No","title":"Approximating values of generalized-reachability stochastic games","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.","quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1,"has_accepted_license":"1","isi":1,"year":"2020","day":"08","publication":"Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science ","page":"102-115","doi":"10.1145/3373718.3394761","date_published":"2020-07-08T00:00:00Z","date_created":"2020-06-14T22:00:48Z"},{"publication_status":"published","publication_identifier":{"eissn":["1553-7358"],"issn":["1553-734X"]},"language":[{"iso":"eng"}],"file":[{"creator":"dernst","date_updated":"2020-11-18T07:26:10Z","file_size":2498594,"date_created":"2020-11-18T07:26:10Z","file_name":"2020_PlosCompBio_Kaveh.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"8768","checksum":"555456dd0e47bcf9e0994bcb95577e88","success":1}],"volume":16,"issue":"11","abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 16","month":"11","date_updated":"2023-08-22T12:49:18Z","ddc":["000"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-11-18T07:26:10Z","_id":"8767","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","keyword":["Ecology","Modelling and Simulation","Computational Theory and Mathematics","Genetics","Ecology","Evolution","Behavior and Systematics","Molecular Biology","Cellular and Molecular Neuroscience"],"status":"public","year":"2020","isi":1,"has_accepted_license":"1","publication":"PLOS Computational Biology","day":"05","date_created":"2020-11-18T07:20:23Z","doi":"10.1371/journal.pcbi.1008402","date_published":"2020-11-05T00:00:00Z","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.","oa":1,"quality_controlled":"1","publisher":"Public Library of Science","citation":{"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.","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.","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","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","short":"K. Kaveh, A. McAvoy, K. Chatterjee, M.A. Nowak, PLOS Computational Biology 16 (2020).","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."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000591317200004"]},"article_processing_charge":"No","author":[{"first_name":"Kamran","full_name":"Kaveh, Kamran","last_name":"Kaveh"},{"last_name":"McAvoy","full_name":"McAvoy, Alex","first_name":"Alex"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Martin A.","full_name":"Nowak, Martin A.","last_name":"Nowak"}],"title":"The Moran process on 2-chromatic graphs","article_number":"e1008402"},{"oa":1,"publisher":"MDPI","quality_controlled":"1","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.","date_created":"2020-11-22T23:01:24Z","doi":"10.3390/math8111945","date_published":"2020-11-04T00:00:00Z","publication":"Mathematics","day":"04","year":"2020","isi":1,"has_accepted_license":"1","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"article_number":"1945","title":"Prioritised learning in snowdrift-type games","article_processing_charge":"No","external_id":{"isi":["000593962100001"]},"author":[{"full_name":"Kleshnina, Maria","last_name":"Kleshnina","id":"4E21749C-F248-11E8-B48F-1D18A9856A87","first_name":"Maria"},{"first_name":"Sabrina","full_name":"Streipert, Sabrina","last_name":"Streipert"},{"first_name":"Jerzy","full_name":"Filar, Jerzy","last_name":"Filar"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ista":"Kleshnina M, Streipert S, Filar J, Chatterjee K. 2020. Prioritised learning in snowdrift-type games. Mathematics. 8(11), 1945.","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.","apa":"Kleshnina, M., Streipert, S., Filar, J., & Chatterjee, K. (2020). Prioritised learning in snowdrift-type games. Mathematics. MDPI. https://doi.org/10.3390/math8111945","ama":"Kleshnina M, Streipert S, Filar J, Chatterjee K. Prioritised learning in snowdrift-type games. Mathematics. 2020;8(11). doi:10.3390/math8111945","short":"M. Kleshnina, S. Streipert, J. Filar, K. Chatterjee, Mathematics 8 (2020).","ieee":"M. Kleshnina, S. Streipert, J. Filar, and K. Chatterjee, “Prioritised learning in snowdrift-type games,” Mathematics, vol. 8, no. 11. MDPI, 2020.","mla":"Kleshnina, Maria, et al. “Prioritised Learning in Snowdrift-Type Games.” Mathematics, vol. 8, no. 11, 1945, MDPI, 2020, doi:10.3390/math8111945."},"intvolume":" 8","month":"11","scopus_import":"1","oa_version":"Published Version","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."}],"ec_funded":1,"volume":8,"issue":"11","language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_id":"8797","checksum":"61cfcc3b35760656ce7a9385a4ace5d2","file_size":565191,"date_updated":"2020-11-23T13:06:30Z","creator":"dernst","file_name":"2020_Mathematics_Kleshnina.pdf","date_created":"2020-11-23T13:06:30Z"}],"publication_status":"published","publication_identifier":{"eissn":["22277390"]},"status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","_id":"8789","file_date_updated":"2020-11-23T13:06:30Z","department":[{"_id":"KrCh"}],"ddc":["000"],"date_updated":"2023-08-22T13:25:45Z"},{"page":"3981-3992","date_created":"2020-11-22T23:01:24Z","doi":"10.1109/TCAD.2020.3012803","date_published":"2020-11-01T00:00:00Z","year":"2020","isi":1,"publication":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems","day":"01","publisher":"IEEE","quality_controlled":"1","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","external_id":{"isi":["000587712700069"]},"author":[{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"first_name":"Nico","last_name":"Schaumberger","full_name":"Schaumberger, Nico"},{"full_name":"Schmid, Ulrich","last_name":"Schmid","first_name":"Ulrich"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"}],"title":"Precedence-aware automated competitive analysis of real-time scheduling","citation":{"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.","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.","short":"A. Pavlogiannis, N. Schaumberger, U. Schmid, K. Chatterjee, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 3981–3992.","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","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","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."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"volume":39,"issue":"11","publication_status":"published","publication_identifier":{"issn":["02780070"],"eissn":["19374151"]},"language":[{"iso":"eng"}],"scopus_import":"1","intvolume":" 39","month":"11","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."}],"oa_version":"None","department":[{"_id":"KrCh"}],"date_updated":"2023-08-22T13:27:05Z","type":"journal_article","article_type":"original","status":"public","_id":"8788"},{"issue":"02","volume":34,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2159-5399"],"isbn":["9781577358350"],"eissn":["2374-3468"]},"publication_status":"published","month":"04","intvolume":" 34","scopus_import":"1","oa_version":"Preprint","abstract":[{"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.","lang":"eng"}],"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"date_updated":"2023-09-05T12:40:00Z","status":"public","type":"journal_article","article_type":"original","conference":{"location":"New York, NY, United States","end_date":"2020-02-12","start_date":"2020-02-07","name":"AAAI: Conference on Artificial Intelligence"},"_id":"9197","doi":"10.1609/aaai.v34i02.5546","date_published":"2020-04-03T00:00:00Z","date_created":"2021-02-25T09:05:18Z","page":"1798-1805","day":"03","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","year":"2020","quality_controlled":"1","publisher":"Association for the Advancement of Artificial Intelligence","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).","title":"All-pay bidding games on graphs","author":[{"full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"arxiv":["1911.08360"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","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.","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.","short":"G. Avni, R. Ibsen-Jensen, J. Tkadlec, Proceedings of the AAAI Conference on Artificial Intelligence 34 (2020) 1798–1805.","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"},"project":[{"grant_number":"S11402-N23","name":"Rigorous Systems Engineering","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z211","name":"The Wittgenstein Prize"},{"grant_number":"M02369","name":"Formal Methods meets Algorithmic Game Theory","call_identifier":"FWF","_id":"264B3912-B435-11E9-9278-68D0E5697425"}]}]