[{"date_created":"2020-10-18T22:01:36Z","type":"journal_article","month":"10","article_type":"original","file":[{"relation":"main_file","date_updated":"2020-10-19T11:14:20Z","file_id":"8676","success":1,"file_name":"2020_ijmsi_Shakiba_accepted.pdf","content_type":"application/pdf","file_size":261688,"creator":"dernst","access_level":"open_access","date_created":"2020-10-19T11:14:20Z","checksum":"f299661a6d51cda6d255a76be696f48d"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","issue":"2","intvolume":"        15","language":[{"iso":"eng"}],"volume":15,"date_published":"2020-10-01T00:00:00Z","_id":"8671","external_id":{"arxiv":["1805.10672"]},"file_date_updated":"2020-10-19T11:14:20Z","title":"A note on belief structures and s-approximation spaces","arxiv":1,"year":"2020","oa_version":"Submitted Version","page":"117-128","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. "}],"publication_status":"published","ddc":["000"],"doi":"10.29252/ijmsi.15.2.117","has_accepted_license":"1","day":"01","department":[{"_id":"KrCh"}],"scopus_import":"1","publication":"Iranian Journal of Mathematical Sciences and Informatics","oa":1,"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.","publication_identifier":{"eissn":["2008-9473"],"issn":["1735-4463"]},"status":"public","citation":{"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.","ieee":"A. Shakiba, A. K. Goharshady, M. R. Hooshmandasl, and M. Alambardar Meybodi, “A note on belief structures and s-approximation spaces,” <i>Iranian Journal of Mathematical Sciences and Informatics</i>, vol. 15, no. 2. Iranian Academic Center for Education, Culture and Research, pp. 117–128, 2020.","chicago":"Shakiba, A., Amir Kafshdar Goharshady, M.R. Hooshmandasl, and M. Alambardar Meybodi. “A Note on Belief Structures and S-Approximation Spaces.” <i>Iranian Journal of Mathematical Sciences and Informatics</i>. Iranian Academic Center for Education, Culture and Research, 2020. <a href=\"https://doi.org/10.29252/ijmsi.15.2.117\">https://doi.org/10.29252/ijmsi.15.2.117</a>.","short":"A. Shakiba, A.K. Goharshady, M.R. Hooshmandasl, M. Alambardar Meybodi, Iranian Journal of Mathematical Sciences and Informatics 15 (2020) 117–128.","apa":"Shakiba, A., Goharshady, A. K., Hooshmandasl, M. R., &#38; Alambardar Meybodi, M. (2020). A note on belief structures and s-approximation spaces. <i>Iranian Journal of Mathematical Sciences and Informatics</i>. Iranian Academic Center for Education, Culture and Research. <a href=\"https://doi.org/10.29252/ijmsi.15.2.117\">https://doi.org/10.29252/ijmsi.15.2.117</a>","ama":"Shakiba A, Goharshady AK, Hooshmandasl MR, Alambardar Meybodi M. A note on belief structures and s-approximation spaces. <i>Iranian Journal of Mathematical Sciences and Informatics</i>. 2020;15(2):117-128. doi:<a href=\"https://doi.org/10.29252/ijmsi.15.2.117\">10.29252/ijmsi.15.2.117</a>","mla":"Shakiba, A., et al. “A Note on Belief Structures and S-Approximation Spaces.” <i>Iranian Journal of Mathematical Sciences and Informatics</i>, vol. 15, no. 2, Iranian Academic Center for Education, Culture and Research, 2020, pp. 117–28, doi:<a href=\"https://doi.org/10.29252/ijmsi.15.2.117\">10.29252/ijmsi.15.2.117</a>."},"publisher":"Iranian Academic Center for Education, Culture and Research","project":[{"name":"Quantitative Analysis of Probabilistic Systems with a focus on Crypto-Currencies","_id":"267066CE-B435-11E9-9278-68D0E5697425"}],"date_updated":"2025-04-15T07:55:04Z","author":[{"full_name":"Shakiba, A.","first_name":"A.","last_name":"Shakiba"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584","last_name":"Goharshady","full_name":"Goharshady, Amir Kafshdar","first_name":"Amir Kafshdar"},{"last_name":"Hooshmandasl","first_name":"M.R.","full_name":"Hooshmandasl, M.R."},{"full_name":"Alambardar Meybodi, M.","first_name":"M.","last_name":"Alambardar Meybodi"}],"quality_controlled":"1"},{"department":[{"_id":"KrCh"}],"isi":1,"doi":"10.1371/journal.pcbi.1008402","article_number":"e1008402","day":"05","has_accepted_license":"1","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."}],"publication_status":"published","ddc":["000"],"keyword":["Ecology","Modelling and Simulation","Computational Theory and Mathematics","Genetics","Ecology","Evolution","Behavior and Systematics","Molecular Biology","Cellular and Molecular Neuroscience"],"oa_version":"Published Version","pmid":1,"quality_controlled":"1","publisher":"Public Library of Science","citation":{"short":"K. Kaveh, A. McAvoy, K. Chatterjee, M.A. Nowak, PLOS Computational Biology 16 (2020).","apa":"Kaveh, K., McAvoy, A., Chatterjee, K., &#38; Nowak, M. A. (2020). The Moran process on 2-chromatic graphs. <i>PLOS Computational Biology</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1008402\">https://doi.org/10.1371/journal.pcbi.1008402</a>","ista":"Kaveh K, McAvoy A, Chatterjee K, Nowak MA. 2020. The Moran process on 2-chromatic graphs. PLOS Computational Biology. 16(11), e1008402.","ieee":"K. Kaveh, A. McAvoy, K. Chatterjee, and M. A. Nowak, “The Moran process on 2-chromatic graphs,” <i>PLOS Computational Biology</i>, vol. 16, no. 11. Public Library of Science, 2020.","chicago":"Kaveh, Kamran, Alex McAvoy, Krishnendu Chatterjee, and Martin A. Nowak. “The Moran Process on 2-Chromatic Graphs.” <i>PLOS Computational Biology</i>. Public Library of Science, 2020. <a href=\"https://doi.org/10.1371/journal.pcbi.1008402\">https://doi.org/10.1371/journal.pcbi.1008402</a>.","mla":"Kaveh, Kamran, et al. “The Moran Process on 2-Chromatic Graphs.” <i>PLOS Computational Biology</i>, vol. 16, no. 11, e1008402, Public Library of Science, 2020, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1008402\">10.1371/journal.pcbi.1008402</a>.","ama":"Kaveh K, McAvoy A, Chatterjee K, Nowak MA. The Moran process on 2-chromatic graphs. <i>PLOS Computational Biology</i>. 2020;16(11). doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1008402\">10.1371/journal.pcbi.1008402</a>"},"author":[{"last_name":"Kaveh","first_name":"Kamran","full_name":"Kaveh, Kamran"},{"full_name":"McAvoy, Alex","first_name":"Alex","last_name":"McAvoy"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Nowak","full_name":"Nowak, Martin A.","first_name":"Martin A."}],"date_updated":"2025-06-12T07:02:01Z","oa":1,"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.","publication_identifier":{"eissn":["1553-7358"],"issn":["1553-734X"]},"status":"public","scopus_import":"1","publication":"PLOS Computational Biology","language":[{"iso":"eng"}],"intvolume":"        16","volume":16,"issue":"11","month":"11","file":[{"file_name":"2020_PlosCompBio_Kaveh.pdf","success":1,"file_id":"8768","date_updated":"2020-11-18T07:26:10Z","relation":"main_file","checksum":"555456dd0e47bcf9e0994bcb95577e88","access_level":"open_access","date_created":"2020-11-18T07:26:10Z","creator":"dernst","file_size":2498594,"content_type":"application/pdf"}],"article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_created":"2020-11-18T07:20:23Z","type":"journal_article","title":"The Moran process on 2-chromatic graphs","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"year":"2020","external_id":{"isi":["000591317200004"],"pmid":["33151935"]},"file_date_updated":"2020-11-18T07:26:10Z","date_published":"2020-11-05T00:00:00Z","_id":"8767"},{"publisher":"IEEE","citation":{"mla":"Pavlogiannis, Andreas, et al. “Precedence-Aware Automated Competitive Analysis of Real-Time Scheduling.” <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>, vol. 39, no. 11, IEEE, 2020, pp. 3981–92, doi:<a href=\"https://doi.org/10.1109/TCAD.2020.3012803\">10.1109/TCAD.2020.3012803</a>.","ama":"Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. Precedence-aware automated competitive analysis of real-time scheduling. <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>. 2020;39(11):3981-3992. doi:<a href=\"https://doi.org/10.1109/TCAD.2020.3012803\">10.1109/TCAD.2020.3012803</a>","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., &#38; Chatterjee, K. (2020). Precedence-aware automated competitive analysis of real-time scheduling. <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>. IEEE. <a href=\"https://doi.org/10.1109/TCAD.2020.3012803\">https://doi.org/10.1109/TCAD.2020.3012803</a>","ieee":"A. Pavlogiannis, N. Schaumberger, U. Schmid, and K. Chatterjee, “Precedence-aware automated competitive analysis of real-time scheduling,” <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>, vol. 39, no. 11. IEEE, pp. 3981–3992, 2020.","chicago":"Pavlogiannis, Andreas, Nico Schaumberger, Ulrich Schmid, and Krishnendu Chatterjee. “Precedence-Aware Automated Competitive Analysis of Real-Time Scheduling.” <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>. IEEE, 2020. <a href=\"https://doi.org/10.1109/TCAD.2020.3012803\">https://doi.org/10.1109/TCAD.2020.3012803</a>.","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."},"author":[{"last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","full_name":"Pavlogiannis, Andreas"},{"last_name":"Schaumberger","full_name":"Schaumberger, Nico","first_name":"Nico"},{"first_name":"Ulrich","full_name":"Schmid, Ulrich","last_name":"Schmid"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"}],"date_updated":"2026-04-02T14:37:50Z","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory"}],"quality_controlled":"1","publication":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems","scopus_import":"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. ","publication_identifier":{"issn":["0278-0070"],"eissn":["1937-4151"]},"status":"public","doi":"10.1109/TCAD.2020.3012803","day":"01","department":[{"_id":"KrCh"}],"isi":1,"oa_version":"None","page":"3981-3992","abstract":[{"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.","lang":"eng"}],"publication_status":"published","external_id":{"isi":["000587712700069"]},"title":"Precedence-aware automated competitive analysis of real-time scheduling","year":"2020","date_published":"2020-11-01T00:00:00Z","_id":"8788","issue":"11","intvolume":"        39","language":[{"iso":"eng"}],"volume":39,"date_created":"2020-11-22T23:01:24Z","type":"journal_article","month":"11","article_type":"original","article_processing_charge":"No","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd"},{"has_accepted_license":"1","day":"04","article_number":"1945","doi":"10.3390/math8111945","isi":1,"department":[{"_id":"KrCh"}],"oa_version":"Published Version","ddc":["000"],"publication_status":"published","abstract":[{"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.","lang":"eng"}],"corr_author":"1","project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"},{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"date_updated":"2026-04-07T08:37:03Z","author":[{"full_name":"Kleshnina, Maria","first_name":"Maria","orcid":"0000-0002-5518-8317","id":"4E21749C-F248-11E8-B48F-1D18A9856A87","last_name":"Kleshnina"},{"full_name":"Streipert, Sabrina","first_name":"Sabrina","last_name":"Streipert"},{"last_name":"Filar","full_name":"Filar, Jerzy","first_name":"Jerzy"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"citation":{"short":"M. Kleshnina, S. Streipert, J. Filar, K. Chatterjee, Mathematics 8 (2020).","apa":"Kleshnina, M., Streipert, S., Filar, J., &#38; Chatterjee, K. (2020). Prioritised learning in snowdrift-type games. <i>Mathematics</i>. MDPI. <a href=\"https://doi.org/10.3390/math8111945\">https://doi.org/10.3390/math8111945</a>","chicago":"Kleshnina, Maria, Sabrina Streipert, Jerzy Filar, and Krishnendu Chatterjee. “Prioritised Learning in Snowdrift-Type Games.” <i>Mathematics</i>. MDPI, 2020. <a href=\"https://doi.org/10.3390/math8111945\">https://doi.org/10.3390/math8111945</a>.","ista":"Kleshnina M, Streipert S, Filar J, Chatterjee K. 2020. Prioritised learning in snowdrift-type games. Mathematics. 8(11), 1945.","ieee":"M. Kleshnina, S. Streipert, J. Filar, and K. Chatterjee, “Prioritised learning in snowdrift-type games,” <i>Mathematics</i>, vol. 8, no. 11. MDPI, 2020.","mla":"Kleshnina, Maria, et al. “Prioritised Learning in Snowdrift-Type Games.” <i>Mathematics</i>, vol. 8, no. 11, 1945, MDPI, 2020, doi:<a href=\"https://doi.org/10.3390/math8111945\">10.3390/math8111945</a>.","ama":"Kleshnina M, Streipert S, Filar J, Chatterjee K. Prioritised learning in snowdrift-type games. <i>Mathematics</i>. 2020;8(11). doi:<a href=\"https://doi.org/10.3390/math8111945\">10.3390/math8111945</a>"},"publisher":"MDPI","quality_controlled":"1","ec_funded":1,"scopus_import":"1","publication":"Mathematics","status":"public","publication_identifier":{"eissn":["2227-7390"]},"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.","oa":1,"issue":"11","volume":8,"intvolume":"         8","language":[{"iso":"eng"}],"type":"journal_article","date_created":"2020-11-22T23:01:24Z","article_processing_charge":"No","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","article_type":"original","file":[{"date_created":"2020-11-23T13:06:30Z","creator":"dernst","access_level":"open_access","file_size":565191,"content_type":"application/pdf","checksum":"61cfcc3b35760656ce7a9385a4ace5d2","file_id":"8797","success":1,"date_updated":"2020-11-23T13:06:30Z","relation":"main_file","file_name":"2020_Mathematics_Kleshnina.pdf"}],"month":"11","file_date_updated":"2020-11-23T13:06:30Z","external_id":{"isi":["000593962100001"]},"year":"2020","title":"Prioritised learning in snowdrift-type games","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"_id":"8789","date_published":"2020-11-04T00:00:00Z"},{"language":[{"iso":"eng"}],"intvolume":"        34","volume":34,"issue":"02","OA_place":"repository","main_file_link":[{"url":"https://arxiv.org/abs/1911.08360","open_access":"1"}],"article_type":"original","month":"04","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2021-02-25T09:05:18Z","type":"journal_article","arxiv":1,"title":"All-pay bidding games on graphs","year":"2020","external_id":{"arxiv":["1911.08360"]},"date_published":"2020-04-03T00:00:00Z","_id":"9197","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"conference":{"start_date":"2020-02-07","end_date":"2020-02-12","name":"AAAI: Conference on Artificial Intelligence","location":"New York, NY, United States"},"doi":"10.1609/aaai.v34i02.5546","day":"03","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."}],"page":"1798-1805","publication_status":"published","oa_version":"Preprint","quality_controlled":"1","citation":{"apa":"Avni, G., Ibsen-Jensen, R., &#38; Tkadlec, J. (2020). All-pay bidding games on graphs. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. New York, NY, United States: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">https://doi.org/10.1609/aaai.v34i02.5546</a>","short":"G. Avni, R. Ibsen-Jensen, J. Tkadlec, Proceedings of the AAAI Conference on Artificial Intelligence 34 (2020) 1798–1805.","ieee":"G. Avni, R. Ibsen-Jensen, and J. Tkadlec, “All-pay bidding games on graphs,” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 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.","chicago":"Avni, Guy, Rasmus Ibsen-Jensen, and Josef Tkadlec. “All-Pay Bidding Games on Graphs.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Association for the Advancement of Artificial Intelligence, 2020. <a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">https://doi.org/10.1609/aaai.v34i02.5546</a>.","mla":"Avni, Guy, et al. “All-Pay Bidding Games on Graphs.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 34, no. 02, Association for the Advancement of Artificial Intelligence, 2020, pp. 1798–805, doi:<a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">10.1609/aaai.v34i02.5546</a>.","ama":"Avni G, Ibsen-Jensen R, Tkadlec J. All-pay bidding games on graphs. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. 2020;34(02):1798-1805. doi:<a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">10.1609/aaai.v34i02.5546</a>"},"publisher":"Association for the Advancement of Artificial Intelligence","author":[{"full_name":"Avni, Guy","first_name":"Guy","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5588-8287","last_name":"Avni"},{"first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef"}],"project":[{"grant_number":"S11402-N23","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Formal Methods meets Algorithmic Game Theory","grant_number":"M02369","_id":"264B3912-B435-11E9-9278-68D0E5697425"}],"date_updated":"2025-07-03T11:44:58Z","oa":1,"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).","status":"public","OA_type":"green","publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"],"isbn":["9781577358350"]},"scopus_import":"1","publication":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"main_file_link":[{"url":"https://doi.org/10.6084/m9.figshare.5973013.v1","open_access":"1"}],"day":"15","doi":"10.6084/m9.figshare.5973013.v1","OA_place":"publisher","department":[{"_id":"KrCh"}],"type":"research_data_reference","oa_version":"Published Version","date_created":"2021-08-06T13:09:57Z","article_processing_charge":"No","user_id":"0043cee0-e5fc-11ee-9736-f83bc23afbf0","abstract":[{"lang":"eng","text":"Data and mathematica notebooks for plotting figures from Language learning with communication between learners"}],"month":"10","author":[{"orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus"},{"orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"date_updated":"2025-04-15T08:12:20Z","citation":{"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.","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. <a href=\"https://doi.org/10.6084/m9.figshare.5973013.v1\">https://doi.org/10.6084/m9.figshare.5973013.v1</a>.","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, <a href=\"https://doi.org/10.6084/m9.figshare.5973013.v1\">10.6084/m9.figshare.5973013.v1</a>.","apa":"Ibsen-Jensen, R., Tkadlec, J., Chatterjee, K., &#38; 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. <a href=\"https://doi.org/10.6084/m9.figshare.5973013.v1\">https://doi.org/10.6084/m9.figshare.5973013.v1</a>","short":"R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, (2020).","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:<a href=\"https://doi.org/10.6084/m9.figshare.5973013.v1\">10.6084/m9.figshare.5973013.v1</a>","mla":"Ibsen-Jensen, Rasmus, et al. <i>Data and Mathematica Notebooks for Plotting Figures from Language Learning with Communication between Learners from Language Acquisition with Communication between Learners</i>. Royal Society, 2020, doi:<a href=\"https://doi.org/10.6084/m9.figshare.5973013.v1\">10.6084/m9.figshare.5973013.v1</a>."},"related_material":{"record":[{"id":"198","status":"public","relation":"used_in_publication"}]},"publisher":"Royal Society","year":"2020","title":"Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners","_id":"9814","date_published":"2020-10-15T00:00:00Z","OA_type":"hybrid","status":"public","oa":1},{"publication_identifier":{"eissn":["2663-337X"]},"status":"public","oa":1,"alternative_title":["ISTA Thesis"],"author":[{"last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","first_name":"Josef","full_name":"Tkadlec, Josef"}],"date_updated":"2026-04-16T08:32:37Z","related_material":{"record":[{"relation":"dissertation_contains","id":"5751","status":"public"},{"relation":"dissertation_contains","status":"public","id":"7210"},{"relation":"dissertation_contains","status":"public","id":"7212"}]},"citation":{"short":"J. Tkadlec, A Role of Graphs in Evolutionary Processes, Institute of Science and Technology Austria, 2020.","apa":"Tkadlec, J. (2020). <i>A role of graphs in evolutionary processes</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7196\">https://doi.org/10.15479/AT:ISTA:7196</a>","ista":"Tkadlec J. 2020. A role of graphs in evolutionary processes. Institute of Science and Technology Austria.","chicago":"Tkadlec, Josef. “A Role of Graphs in Evolutionary Processes.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7196\">https://doi.org/10.15479/AT:ISTA:7196</a>.","ieee":"J. Tkadlec, “A role of graphs in evolutionary processes,” Institute of Science and Technology Austria, 2020.","mla":"Tkadlec, Josef. <i>A Role of Graphs in Evolutionary Processes</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7196\">10.15479/AT:ISTA:7196</a>.","ama":"Tkadlec J. A role of graphs in evolutionary processes. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7196\">10.15479/AT:ISTA:7196</a>"},"publisher":"Institute of Science and Technology Austria","publication_status":"published","ddc":["519"],"page":"144","supervisor":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"}],"abstract":[{"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.","lang":"eng"}],"corr_author":"1","oa_version":"Published Version","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"day":"12","has_accepted_license":"1","doi":"10.15479/AT:ISTA:7196","_id":"7196","date_published":"2020-01-12T00:00:00Z","year":"2020","title":"A role of graphs in evolutionary processes","file_date_updated":"2020-07-14T12:47:52Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","article_processing_charge":"No","file":[{"checksum":"451f8e64b0eb26bf297644ac72bfcbe9","creator":"jtkadlec","date_created":"2020-01-12T11:49:49Z","access_level":"closed","content_type":"application/zip","file_size":21100497,"file_name":"thesis.zip","file_id":"7255","relation":"source_file","date_updated":"2020-07-14T12:47:52Z"},{"file_size":11670983,"content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2020-01-28T07:32:42Z","checksum":"d8c44cbc4f939c49a8efc9d4b8bb3985","date_updated":"2020-07-14T12:47:52Z","relation":"main_file","file_id":"7367","file_name":"2020_Tkadlec_Thesis.pdf"}],"month":"01","type":"dissertation","date_created":"2019-12-20T12:26:36Z","language":[{"iso":"eng"}],"degree_awarded":"PhD","OA_place":"publisher"},{"publication_status":"published","ddc":["000"],"abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","department":[{"_id":"KrCh"}],"isi":1,"day":"17","has_accepted_license":"1","doi":"10.1371/journal.pcbi.1007494","article_number":"e1007494","publication_identifier":{"issn":["1553-734X"],"eissn":["1553-7358"]},"status":"public","oa":1,"publication":"PLoS computational biology","scopus_import":"1","ec_funded":1,"quality_controlled":"1","date_updated":"2026-04-16T08:32:38Z","author":[{"full_name":"Tkadlec, Josef","first_name":"Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Nowak","full_name":"Nowak, Martin A.","first_name":"Martin A."}],"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"publisher":"Public Library of Science","citation":{"mla":"Tkadlec, Josef, et al. “Limits on Amplifiers of Natural Selection under Death-Birth Updating.” <i>PLoS Computational Biology</i>, vol. 16, e1007494, Public Library of Science, 2020, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1007494\">10.1371/journal.pcbi.1007494</a>.","ama":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Limits on amplifiers of natural selection under death-Birth updating. <i>PLoS computational biology</i>. 2020;16. doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1007494\">10.1371/journal.pcbi.1007494</a>","apa":"Tkadlec, J., Pavlogiannis, A., Chatterjee, K., &#38; Nowak, M. A. (2020). Limits on amplifiers of natural selection under death-Birth updating. <i>PLoS Computational Biology</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1007494\">https://doi.org/10.1371/journal.pcbi.1007494</a>","short":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational Biology 16 (2020).","chicago":"Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. “Limits on Amplifiers of Natural Selection under Death-Birth Updating.” <i>PLoS Computational Biology</i>. Public Library of Science, 2020. <a href=\"https://doi.org/10.1371/journal.pcbi.1007494\">https://doi.org/10.1371/journal.pcbi.1007494</a>.","ieee":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Limits on amplifiers of natural selection under death-Birth updating,” <i>PLoS computational biology</i>, 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."},"related_material":{"record":[{"status":"public","id":"7196","relation":"part_of_dissertation"}]},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","article_processing_charge":"No","month":"01","file":[{"file_id":"7441","date_updated":"2020-07-14T12:47:53Z","relation":"main_file","file_name":"2020_PlosCompBio_Tkadlec.pdf","access_level":"open_access","date_created":"2020-02-03T07:32:42Z","creator":"dernst","file_size":1817531,"content_type":"application/pdf","checksum":"ce32ee2d2f53aed832f78bbd47e882df"}],"article_type":"original","type":"journal_article","date_created":"2019-12-23T13:45:11Z","volume":16,"language":[{"iso":"eng"}],"intvolume":"        16","_id":"7212","date_published":"2020-01-17T00:00:00Z","year":"2020","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"title":"Limits on amplifiers of natural selection under death-Birth updating","arxiv":1,"file_date_updated":"2020-07-14T12:47:53Z","external_id":{"arxiv":["1906.02785"],"isi":["000510916500025"]}},{"volume":23,"language":[{"iso":"eng"}],"intvolume":"        23","issue":"3","article_processing_charge":"Yes (via OA deal)","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"03","article_type":"letter_note","file":[{"content_type":"application/pdf","file_size":561749,"creator":"dernst","access_level":"open_access","date_created":"2020-11-19T11:27:10Z","checksum":"0cd8be386fa219db02845b7c3991ce04","relation":"main_file","date_updated":"2020-11-19T11:27:10Z","success":1,"file_id":"8776","file_name":"2020_EcologyLetters_Milutinovic.pdf"}],"type":"journal_article","date_created":"2020-01-20T13:32:12Z","year":"2020","title":"Social immunity modulates competition between coinfecting pathogens","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","short":"CC BY-NC (4.0)","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)"},"acknowledged_ssus":[{"_id":"LifeSc"}],"file_date_updated":"2020-11-19T11:27:10Z","external_id":{"pmid":["31950595"],"isi":["000507515900001"]},"_id":"7343","date_published":"2020-03-01T00:00:00Z","department":[{"_id":"SyCr"},{"_id":"KrCh"}],"isi":1,"day":"01","has_accepted_license":"1","doi":"10.1111/ele.13458","publication_status":"published","ddc":["570"],"page":"565-574","corr_author":"1","abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","quality_controlled":"1","ec_funded":1,"pmid":1,"author":[{"full_name":"Milutinovic, Barbara","first_name":"Barbara","last_name":"Milutinovic","orcid":"0000-0002-8214-4758","id":"2CDC32B8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Miriam","full_name":"Stock, Miriam","id":"42462816-F248-11E8-B48F-1D18A9856A87","last_name":"Stock"},{"last_name":"Grasse","id":"406F989C-F248-11E8-B48F-1D18A9856A87","first_name":"Anna V","full_name":"Grasse, Anna V"},{"first_name":"Elisabeth","full_name":"Naderlinger, Elisabeth","id":"31757262-F248-11E8-B48F-1D18A9856A87","last_name":"Naderlinger"},{"last_name":"Hilbe","orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian","full_name":"Hilbe, Christian"},{"id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","last_name":"Cremer","orcid":"0000-0002-2193-3868","full_name":"Cremer, Sylvia","first_name":"Sylvia"}],"date_updated":"2025-06-12T07:32:35Z","project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"grant_number":"CR-118/3-1","_id":"25DAF0B2-B435-11E9-9278-68D0E5697425","name":"Host-Parasite Coevolution"}],"publisher":"Wiley","citation":{"ama":"Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. Social immunity modulates competition between coinfecting pathogens. <i>Ecology Letters</i>. 2020;23(3):565-574. doi:<a href=\"https://doi.org/10.1111/ele.13458\">10.1111/ele.13458</a>","mla":"Milutinovic, Barbara, et al. “Social Immunity Modulates Competition between Coinfecting Pathogens.” <i>Ecology Letters</i>, vol. 23, no. 3, Wiley, 2020, pp. 565–74, doi:<a href=\"https://doi.org/10.1111/ele.13458\">10.1111/ele.13458</a>.","chicago":"Milutinovic, Barbara, Miriam Stock, Anna V Grasse, Elisabeth Naderlinger, Christian Hilbe, and Sylvia Cremer. “Social Immunity Modulates Competition between Coinfecting Pathogens.” <i>Ecology Letters</i>. Wiley, 2020. <a href=\"https://doi.org/10.1111/ele.13458\">https://doi.org/10.1111/ele.13458</a>.","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.","ieee":"B. Milutinovic, M. Stock, A. V. Grasse, E. Naderlinger, C. Hilbe, and S. Cremer, “Social immunity modulates competition between coinfecting pathogens,” <i>Ecology Letters</i>, vol. 23, no. 3. Wiley, pp. 565–574, 2020.","short":"B. Milutinovic, M. Stock, A.V. Grasse, E. Naderlinger, C. Hilbe, S. Cremer, Ecology Letters 23 (2020) 565–574.","apa":"Milutinovic, B., Stock, M., Grasse, A. V., Naderlinger, E., Hilbe, C., &#38; Cremer, S. (2020). Social immunity modulates competition between coinfecting pathogens. <i>Ecology Letters</i>. Wiley. <a href=\"https://doi.org/10.1111/ele.13458\">https://doi.org/10.1111/ele.13458</a>"},"related_material":{"record":[{"status":"public","id":"13060","relation":"research_data"}],"link":[{"relation":"press_release","description":"News on IST Homepage","url":"https://ist.ac.at/en/news/social-ants-shapes-disease-outcome/"}]},"publication_identifier":{"issn":["1461-023X"],"eissn":["1461-0248"]},"status":"public","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.). ","oa":1,"scopus_import":"1","publication":"Ecology Letters"},{"alternative_title":["LIPIcs"],"scopus_import":"1","publication":"Proceedings of the 23rd International Conference on Principles of Distributed Systems","status":"public","oa":1,"date_updated":"2025-04-15T08:10:32Z","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"author":[{"orcid":"0000-0002-6978-7329","last_name":"Schmid","id":"38B437DE-F248-11E8-B48F-1D18A9856A87","first_name":"Laura","full_name":"Schmid, Laura"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"}],"citation":{"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., &#38; Schmid, S. (2020). The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game. In <i>Proceedings of the 23rd International Conference on Principles of Distributed Systems</i> (Vol. 153). Neuchâtel, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.21\">https://doi.org/10.4230/LIPIcs.OPODIS.2019.21</a>","ieee":"L. Schmid, K. Chatterjee, and S. Schmid, “The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game,” in <i>Proceedings of the 23rd International Conference on Principles of Distributed Systems</i>, 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.","chicago":"Schmid, Laura, Krishnendu Chatterjee, and Stefan Schmid. “The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game.” In <i>Proceedings of the 23rd International Conference on Principles of Distributed Systems</i>, Vol. 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.21\">https://doi.org/10.4230/LIPIcs.OPODIS.2019.21</a>.","mla":"Schmid, Laura, et al. “The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game.” <i>Proceedings of the 23rd International Conference on Principles of Distributed Systems</i>, vol. 153, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.21\">10.4230/LIPIcs.OPODIS.2019.21</a>.","ama":"Schmid L, Chatterjee K, Schmid S. The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game. In: <i>Proceedings of the 23rd International Conference on Principles of Distributed Systems</i>. Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.21\">10.4230/LIPIcs.OPODIS.2019.21</a>"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa_version":"Preprint","ddc":["000"],"publication_status":"published","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. "}],"day":"10","has_accepted_license":"1","article_number":"21","doi":"10.4230/LIPIcs.OPODIS.2019.21","conference":{"start_date":"2019-12-17","end_date":"2019-12-19","name":"OPODIS: International Conference on Principles of Distributed Systems","location":"Neuchâtel, Switzerland"},"department":[{"_id":"KrCh"}],"_id":"7346","date_published":"2020-02-10T00:00:00Z","file_date_updated":"2020-07-14T12:47:56Z","external_id":{"arxiv":["1906.00110"]},"year":"2020","arxiv":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"title":"The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game","type":"conference","date_created":"2020-01-21T16:00:26Z","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"02","file":[{"checksum":"9a91916ac2c21ab42458fcda39ef0b8d","date_created":"2020-03-23T09:14:06Z","creator":"dernst","access_level":"open_access","content_type":"application/pdf","file_size":630752,"file_name":"2019_LIPIcS_Schmid.pdf","file_id":"7608","relation":"main_file","date_updated":"2020-07-14T12:47:56Z"}],"volume":153,"language":[{"iso":"eng"}],"intvolume":"       153"},{"_id":"8728","date_published":"2020-10-12T00:00:00Z","file_date_updated":"2020-11-06T07:41:03Z","external_id":{"isi":["000723555700014"]},"year":"2020","title":"Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth","type":"conference","date_created":"2020-11-06T07:30:05Z","article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"10","file":[{"checksum":"ae83f27e5b189d5abc2e7514f1b7e1b5","content_type":"application/pdf","file_size":726648,"creator":"dernst","access_level":"open_access","date_created":"2020-11-06T07:41:03Z","file_name":"2020_LNCS_ATVA_Asadi_accepted.pdf","relation":"main_file","date_updated":"2020-11-06T07:41:03Z","success":1,"file_id":"8729"}],"volume":12302,"language":[{"iso":"eng"}],"intvolume":"     12302","publication":"Automated Technology for Verification and Analysis","scopus_import":"1","alternative_title":["LNCS"],"publication_identifier":{"eisbn":["9783030591526"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783030591519"]},"status":"public","oa":1,"author":[{"first_name":"Ali","full_name":"Asadi, Ali","last_name":"Asadi"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Goharshady, Amir Kafshdar","first_name":"Amir Kafshdar","last_name":"Goharshady","orcid":"0000-0003-1702-6584","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mohammadi, Kiarash","first_name":"Kiarash","last_name":"Mohammadi"},{"first_name":"Andreas","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"}],"date_updated":"2026-07-04T22:31:08Z","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"name":"Quantitative Analysis of Probabilistic Systems with a focus on Crypto-Currencies","_id":"267066CE-B435-11E9-9278-68D0E5697425"}],"citation":{"mla":"Asadi, Ali, et al. “Faster Algorithms for Quantitative Analysis of MCs and MDPs with Small Treewidth.” <i>Automated Technology for Verification and Analysis</i>, vol. 12302, Springer Nature, 2020, pp. 253–70, doi:<a href=\"https://doi.org/10.1007/978-3-030-59152-6_14\">10.1007/978-3-030-59152-6_14</a>.","ama":"Asadi A, Chatterjee K, Goharshady AK, Mohammadi K, Pavlogiannis A. Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth. In: <i>Automated Technology for Verification and Analysis</i>. Vol 12302. Springer Nature; 2020:253-270. doi:<a href=\"https://doi.org/10.1007/978-3-030-59152-6_14\">10.1007/978-3-030-59152-6_14</a>","apa":"Asadi, A., Chatterjee, K., Goharshady, A. K., Mohammadi, K., &#38; Pavlogiannis, A. (2020). Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth. In <i>Automated Technology for Verification and Analysis</i> (Vol. 12302, pp. 253–270). Hanoi, Vietnam: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-59152-6_14\">https://doi.org/10.1007/978-3-030-59152-6_14</a>","short":"A. Asadi, K. Chatterjee, A.K. Goharshady, K. Mohammadi, A. Pavlogiannis, in:, Automated Technology for Verification and Analysis, Springer Nature, 2020, pp. 253–270.","ieee":"A. Asadi, K. Chatterjee, A. K. Goharshady, K. Mohammadi, and A. Pavlogiannis, “Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth,” in <i>Automated Technology for Verification and Analysis</i>, Hanoi, Vietnam, 2020, vol. 12302, pp. 253–270.","ista":"Asadi A, Chatterjee K, Goharshady AK, Mohammadi K, Pavlogiannis A. 2020. Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth. Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 12302, 253–270.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Kiarash Mohammadi, and Andreas Pavlogiannis. “Faster Algorithms for Quantitative Analysis of MCs and MDPs with Small Treewidth.” In <i>Automated Technology for Verification and Analysis</i>, 12302:253–70. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-59152-6_14\">https://doi.org/10.1007/978-3-030-59152-6_14</a>."},"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8934"}]},"publisher":"Springer Nature","quality_controlled":"1","oa_version":"Submitted Version","publication_status":"published","ddc":["000"],"page":"253-270","abstract":[{"lang":"eng","text":"Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) are two standard formalisms in system analysis. Their main associated quantitative objectives are hitting probabilities, discounted sum, and mean payoff. Although there are many techniques for computing these objectives in general MCs/MDPs, they have not been thoroughly studied in terms of parameterized algorithms, particularly when treewidth is used as the parameter. This is in sharp contrast to qualitative objectives for MCs, MDPs and graph games, for which treewidth-based algorithms yield significant complexity improvements. In this work, we show that treewidth can also be used to obtain faster algorithms for the quantitative problems. For an MC with n states and m transitions, we show that each of the classical quantitative objectives can be computed in   O((n+m)⋅t2)  time, given a tree decomposition of the MC with width t. Our results also imply a bound of   O(κ⋅(n+m)⋅t2)  for each objective on MDPs, where   κ  is the number of strategy-iteration refinements required for the given input and objective. Finally, we make an experimental evaluation of our new algorithms on low-treewidth MCs and MDPs obtained from the DaCapo benchmark suite. Our experiments show that on low-treewidth MCs and MDPs, our algorithms outperform existing well-established methods by one or more orders of magnitude."}],"has_accepted_license":"1","day":"12","doi":"10.1007/978-3-030-59152-6_14","conference":{"start_date":"2020-10-19","end_date":"2020-10-23","location":"Hanoi, Vietnam","name":"ATVA: Automated Technology for Verification and Analysis"},"department":[{"_id":"KrCh"}],"isi":1},{"page":"672-687","abstract":[{"text":"We consider the classical problem of invariant generation for programs with polynomial assignments and focus on synthesizing invariants that are a conjunction of strict polynomial inequalities. We present a sound and semi-complete method based on positivstellensaetze, i.e. theorems in semi-algebraic geometry that characterize positive polynomials over a semi-algebraic set.\r\n\r\nOn the theoretical side, the worst-case complexity of our approach is subexponential, whereas the worst-case complexity of the previous complete method (Kapur, ACA 2004) is doubly-exponential. Even when restricted to linear invariants, the best previous complexity for complete invariant generation is exponential (Colon et al, CAV 2003). On the practical side, we reduce the invariant generation problem to quadratic programming (QCLP), which is a classical optimization problem with many industrial solvers. We demonstrate the applicability of our approach by providing experimental results on several academic benchmarks. To the best of our knowledge, the only previous invariant generation method that provides completeness guarantees for invariants consisting of polynomial inequalities is (Kapur, ACA 2004), which relies on quantifier elimination and cannot even handle toy programs such as our running example.","lang":"eng"}],"publication_status":"published","oa_version":"Preprint","department":[{"_id":"KrCh"}],"isi":1,"conference":{"end_date":"2020-06-20","start_date":"2020-06-15","location":"London, United Kingdom","name":"PLDI: Programming Language Design and Implementation"},"doi":"10.1145/3385412.3385969","day":"11","oa":1,"publication_identifier":{"isbn":["9781450376136"]},"status":"public","scopus_import":"1","publication":"Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation","quality_controlled":"1","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8934"}]},"publisher":"Association for Computing Machinery","citation":{"short":"K. Chatterjee, H. Fu, A.K. Goharshady, E.K. Goharshady, in:, Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2020, pp. 672–687.","apa":"Chatterjee, K., Fu, H., Goharshady, A. K., &#38; Goharshady, E. K. (2020). Polynomial invariant generation for non-deterministic recursive programs. In <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i> (pp. 672–687). London, United Kingdom: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3385412.3385969\">https://doi.org/10.1145/3385412.3385969</a>","ieee":"K. Chatterjee, H. Fu, A. K. Goharshady, and E. K. Goharshady, “Polynomial invariant generation for non-deterministic recursive programs,” in <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>, London, United Kingdom, 2020, pp. 672–687.","ista":"Chatterjee K, Fu H, Goharshady AK, Goharshady EK. 2020. Polynomial invariant generation for non-deterministic recursive programs. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation, 672–687.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Ehsan Kafshdar Goharshady. “Polynomial Invariant Generation for Non-Deterministic Recursive Programs.” In <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>, 672–87. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3385412.3385969\">https://doi.org/10.1145/3385412.3385969</a>.","mla":"Chatterjee, Krishnendu, et al. “Polynomial Invariant Generation for Non-Deterministic Recursive Programs.” <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>, Association for Computing Machinery, 2020, pp. 672–87, doi:<a href=\"https://doi.org/10.1145/3385412.3385969\">10.1145/3385412.3385969</a>.","ama":"Chatterjee K, Fu H, Goharshady AK, Goharshady EK. Polynomial invariant generation for non-deterministic recursive programs. In: <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>. Association for Computing Machinery; 2020:672-687. doi:<a href=\"https://doi.org/10.1145/3385412.3385969\">10.1145/3385412.3385969</a>"},"author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Hongfei","full_name":"Fu, Hongfei","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","last_name":"Fu"},{"first_name":"Amir Kafshdar","full_name":"Goharshady, Amir Kafshdar","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584"},{"first_name":"Ehsan Kafshdar","full_name":"Goharshady, Ehsan Kafshdar","last_name":"Goharshady"}],"date_updated":"2026-07-04T22:31:09Z","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425"}],"month":"06","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2020-07-05T22:00:45Z","type":"conference","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1902.04373","open_access":"1"}],"date_published":"2020-06-11T00:00:00Z","_id":"8089","title":"Polynomial invariant generation for non-deterministic recursive programs","arxiv":1,"year":"2020","external_id":{"arxiv":["1902.04373"],"isi":["000614622300045"]}},{"year":"2020","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"title":"Optimal and perfectly parallel algorithms for on-demand data-flow analysis","file_date_updated":"2020-07-14T12:48:03Z","external_id":{"isi":["000681656800005"]},"_id":"7810","date_published":"2020-04-18T00:00:00Z","volume":12075,"intvolume":"     12075","language":[{"iso":"eng"}],"article_processing_charge":"No","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","file":[{"file_name":"2020_LNCS_Chatterjee.pdf","file_id":"7895","date_updated":"2020-07-14T12:48:03Z","relation":"main_file","checksum":"8618b80f4cf7b39a60e61a6445ad9807","date_created":"2020-05-26T13:34:48Z","creator":"dernst","access_level":"open_access","file_size":651250,"content_type":"application/pdf"}],"month":"04","type":"conference","date_created":"2020-05-10T22:00:50Z","quality_controlled":"1","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Goharshady, Amir Kafshdar","first_name":"Amir Kafshdar","orcid":"0000-0003-1702-6584","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen"},{"orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","full_name":"Pavlogiannis, Andreas"}],"project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification"},{"_id":"266EEEC0-B435-11E9-9278-68D0E5697425","name":"Quantitative Game-theoretic Analysis of Blockchain Applications and Smart Contracts"},{"_id":"267066CE-B435-11E9-9278-68D0E5697425","name":"Quantitative Analysis of Probabilistic Systems with a focus on Crypto-Currencies"}],"date_updated":"2026-07-04T22:31:09Z","related_material":{"record":[{"status":"public","id":"8934","relation":"dissertation_contains"}]},"publisher":"Springer Nature","citation":{"mla":"Chatterjee, Krishnendu, et al. “Optimal and Perfectly Parallel Algorithms for On-Demand Data-Flow Analysis.” <i>European Symposium on Programming</i>, vol. 12075, Springer Nature, 2020, pp. 112–40, doi:<a href=\"https://doi.org/10.1007/978-3-030-44914-8_5\">10.1007/978-3-030-44914-8_5</a>.","ama":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In: <i>European Symposium on Programming</i>. Vol 12075. Springer Nature; 2020:112-140. doi:<a href=\"https://doi.org/10.1007/978-3-030-44914-8_5\">10.1007/978-3-030-44914-8_5</a>","short":"K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, European Symposium on Programming, Springer Nature, 2020, pp. 112–140.","apa":"Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2020). Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In <i>European Symposium on Programming</i> (Vol. 12075, pp. 112–140). Dublin, Ireland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-44914-8_5\">https://doi.org/10.1007/978-3-030-44914-8_5</a>","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Optimal and Perfectly Parallel Algorithms for On-Demand Data-Flow Analysis.” In <i>European Symposium on Programming</i>, 12075:112–40. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-44914-8_5\">https://doi.org/10.1007/978-3-030-44914-8_5</a>.","ista":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2020. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. European Symposium on Programming. ESOP: Programming Languages and Systems, LNCS, vol. 12075, 112–140.","ieee":"K. Chatterjee, A. K. Goharshady, R. Ibsen-Jensen, and A. Pavlogiannis, “Optimal and perfectly parallel algorithms for on-demand data-flow analysis,” in <i>European Symposium on Programming</i>, Dublin, Ireland, 2020, vol. 12075, pp. 112–140."},"publication_identifier":{"isbn":["9783030449131"],"eissn":["1611-3349"],"issn":["0302-9743"]},"status":"public","oa":1,"scopus_import":"1","publication":"European Symposium on Programming","alternative_title":["LNCS"],"conference":{"location":"Dublin, Ireland","name":"ESOP: Programming Languages and Systems","end_date":"2020-04-30","start_date":"2020-04-25"},"department":[{"_id":"KrCh"}],"isi":1,"has_accepted_license":"1","day":"18","doi":"10.1007/978-3-030-44914-8_5","publication_status":"published","ddc":["000"],"page":"112-140","corr_author":"1","abstract":[{"lang":"eng","text":"Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointers analysis. The most widely-used framework for interprocedural data-flow analysis is IFDS, which encompasses distributive data-flow functions over a finite domain. On-demand data-flow analyses restrict the focus of the analysis on specific program locations and data facts. This setting provides a natural split between (i) an offline (or preprocessing) phase, where the program is partially analyzed and analysis summaries are created, and (ii) an online (or query) phase, where analysis queries arrive on demand and the summaries are used to speed up answering queries.\r\nIn this work, we consider on-demand IFDS analyses where the queries concern program locations of the same procedure (aka same-context queries). We exploit the fact that flow graphs of programs have low treewidth to develop faster algorithms that are space and time optimal for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are embarrassingly parallelizable, i.e. the total work for answering each query is split to a number of threads such that each thread performs only a constant amount of work. Finally, we implement a static analyzer based on our algorithms, and perform a series of on-demand analysis experiments on standard benchmarks. Our experimental results show a drastic speed-up of the queries after only a lightweight preprocessing phase, which significantly outperforms existing techniques."}],"oa_version":"Published Version"},{"isi":1,"department":[{"_id":"KrCh"}],"day":"01","article_number":"106665","doi":"10.1016/j.ress.2019.106665","publication_status":"published","abstract":[{"text":"We consider the classic problem of Network Reliability. A network is given together with a source vertex, one or more target vertices, and probabilities assigned to each of the edges. Each edge of the network is operable with its associated probability and the problem is to determine the probability of having at least one source-to-target path that is entirely composed of operable edges. This problem is known to be NP-hard.\r\n\r\nWe provide a novel scalable algorithm to solve the Network Reliability problem when the treewidth of the underlying network is small. We also show our algorithm’s applicability for real-world transit networks that have small treewidth, including the metro networks of major cities, such as London and Tokyo. Our algorithm leverages tree decompositions to shrink the original graph into much smaller graphs, for which reliability can be efficiently and exactly computed using a brute force method. To the best of our knowledge, this is the first exact algorithm for Network Reliability that can scale to handle real-world instances of the problem.","lang":"eng"}],"oa_version":"Preprint","quality_controlled":"1","author":[{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584","last_name":"Goharshady","full_name":"Goharshady, Amir Kafshdar","first_name":"Amir Kafshdar"},{"full_name":"Mohammadi, Fatemeh","first_name":"Fatemeh","last_name":"Mohammadi"}],"date_updated":"2026-07-04T22:31:09Z","project":[{"name":"Quantitative Game-theoretic Analysis of Blockchain Applications and Smart Contracts","_id":"266EEEC0-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"status":"public","id":"8934","relation":"dissertation_contains"}]},"publisher":"Elsevier","citation":{"ista":"Goharshady AK, Mohammadi F. 2020. An efficient algorithm for computing network reliability in small treewidth. Reliability Engineering and System Safety. 193, 106665.","ieee":"A. K. Goharshady and F. Mohammadi, “An efficient algorithm for computing network reliability in small treewidth,” <i>Reliability Engineering and System Safety</i>, vol. 193. Elsevier, 2020.","chicago":"Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm for Computing Network Reliability in Small Treewidth.” <i>Reliability Engineering and System Safety</i>. Elsevier, 2020. <a href=\"https://doi.org/10.1016/j.ress.2019.106665\">https://doi.org/10.1016/j.ress.2019.106665</a>.","apa":"Goharshady, A. K., &#38; Mohammadi, F. (2020). An efficient algorithm for computing network reliability in small treewidth. <i>Reliability Engineering and System Safety</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ress.2019.106665\">https://doi.org/10.1016/j.ress.2019.106665</a>","short":"A.K. Goharshady, F. Mohammadi, Reliability Engineering and System Safety 193 (2020).","ama":"Goharshady AK, Mohammadi F. An efficient algorithm for computing network reliability in small treewidth. <i>Reliability Engineering and System Safety</i>. 2020;193. doi:<a href=\"https://doi.org/10.1016/j.ress.2019.106665\">10.1016/j.ress.2019.106665</a>","mla":"Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm for Computing Network Reliability in Small Treewidth.” <i>Reliability Engineering and System Safety</i>, vol. 193, 106665, Elsevier, 2020, doi:<a href=\"https://doi.org/10.1016/j.ress.2019.106665\">10.1016/j.ress.2019.106665</a>."},"status":"public","publication_identifier":{"issn":["0951-8320"]},"acknowledgement":"We are grateful to the anonymous reviewers for their comments, which significantly improved the present work. The research was partially supported by the EPSRC Early Career Fellowship EP/R023379/1, grant no. SC7-1718-01 of the London Mathematical Society, an IBM PhD Fellowship, and a DOC Fellowship of the Austrian Academy of Sciences (ÖAW).","oa":1,"publication":"Reliability Engineering and System Safety","scopus_import":"1","volume":193,"language":[{"iso":"eng"}],"intvolume":"       193","main_file_link":[{"url":"https://arxiv.org/abs/1712.09692","open_access":"1"}],"article_processing_charge":"No","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","month":"01","article_type":"original","type":"journal_article","date_created":"2019-09-29T22:00:44Z","year":"2020","arxiv":1,"title":"An efficient algorithm for computing network reliability in small treewidth","external_id":{"isi":["000501641400050"],"arxiv":["1712.09692"]},"_id":"6918","date_published":"2020-01-01T00:00:00Z"},{"year":"2019","arxiv":1,"title":"Termination of nondeterministic probabilistic programs","external_id":{"arxiv":["1701.02944"],"isi":["000931943000022"]},"_id":"5948","date_published":"2019-01-11T00:00:00Z","volume":11388,"language":[{"iso":"eng"}],"intvolume":"     11388","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1701.02944"}],"OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","month":"01","type":"conference","date_created":"2019-02-10T22:59:17Z","quality_controlled":"1","author":[{"last_name":"Fu","full_name":"Fu, Hongfei","first_name":"Hongfei"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"}],"date_updated":"2025-07-03T11:45:45Z","project":[{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"},{"call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"citation":{"apa":"Fu, H., &#38; Chatterjee, K. (2019). Termination of nondeterministic probabilistic programs. In <i>International Conference on Verification, Model Checking, and Abstract Interpretation</i> (Vol. 11388, pp. 468–490). Cascais, Portugal: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-11245-5_22\">https://doi.org/10.1007/978-3-030-11245-5_22</a>","short":"H. Fu, K. Chatterjee, in:, International Conference on Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2019, pp. 468–490.","chicago":"Fu, Hongfei, and Krishnendu Chatterjee. “Termination of Nondeterministic Probabilistic Programs.” In <i>International Conference on Verification, Model Checking, and Abstract Interpretation</i>, 11388:468–90. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-11245-5_22\">https://doi.org/10.1007/978-3-030-11245-5_22</a>.","ista":"Fu H, Chatterjee K. 2019. Termination of nondeterministic probabilistic programs. International Conference on Verification, Model Checking, and Abstract Interpretation. VMCAI: Verification, Model Checking, and Abstract Interpretation, LNCS, vol. 11388, 468–490.","ieee":"H. Fu and K. Chatterjee, “Termination of nondeterministic probabilistic programs,” in <i>International Conference on Verification, Model Checking, and Abstract Interpretation</i>, Cascais, Portugal, 2019, vol. 11388, pp. 468–490.","mla":"Fu, Hongfei, and Krishnendu Chatterjee. “Termination of Nondeterministic Probabilistic Programs.” <i>International Conference on Verification, Model Checking, and Abstract Interpretation</i>, vol. 11388, Springer Nature, 2019, pp. 468–90, doi:<a href=\"https://doi.org/10.1007/978-3-030-11245-5_22\">10.1007/978-3-030-11245-5_22</a>.","ama":"Fu H, Chatterjee K. Termination of nondeterministic probabilistic programs. In: <i>International Conference on Verification, Model Checking, and Abstract Interpretation</i>. Vol 11388. Springer Nature; 2019:468-490. doi:<a href=\"https://doi.org/10.1007/978-3-030-11245-5_22\">10.1007/978-3-030-11245-5_22</a>"},"publisher":"Springer Nature","status":"public","OA_type":"green","oa":1,"alternative_title":["LNCS"],"scopus_import":"1","publication":"International Conference on Verification, Model Checking, and Abstract Interpretation","conference":{"start_date":"2019-01-13","end_date":"2019-01-15","location":"Cascais, Portugal","name":"VMCAI: Verification, Model Checking, and Abstract Interpretation"},"isi":1,"department":[{"_id":"KrCh"}],"day":"11","doi":"10.1007/978-3-030-11245-5_22","publication_status":"published","abstract":[{"text":"We study the termination problem for nondeterministic probabilistic programs. We consider the bounded termination problem that asks whether the supremum of the expected termination time over all schedulers is bounded. First, we show that ranking supermartingales (RSMs) are both sound and complete for proving bounded termination over nondeterministic probabilistic programs. For nondeterministic probabilistic programs a previous result claimed that RSMs are not complete for bounded termination, whereas our result corrects the previous flaw and establishes completeness with a rigorous proof. Second, we present the first sound approach to establish lower bounds on expected termination time through RSMs.","lang":"eng"}],"page":"468-490","oa_version":"Preprint"},{"citation":{"ista":"Chatterjee K, Pavlogiannis A, Toman V. 2019. Value-centric dynamic partial order reduction. Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications. OOPSLA: Object-oriented Programming, Systems, Languages and Applications vol. 3, 124.","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, and Viktor Toman. “Value-Centric Dynamic Partial Order Reduction.” In <i>Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications</i>, Vol. 3. ACM, 2019. <a href=\"https://doi.org/10.1145/3360550\">https://doi.org/10.1145/3360550</a>.","ieee":"K. Chatterjee, A. Pavlogiannis, and V. Toman, “Value-centric dynamic partial order reduction,” in <i>Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications</i>, Athens, Greece, 2019, vol. 3.","short":"K. Chatterjee, A. Pavlogiannis, V. Toman, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM, 2019.","apa":"Chatterjee, K., Pavlogiannis, A., &#38; Toman, V. (2019). Value-centric dynamic partial order reduction. In <i>Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications</i> (Vol. 3). Athens, Greece: ACM. <a href=\"https://doi.org/10.1145/3360550\">https://doi.org/10.1145/3360550</a>","ama":"Chatterjee K, Pavlogiannis A, Toman V. Value-centric dynamic partial order reduction. In: <i>Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications</i>. Vol 3. ACM; 2019. doi:<a href=\"https://doi.org/10.1145/3360550\">10.1145/3360550</a>","mla":"Chatterjee, Krishnendu, et al. “Value-Centric Dynamic Partial Order Reduction.” <i>Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications</i>, vol. 3, 124, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3360550\">10.1145/3360550</a>."},"related_material":{"record":[{"relation":"dissertation_contains","id":"10199","status":"public"}]},"publisher":"ACM","date_updated":"2026-04-08T07:00:31Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"},{"full_name":"Toman, Viktor","first_name":"Viktor","id":"3AF3DA7C-F248-11E8-B48F-1D18A9856A87","last_name":"Toman","orcid":"0000-0001-9036-063X"}],"project":[{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF"},{"call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","scopus_import":"1","publication":"Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications","acknowledgement":"The authors would also like to thank anonymous referees for their valuable comments and helpful suggestions. This work is supported by the Austrian Science Fund (FWF) NFN grants S11407-N23 (RiSE/SHiNE) and S11402-N23 (RiSE/SHiNE), by the Vienna Science and Technology Fund (WWTF) Project ICT15-003, and by the Austrian Science Fund (FWF) Schrodinger grant J-4220.\r\n","oa":1,"OA_type":"hybrid","status":"public","publication_identifier":{"eissn":["2475-1421"]},"article_number":"124","doi":"10.1145/3360550","has_accepted_license":"1","day":"10","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"conference":{"end_date":"2019-10-25","start_date":"2019-10-23","name":"OOPSLA: Object-oriented Programming, Systems, Languages and Applications","location":"Athens, Greece"},"oa_version":"Published Version","abstract":[{"text":"The verification of concurrent programs remains an open challenge, as thread interaction has to be accounted for, which leads to state-space explosion. Stateless model checking battles this problem by exploring traces rather than states of the program. As there are exponentially many traces, dynamic partial-order reduction (DPOR) techniques are used to partition the trace space into equivalence classes, and explore a few representatives from each class. The standard equivalence that underlies most DPOR techniques is the happens-before equivalence, however recent works have spawned a vivid interest towards coarser equivalences. The efficiency of such approaches is a product of two parameters: (i) the size of the partitioning induced by the equivalence, and (ii) the time spent by the exploration algorithm in each class of the partitioning. In this work, we present a new equivalence, called value-happens-before and show that it has two appealing features. First, value-happens-before is always at least as coarse as the happens-before equivalence, and can be even exponentially coarser. Second, the value-happens-before partitioning is efficiently explorable when the number of threads is bounded. We present an algorithm called value-centric DPOR (VCDPOR), which explores the underlying partitioning using polynomial time per class. Finally, we perform an experimental evaluation of VCDPOR on various benchmarks, and compare it against other state-of-the-art approaches. Our results show that value-happens-before typically induces a significant reduction in the size of the underlying partitioning, which leads to a considerable reduction in the running time for exploring the whole partitioning.","lang":"eng"}],"corr_author":"1","keyword":["safety","risk","reliability and quality","software"],"ddc":["000"],"publication_status":"published","external_id":{"arxiv":["1909.00989"]},"file_date_updated":"2021-11-12T11:41:56Z","arxiv":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"title":"Value-centric dynamic partial order reduction","year":"2019","date_published":"2019-10-10T00:00:00Z","_id":"10190","OA_place":"publisher","language":[{"iso":"eng"}],"intvolume":"         3","volume":3,"date_created":"2021-10-27T14:57:06Z","type":"conference","month":"10","file":[{"access_level":"open_access","creator":"cchlebak","date_created":"2021-11-12T11:41:56Z","content_type":"application/pdf","file_size":570829,"checksum":"2149979c46964c4d117af06ccb6c0834","success":1,"file_id":"10278","relation":"main_file","date_updated":"2021-11-12T11:41:56Z","file_name":"2019_ACM_Chatterjee.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No"},{"department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"language":[{"iso":"eng"}],"day":"16","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.06981"}],"doi":"10.48550/arXiv.1903.06981","article_number":"1903.06981","article_processing_charge":"No","publication_status":"draft","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"03","abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex.  The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete.  We present some partial results:\r\n1.  An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2.  Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3.  Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.\r\n3.  A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars.  In this version, tokens and  vertices  have  colours,  and  colours  have  weights.   The  goal  is  to  get  every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"type":"preprint","date_created":"2020-06-08T12:25:25Z","oa_version":"Preprint","year":"2019","title":"Token swapping on trees","arxiv":1,"date_updated":"2026-04-08T07:23:00Z","author":[{"first_name":"Ahmad","full_name":"Biniaz, Ahmad","last_name":"Biniaz"},{"first_name":"Kshitij","full_name":"Jain, Kshitij","last_name":"Jain"},{"last_name":"Lubiw","full_name":"Lubiw, Anna","first_name":"Anna"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","last_name":"Masárová","full_name":"Masárová, Zuzana","first_name":"Zuzana"},{"last_name":"Miltzow","full_name":"Miltzow, Tillmann","first_name":"Tillmann"},{"first_name":"Debajyoti","full_name":"Mondal, Debajyoti","last_name":"Mondal"},{"first_name":"Anurag Murty","full_name":"Naredla, Anurag Murty","last_name":"Naredla"},{"first_name":"Josef","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","orcid":"0000-0002-1097-9684"},{"first_name":"Alexi","full_name":"Turcotte, Alexi","last_name":"Turcotte"}],"citation":{"apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.1903.06981\">https://doi.org/10.48550/arXiv.1903.06981</a>","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.1903.06981\">https://doi.org/10.48550/arXiv.1903.06981</a>.","ieee":"A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>arXiv</i>. .","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>ArXiv</i>, 1903.06981, doi:<a href=\"https://doi.org/10.48550/arXiv.1903.06981\">10.48550/arXiv.1903.06981</a>.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.1903.06981\">10.48550/arXiv.1903.06981</a>"},"related_material":{"record":[{"relation":"later_version","status":"public","id":"12833"},{"id":"7944","status":"public","relation":"dissertation_contains"}]},"external_id":{"arxiv":["1903.06981"]},"status":"public","oa":1,"_id":"7950","date_published":"2019-03-16T00:00:00Z","publication":"arXiv"},{"publication":"31st International Conference on Computer-Aided Verification","scopus_import":"1","alternative_title":["LNCS"],"publication_identifier":{"isbn":["9783030255398"],"issn":["0302-9743"]},"status":"public","oa":1,"author":[{"first_name":"Guy","full_name":"Avni, Guy","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","last_name":"Avni","orcid":"0000-0001-5588-8287"},{"last_name":"Bloem","full_name":"Bloem, Roderick","first_name":"Roderick"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"},{"last_name":"Konighofer","full_name":"Konighofer, Bettina","first_name":"Bettina"},{"last_name":"Pranger","full_name":"Pranger, Stefan","first_name":"Stefan"}],"project":[{"call_identifier":"FWF","_id":"264B3912-B435-11E9-9278-68D0E5697425","grant_number":"M02369","name":"Formal Methods meets Algorithmic Game Theory"},{"grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"date_updated":"2025-04-15T06:26:05Z","citation":{"ama":"Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. Run-time optimization for learned controllers through quantitative games. In: <i>31st International Conference on Computer-Aided Verification</i>. Vol 11561. Springer; 2019:630-649. doi:<a href=\"https://doi.org/10.1007/978-3-030-25540-4_36\">10.1007/978-3-030-25540-4_36</a>","mla":"Avni, Guy, et al. “Run-Time Optimization for Learned Controllers through Quantitative Games.” <i>31st International Conference on Computer-Aided Verification</i>, vol. 11561, Springer, 2019, pp. 630–49, doi:<a href=\"https://doi.org/10.1007/978-3-030-25540-4_36\">10.1007/978-3-030-25540-4_36</a>.","ista":"Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. 2019. Run-time optimization for learned controllers through quantitative games. 31st International Conference on Computer-Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 11561, 630–649.","ieee":"G. Avni, R. Bloem, K. Chatterjee, T. A. Henzinger, B. Konighofer, and S. Pranger, “Run-time optimization for learned controllers through quantitative games,” in <i>31st International Conference on Computer-Aided Verification</i>, New York, NY, United States, 2019, vol. 11561, pp. 630–649.","chicago":"Avni, Guy, Roderick Bloem, Krishnendu Chatterjee, Thomas A Henzinger, Bettina Konighofer, and Stefan Pranger. “Run-Time Optimization for Learned Controllers through Quantitative Games.” In <i>31st International Conference on Computer-Aided Verification</i>, 11561:630–49. Springer, 2019. <a href=\"https://doi.org/10.1007/978-3-030-25540-4_36\">https://doi.org/10.1007/978-3-030-25540-4_36</a>.","short":"G. Avni, R. Bloem, K. Chatterjee, T.A. Henzinger, B. Konighofer, S. Pranger, in:, 31st International Conference on Computer-Aided Verification, Springer, 2019, pp. 630–649.","apa":"Avni, G., Bloem, R., Chatterjee, K., Henzinger, T. A., Konighofer, B., &#38; Pranger, S. (2019). Run-time optimization for learned controllers through quantitative games. In <i>31st International Conference on Computer-Aided Verification</i> (Vol. 11561, pp. 630–649). New York, NY, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-030-25540-4_36\">https://doi.org/10.1007/978-3-030-25540-4_36</a>"},"publisher":"Springer","quality_controlled":"1","oa_version":"Published Version","publication_status":"published","ddc":["000"],"page":"630-649","abstract":[{"lang":"eng","text":"A controller is a device that interacts with a plant. At each time point,it reads the plant’s state and issues commands with the goal that the plant oper-ates optimally. Constructing optimal controllers is a fundamental and challengingproblem. Machine learning techniques have recently been successfully applied totrain controllers, yet they have limitations. Learned controllers are monolithic andhard to reason about. In particular, it is difficult to add features without retraining,to guarantee any level of performance, and to achieve acceptable performancewhen encountering untrained scenarios. These limitations can be addressed bydeploying quantitative run-timeshieldsthat serve as a proxy for the controller.At each time point, the shield reads the command issued by the controller andmay choose to alter it before passing it on to the plant. We show how optimalshields that interfere as little as possible while guaranteeing a desired level ofcontroller performance, can be generated systematically and automatically usingreactive  synthesis.  First,  we  abstract  the  plant  by  building  a  stochastic  model.Second, we consider the learned controller to be a black box. Third, we mea-surecontroller performanceandshield interferenceby two quantitative run-timemeasures that are formally defined using weighted automata. Then, the problemof constructing a shield that guarantees maximal performance with minimal inter-ference is the problem of finding an optimal strategy in a stochastic2-player game“controller versus shield” played on the abstract state space of the plant with aquantitative objective obtained from combining the performance and interferencemeasures. We illustrate the effectiveness of our approach by automatically con-structing lightweight shields for learned traffic-light controllers in various roadnetworks. The shields we generate avoid liveness bugs, improve controller per-formance in untrained and changing traffic situations, and add features to learnedcontrollers, such as giving priority to emergency vehicles."}],"corr_author":"1","has_accepted_license":"1","day":"12","doi":"10.1007/978-3-030-25540-4_36","conference":{"name":"CAV: Computer Aided Verification","location":"New York, NY, United States","end_date":"2019-07-18","start_date":"2019-07-13"},"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"isi":1,"_id":"6462","date_published":"2019-07-12T00:00:00Z","file_date_updated":"2020-07-14T12:47:31Z","external_id":{"isi":["000491468000036"]},"year":"2019","title":"Run-time optimization for learned controllers through quantitative games","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"conference","date_created":"2019-05-16T11:22:30Z","article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","file":[{"checksum":"c231579f2485c6fd4df17c9443a4d80b","file_size":659766,"content_type":"application/pdf","creator":"dernst","date_created":"2019-08-14T09:35:24Z","access_level":"open_access","file_name":"2019_CAV_Avni.pdf","date_updated":"2020-07-14T12:47:31Z","relation":"main_file","file_id":"6816"}],"month":"07","volume":11561,"language":[{"iso":"eng"}],"intvolume":"     11561"},{"author":[{"last_name":"Hauser","full_name":"Hauser, Oliver P.","first_name":"Oliver P."},{"full_name":"Hilbe, Christian","first_name":"Christian","orcid":"0000-0001-5116-955X","last_name":"Hilbe","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"last_name":"Nowak","full_name":"Nowak, Martin A.","first_name":"Martin A."}],"date_updated":"2025-07-10T11:53:55Z","project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"publisher":"Springer Nature","related_material":{"link":[{"relation":"press_release","description":"News on IST Homepage","url":"https://ist.ac.at/en/news/too-much-inequality-impedes-support-for-public-goods-according-to-research-published-in-nature/"}]},"citation":{"apa":"Hauser, O. P., Hilbe, C., Chatterjee, K., &#38; Nowak, M. A. (2019). Social dilemmas among unequals. <i>Nature</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41586-019-1488-5\">https://doi.org/10.1038/s41586-019-1488-5</a>","short":"O.P. Hauser, C. Hilbe, K. Chatterjee, M.A. Nowak, Nature 572 (2019) 524–527.","ieee":"O. P. Hauser, C. Hilbe, K. Chatterjee, and M. A. Nowak, “Social dilemmas among unequals,” <i>Nature</i>, vol. 572, no. 7770. Springer Nature, pp. 524–527, 2019.","ista":"Hauser OP, Hilbe C, Chatterjee K, Nowak MA. 2019. Social dilemmas among unequals. Nature. 572(7770), 524–527.","chicago":"Hauser, Oliver P., Christian Hilbe, Krishnendu Chatterjee, and Martin A. Nowak. “Social Dilemmas among Unequals.” <i>Nature</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1038/s41586-019-1488-5\">https://doi.org/10.1038/s41586-019-1488-5</a>.","mla":"Hauser, Oliver P., et al. “Social Dilemmas among Unequals.” <i>Nature</i>, vol. 572, no. 7770, Springer Nature, 2019, pp. 524–27, doi:<a href=\"https://doi.org/10.1038/s41586-019-1488-5\">10.1038/s41586-019-1488-5</a>.","ama":"Hauser OP, Hilbe C, Chatterjee K, Nowak MA. Social dilemmas among unequals. <i>Nature</i>. 2019;572(7770):524-527. doi:<a href=\"https://doi.org/10.1038/s41586-019-1488-5\">10.1038/s41586-019-1488-5</a>"},"quality_controlled":"1","ec_funded":1,"publication":"Nature","scopus_import":"1","status":"public","publication_identifier":{"issn":["0028-0836"],"eissn":["1476-4687"]},"oa":1,"has_accepted_license":"1","day":"22","doi":"10.1038/s41586-019-1488-5","isi":1,"department":[{"_id":"KrCh"}],"oa_version":"Submitted Version","ddc":["000"],"publication_status":"published","abstract":[{"lang":"eng","text":"Direct reciprocity is a powerful mechanism for the evolution of cooperation on the basis of repeated interactions1,2,3,4. It requires that interacting individuals are sufficiently equal, such that everyone faces similar consequences when they cooperate or defect. Yet inequality is ubiquitous among humans5,6 and is generally considered to undermine cooperation and welfare7,8,9,10. Most previous models of reciprocity do not include inequality11,12,13,14,15. These models assume that individuals are the same in all relevant aspects. Here we introduce a general framework to study direct reciprocity among unequal individuals. Our model allows for multiple sources of inequality. Subjects can differ in their endowments, their productivities and in how much they benefit from public goods. We find that extreme inequality prevents cooperation. But if subjects differ in productivity, some endowment inequality can be necessary for cooperation to prevail. Our mathematical predictions are supported by a behavioural experiment in which we vary the endowments and productivities of the subjects. We observe that overall welfare is maximized when the two sources of heterogeneity are aligned, such that more productive individuals receive higher endowments. By contrast, when endowments and productivities are misaligned, cooperation quickly breaks down. Our findings have implications for policy-makers concerned with equity, efficiency and the provisioning of public goods."}],"page":"524-527","file_date_updated":"2020-07-14T12:47:42Z","external_id":{"isi":["000482219600045"]},"year":"2019","title":"Social dilemmas among unequals","_id":"6836","date_published":"2019-08-22T00:00:00Z","issue":"7770","volume":572,"language":[{"iso":"eng"}],"intvolume":"       572","type":"journal_article","date_created":"2019-09-01T22:00:56Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","file":[{"checksum":"a6e0e3168bf62de624e7772cdfaeb26f","creator":"dernst","date_created":"2020-05-14T10:00:32Z","access_level":"open_access","content_type":"application/pdf","file_size":18577756,"file_name":"2019_Nature_Hauser.pdf","file_id":"7828","relation":"main_file","date_updated":"2020-07-14T12:47:42Z"}],"article_type":"letter_note","month":"08"},{"conference":{"start_date":"2019-08-26","end_date":"2019-08-30","name":"MFCS: Mathematical Foundations of Computer Science","location":"Aachen, Germany"},"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"day":"01","has_accepted_license":"1","doi":"10.4230/LIPICS.MFCS.2019.11","article_number":"11","publication_status":"published","ddc":["004"],"corr_author":"1","abstract":[{"lang":"eng","text":"In two-player games on graphs, the players move a token through a graph to produce a finite or infinite path, which determines the qualitative winner or quantitative payoff of the game. We study bidding games in which the players bid for the right to move the token. Several bidding rules were studied previously. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the \"bank\" rather than the other player. Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant tau in [0,1]: portion tau of the winning bid is paid to the other player, and portion 1-tau to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games. It was previously shown that both Richman and poorman infinite-duration games with qualitative objectives reduce to reachability games, and we show a similar result here. Our most interesting results concern quantitative taxman games, namely mean-payoff games, where poorman and Richman bidding differ significantly. A central quantity in these games is the ratio between the two players' initial budgets. While in poorman mean-payoff games, the optimal payoff of a player depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with random-turn games in which in each turn, instead of bidding, a coin is tossed to determine which player moves. While the value with Richman bidding equals the value of a random-turn game with an un-biased coin, with poorman bidding, the bias in the coin is the initial ratio of the budgets. We give a complete classification of mean-payoff taxman games that is based on a probabilistic connection: the value of a taxman bidding game with parameter tau and initial ratio r, equals the value of a random-turn game that uses a coin with bias F(tau, r) = (r+tau * (1-r))/(1+tau). Thus, we show that Richman bidding is the exception; namely, for every tau <1, the value of the game depends on the initial ratio. Our proof technique simplifies and unifies the previous proof techniques for both Richman and poorman bidding. "}],"oa_version":"Published Version","ec_funded":1,"quality_controlled":"1","author":[{"first_name":"Guy","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"full_name":"Zikelic, Dorde","first_name":"Dorde","last_name":"Zikelic","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2025-07-10T11:53:57Z","project":[{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","name":"International IST Doctoral Program"},{"call_identifier":"FWF","name":"Formal Methods meets Algorithmic Game Theory","_id":"264B3912-B435-11E9-9278-68D0E5697425","grant_number":"M02369"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"chicago":"Avni, Guy, Thomas A Henzinger, and Dorde Zikelic. “Bidding Mechanisms in Graph Games,” Vol. 138. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.MFCS.2019.11\">https://doi.org/10.4230/LIPICS.MFCS.2019.11</a>.","ista":"Avni G, Henzinger TA, Zikelic D. 2019. Bidding mechanisms in graph games. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 138, 11.","ieee":"G. Avni, T. A. Henzinger, and D. Zikelic, “Bidding mechanisms in graph games,” presented at the MFCS: Mathematical Foundations of Computer Science, Aachen, Germany, 2019, vol. 138.","apa":"Avni, G., Henzinger, T. A., &#38; Zikelic, D. (2019). Bidding mechanisms in graph games (Vol. 138). Presented at the MFCS: Mathematical Foundations of Computer Science, Aachen, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.MFCS.2019.11\">https://doi.org/10.4230/LIPICS.MFCS.2019.11</a>","short":"G. Avni, T.A. Henzinger, D. Zikelic, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","ama":"Avni G, Henzinger TA, Zikelic D. Bidding mechanisms in graph games. In: Vol 138. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:<a href=\"https://doi.org/10.4230/LIPICS.MFCS.2019.11\">10.4230/LIPICS.MFCS.2019.11</a>","mla":"Avni, Guy, et al. <i>Bidding Mechanisms in Graph Games</i>. Vol. 138, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:<a href=\"https://doi.org/10.4230/LIPICS.MFCS.2019.11\">10.4230/LIPICS.MFCS.2019.11</a>."},"related_material":{"record":[{"status":"public","id":"9239","relation":"later_version"}]},"status":"public","oa":1,"scopus_import":"1","alternative_title":["LIPIcs"],"volume":138,"intvolume":"       138","language":[{"iso":"eng"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_id":"6913","relation":"main_file","date_updated":"2020-07-14T12:47:42Z","file_name":"2019_LIPIcs_Avni.pdf","creator":"kschuh","date_created":"2019-09-27T11:45:15Z","access_level":"open_access","content_type":"application/pdf","file_size":554457,"checksum":"6346e116a4f4ed1414174d96d2c4fbd7"}],"month":"08","type":"conference","date_created":"2019-09-18T08:04:26Z","year":"2019","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"title":"Bidding mechanisms in graph games","arxiv":1,"file_date_updated":"2020-07-14T12:47:42Z","external_id":{"arxiv":["1905.03835"]},"_id":"6884","date_published":"2019-08-01T00:00:00Z"}]