[{"date_updated":"2025-06-02T08:53:44Z","citation":{"ama":"Chatterjee K, Dvoák W, Henzinger MH, Loitzenbauer V. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. In: <i>Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2016:197-206. doi:<a href=\"https://doi.org/10.1145/2933575.2935304\">10.1145/2933575.2935304</a>","apa":"Chatterjee, K., Dvoák, W., Henzinger, M. H., &#38; Loitzenbauer, V. (2016). Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. In <i>Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 197–206). New York, NY, USA: IEEE. <a href=\"https://doi.org/10.1145/2933575.2935304\">https://doi.org/10.1145/2933575.2935304</a>","chicago":"Chatterjee, Krishnendu, Wolfgang Dvoák, Monika H Henzinger, and Veronika Loitzenbauer. “Model and Objective Separation with Conditional Lower Bounds: Disjunction Is Harder than Conjunction.” In <i>Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 197–206. IEEE, 2016. <a href=\"https://doi.org/10.1145/2933575.2935304\">https://doi.org/10.1145/2933575.2935304</a>.","ieee":"K. Chatterjee, W. Dvoák, M. H. Henzinger, and V. Loitzenbauer, “Model and objective separation with conditional lower bounds: disjunction is harder than conjunction,” in <i>Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science</i>, New York, NY, USA, 2016, pp. 197–206.","short":"K. Chatterjee, W. Dvoák, M.H. Henzinger, V. Loitzenbauer, in:, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206.","mla":"Chatterjee, Krishnendu, et al. “Model and Objective Separation with Conditional Lower Bounds: Disjunction Is Harder than Conjunction.” <i>Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2016, pp. 197–206, doi:<a href=\"https://doi.org/10.1145/2933575.2935304\">10.1145/2933575.2935304</a>.","ista":"Chatterjee K, Dvoák W, Henzinger MH, Loitzenbauer V. 2016. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, , 197–206."},"year":"2016","external_id":{"arxiv":["1602.02670"]},"arxiv":1,"doi":"10.1145/2933575.2935304","day":"05","abstract":[{"text":"Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, graphs and Markov Decision Processes (MDPs), with respect to several fundamental -regular objectives, e.g., Rabin and Streett objectives. For many of these problems the best-known upper bounds are quadratic or cubic, yet no super-linear lower bounds are known. In this work our contributions are two-fold: First, we present several improved algorithms, and second, we present the first conditional super-linear lower bounds based on widely believed assumptions about the complexity of CNF-SAT and combinatorial Boolean matrix multiplication. A separation result for two models with respect to an objective means a conditional lower bound for one model that is strictly higher than the existing upper bound for the other model, and similarly for two objectives with respect to a model. Our results establish the following separation results: (1) A separation of models (graphs and MDPs) for disjunctive queries of reachability and Büchi objectives. (2) Two kinds of separations of objectives, both for graphs and MDPs, namely, (2a) the separation of dual objectives such as Streett/Rabin objectives, and (2b) the separation of conjunction and disjunction of multiple objectives of the same type such as safety, Büchi, and coBüchi. In summary, our results establish the first model and objective separation results for graphs and MDPs for various classical -regular objectives. Quite strikingly, we establish conditional lower bounds for the disjunction of objectives that are strictly higher than the existing upper bounds for the conjunction of the same objectives. © 2016 ACM.","lang":"eng"}],"acknowledgement":"K.  C.,  M.  H.,  and  W.  D.  are  partially  supported  by  the  Vienna\r\nScience and Technology Fund (WWTF) through project ICT15-003.\r\nK. C. is partially supported by the Austrian Science Fund (FWF)\r\nNFN Grant No S11407-N23 (RiSE/SHiNE) and an ERC Start grant\r\n(279307: Graph Games). For W. D., M. H., and V. L. the research\r\nleading to these results has received funding from the European\r\nResearch Council under the European Union’s Seventh Framework\r\nProgramme (FP/2007-2013) / ERC Grant Agreement no. 340506.","_id":"1140","scopus_import":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Dvoák, Wolfgang","first_name":"Wolfgang","last_name":"Dvoák"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Loitzenbauer, Veronika","first_name":"Veronika","last_name":"Loitzenbauer"}],"publication_status":"published","department":[{"_id":"KrCh"}],"article_processing_charge":"No","date_created":"2018-12-11T11:50:22Z","title":"Model and objective separation with conditional lower bounds: disjunction is harder than conjunction","alternative_title":["Proceedings Symposium on Logic in Computer Science"],"page":"197 - 206","quality_controlled":"1","publisher":"IEEE","date_published":"2016-07-05T00:00:00Z","type":"conference","oa":1,"publist_id":"6219","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.02670"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication":"Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science","oa_version":"Preprint","project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"}],"month":"07","language":[{"iso":"eng"}],"conference":{"end_date":"2016-07-08","location":"New York, NY, USA","name":"LICS: Logic in Computer Science","start_date":"2016-07-05"}},{"volume":2016,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5443"}],"link":[{"url":"https://dl.acm.org/citation.cfm?id=3016355","relation":"table_of_contents"}]},"year":"2016","citation":{"apa":"Chatterjee, K., Chmelik, M., &#38; Davies, J. (2016). A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps. In <i>Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence</i> (Vol. 2016, pp. 3225–3232). Phoenix, AZ, USA: AAAI Press.","ama":"Chatterjee K, Chmelik M, Davies J. A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps. In: <i>Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence</i>. Vol 2016. AAAI Press; 2016:3225-3232.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Jessica Davies. “A Symbolic SAT Based Algorithm for Almost Sure Reachability with Small Strategies in Pomdps.” In <i>Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence</i>, 2016:3225–32. AAAI Press, 2016.","ieee":"K. Chatterjee, M. Chmelik, and J. Davies, “A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps,” in <i>Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence</i>, Phoenix, AZ, USA, 2016, vol. 2016, pp. 3225–3232.","mla":"Chatterjee, Krishnendu, et al. “A Symbolic SAT Based Algorithm for Almost Sure Reachability with Small Strategies in Pomdps.” <i>Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence</i>, vol. 2016, AAAI Press, 2016, pp. 3225–32.","short":"K. Chatterjee, M. Chmelik, J. Davies, in:, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, 2016, pp. 3225–3232.","ista":"Chatterjee K, Chmelik M, Davies J. 2016. A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 2016, 3225–3232."},"date_updated":"2023-02-23T12:26:41Z","type":"conference","date_published":"2016-12-02T00:00:00Z","day":"02","publist_id":"6191","abstract":[{"lang":"eng","text":"POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIMEcomplete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved."}],"quality_controlled":"1","ec_funded":1,"page":"3225 - 3232","language":[{"iso":"eng"}],"publisher":"AAAI Press","conference":{"start_date":"2016-02-12","name":"AAAI: Conference on Artificial Intelligence","end_date":"2016-02-17","location":"Phoenix, AZ, USA"},"_id":"1166","publication":"Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"},{"id":"378E0060-F248-11E8-B48F-1D18A9856A87","full_name":"Davies, Jessica","first_name":"Jessica","last_name":"Davies"}],"date_created":"2018-12-11T11:50:30Z","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication_status":"published","oa_version":"None","intvolume":"      2016","title":"A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps","month":"12"},{"language":[{"iso":"eng"}],"conference":{"location":"The Hague, Netherlands","end_date":"2016-09-02","start_date":"2016-08-29","name":"ECAI: European Conference on Artificial Intelligence"},"has_accepted_license":"1","oa_version":"Published Version","month":"01","file":[{"creator":"system","file_id":"4658","relation":"main_file","access_level":"open_access","file_name":"IST-2018-950-v1+1_2016_Chatterjee_The_complexity.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:35Z","file_size":2116225,"checksum":"848043c812ace05e459579c923f3d3cf","date_created":"2018-12-12T10:07:59Z"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"date_published":"2016-01-01T00:00:00Z","type":"conference","publist_id":"7342","oa":1,"page":"1432 - 1439","quality_controlled":"1","file_date_updated":"2020-07-14T12:46:35Z","publisher":"IOS Press","_id":"478","scopus_import":1,"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","date_created":"2018-12-11T11:46:41Z","department":[{"_id":"KrCh"}],"alternative_title":["Frontiers in Artificial Intelligence and Applications"],"pubrep_id":"950","title":"The complexity of deciding legality of a single step of magic: The gathering","intvolume":"       285","volume":285,"ddc":["004"],"date_updated":"2021-01-12T08:00:54Z","year":"2016","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, in:, IOS Press, 2016, pp. 1432–1439.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Deciding Legality of a Single Step of Magic: The Gathering</i>. Vol. 285, IOS Press, 2016, pp. 1432–39, doi:<a href=\"https://doi.org/10.3233/978-1-61499-672-9-1432\">10.3233/978-1-61499-672-9-1432</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2016. The complexity of deciding legality of a single step of magic: The gathering. ECAI: European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, vol. 285, 1432–1439.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2016). The complexity of deciding legality of a single step of magic: The gathering (Vol. 285, pp. 1432–1439). Presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands: IOS Press. <a href=\"https://doi.org/10.3233/978-1-61499-672-9-1432\">https://doi.org/10.3233/978-1-61499-672-9-1432</a>","ama":"Chatterjee K, Ibsen-Jensen R. The complexity of deciding legality of a single step of magic: The gathering. In: Vol 285. IOS Press; 2016:1432-1439. doi:<a href=\"https://doi.org/10.3233/978-1-61499-672-9-1432\">10.3233/978-1-61499-672-9-1432</a>","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Deciding Legality of a Single Step of Magic: The Gathering,” 285:1432–39. IOS Press, 2016. <a href=\"https://doi.org/10.3233/978-1-61499-672-9-1432\">https://doi.org/10.3233/978-1-61499-672-9-1432</a>.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The complexity of deciding legality of a single step of magic: The gathering,” presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands, 2016, vol. 285, pp. 1432–1439."},"doi":"10.3233/978-1-61499-672-9-1432","day":"01","abstract":[{"lang":"eng","text":"Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic."}]},{"language":[{"iso":"eng"}],"conference":{"start_date":"2016-07-05","name":"LICS: Logic in Computer Science","end_date":"2016-07-08","location":"New York, NY, USA"},"oa_version":"Preprint","project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"}],"month":"07","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.06376"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","date_published":"2016-07-05T00:00:00Z","type":"conference","publist_id":"7340","oa":1,"page":"247 - 256","ec_funded":1,"quality_controlled":"1","publisher":"IEEE","_id":"480","scopus_import":1,"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}],"publication_status":"published","date_created":"2018-12-11T11:46:42Z","department":[{"_id":"KrCh"}],"title":"Perfect-information stochastic games with generalized mean-payoff objectives","alternative_title":["Proceedings Symposium on Logic in Computer Science"],"volume":"05-08-July-2016","date_updated":"2021-01-12T08:00:56Z","citation":{"apa":"Chatterjee, K., &#38; Doyen, L. (2016). Perfect-information stochastic games with generalized mean-payoff objectives (Vol. 05-08-July-2016, pp. 247–256). Presented at the LICS: Logic in Computer Science, New York, NY, USA: IEEE. <a href=\"https://doi.org/10.1145/2933575.2934513\">https://doi.org/10.1145/2933575.2934513</a>","ama":"Chatterjee K, Doyen L. Perfect-information stochastic games with generalized mean-payoff objectives. In: Vol 05-08-July-2016. IEEE; 2016:247-256. doi:<a href=\"https://doi.org/10.1145/2933575.2934513\">10.1145/2933575.2934513</a>","ieee":"K. Chatterjee and L. Doyen, “Perfect-information stochastic games with generalized mean-payoff objectives,” presented at the LICS: Logic in Computer Science, New York, NY, USA, 2016, vol. 05-08-July-2016, pp. 247–256.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives,” 05-08-July-2016:247–56. IEEE, 2016. <a href=\"https://doi.org/10.1145/2933575.2934513\">https://doi.org/10.1145/2933575.2934513</a>.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives</i>. Vol. 05-08-July-2016, IEEE, 2016, pp. 247–56, doi:<a href=\"https://doi.org/10.1145/2933575.2934513\">10.1145/2933575.2934513</a>.","short":"K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256.","ista":"Chatterjee K, Doyen L. 2016. Perfect-information stochastic games with generalized mean-payoff objectives. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, vol. 05-08-July-2016, 247–256."},"year":"2016","doi":"10.1145/2933575.2934513","day":"05","abstract":[{"text":"Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements.","lang":"eng"}]},{"doi":"10.15479/AT:IST-2016-523-v1-1","day":"31","publication_identifier":{"issn":["2664-1690"]},"abstract":[{"text":"We consider the quantitative analysis problem for interprocedural control-flow graphs (ICFGs). The input consists of an ICFG, a positive weight function that assigns every transition a positive integer-valued number, and a labelling of the transitions (events) as good, bad, and neutral events. The weight function assigns to each transition a numerical value that represents ameasure of how good or bad an event is. The quantitative analysis problem asks whether there is a run of the ICFG where the ratio of the sum of the numerical weights of good events versus the sum of weights of bad events in the long-run is at least a given threshold (or equivalently, to compute the maximal ratio among all valid paths in the ICFG). The quantitative analysis problem for ICFGs can be solved in polynomial time, and we present an efficient and practical algorithm for the problem. We show that several problems relevant for static program analysis, such as estimating the worst-case execution time of a program or the average energy consumption of a mobile application, can be modeled in our framework. We have implemented our algorithm as a tool in the Java Soot framework. We demonstrate the effectiveness of our approach with two case studies. First, we show that our framework provides a sound approach (no false positives) for the analysis of inefficiently-used containers. Second, we show that our approach can also be used for static profiling of programs which reasons about methods that are frequently invoked. Our experimental results show that our tool scales to relatively large benchmarks, and discovers relevant and useful information that can be used to optimize performance of the programs. ","lang":"eng"}],"oa":1,"date_updated":"2023-02-23T10:06:22Z","citation":{"ieee":"K. Chatterjee, A. Pavlogiannis, and Y. Velner, <i>Quantitative interprocedural analysis</i>. IST Austria, 2016.","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, and Yaron Velner. <i>Quantitative Interprocedural Analysis</i>. IST Austria, 2016. <a href=\"https://doi.org/10.15479/AT:IST-2016-523-v1-1\">https://doi.org/10.15479/AT:IST-2016-523-v1-1</a>.","ama":"Chatterjee K, Pavlogiannis A, Velner Y. <i>Quantitative Interprocedural Analysis</i>. IST Austria; 2016. doi:<a href=\"https://doi.org/10.15479/AT:IST-2016-523-v1-1\">10.15479/AT:IST-2016-523-v1-1</a>","apa":"Chatterjee, K., Pavlogiannis, A., &#38; Velner, Y. (2016). <i>Quantitative interprocedural analysis</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2016-523-v1-1\">https://doi.org/10.15479/AT:IST-2016-523-v1-1</a>","ista":"Chatterjee K, Pavlogiannis A, Velner Y. 2016. Quantitative interprocedural analysis, IST Austria, 33p.","mla":"Chatterjee, Krishnendu, et al. <i>Quantitative Interprocedural Analysis</i>. IST Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:IST-2016-523-v1-1\">10.15479/AT:IST-2016-523-v1-1</a>.","short":"K. Chatterjee, A. Pavlogiannis, Y. Velner, Quantitative Interprocedural Analysis, IST Austria, 2016."},"year":"2016","date_published":"2016-03-31T00:00:00Z","type":"technical_report","file":[{"date_created":"2018-12-12T11:53:52Z","checksum":"cef516fa091925b5868813e355268fb4","file_size":1012204,"date_updated":"2020-07-14T12:46:58Z","content_type":"application/pdf","file_name":"IST-2016-523-v1+1_main.pdf","access_level":"open_access","relation":"main_file","file_id":"5513","creator":"system"}],"ddc":["005"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"status":"public","relation":"later_version","id":"1604"}]},"oa_version":"Published Version","publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:22Z","pubrep_id":"523","month":"03","title":"Quantitative interprocedural analysis","alternative_title":["IST Austria Technical Report"],"_id":"5445","has_accepted_license":"1","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas"},{"full_name":"Velner, Yaron","last_name":"Velner","first_name":"Yaron"}],"publisher":"IST Austria","page":"33","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:58Z"},{"author":[{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas"},{"last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"has_accepted_license":"1","_id":"5449","title":"Amplification on undirected population structures: Comets beat stars","alternative_title":["IST Austria Technical Report"],"pubrep_id":"648","month":"11","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:24Z","publication_status":"published","oa_version":"Updated Version","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:58Z","page":"22","publisher":"IST Austria","type":"technical_report","date_published":"2016-11-09T00:00:00Z","year":"2016","citation":{"mla":"Pavlogiannis, Andreas, et al. <i>Amplification on Undirected Population Structures: Comets Beat Stars</i>. IST Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:IST-2016-648-v1-1\">10.15479/AT:IST-2016-648-v1-1</a>.","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Amplification on Undirected Population Structures: Comets Beat Stars, IST Austria, 2016.","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Amplification on undirected population structures: Comets beat stars, IST Austria, 22p.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., &#38; Nowak, M. (2016). <i>Amplification on undirected population structures: Comets beat stars</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2016-648-v1-1\">https://doi.org/10.15479/AT:IST-2016-648-v1-1</a>","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. <i>Amplification on Undirected Population Structures: Comets Beat Stars</i>. IST Austria; 2016. doi:<a href=\"https://doi.org/10.15479/AT:IST-2016-648-v1-1\">10.15479/AT:IST-2016-648-v1-1</a>","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. <i>Amplification on Undirected Population Structures: Comets Beat Stars</i>. IST Austria, 2016. <a href=\"https://doi.org/10.15479/AT:IST-2016-648-v1-1\">https://doi.org/10.15479/AT:IST-2016-648-v1-1</a>.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, <i>Amplification on undirected population structures: Comets beat stars</i>. IST Austria, 2016."},"date_updated":"2023-02-23T12:22:21Z","oa":1,"abstract":[{"text":"The fixation probability is the probability that a new mutant introduced in a homogeneous population eventually takes over the entire population.\r\nThe fixation probability is a fundamental quantity of natural selection, and known to depend on the population structure.\r\nAmplifiers of natural selection are population structures which increase the fixation probability of advantageous mutants, as compared to the baseline case of well-mixed populations. In this work we focus on symmetric population structures represented as undirected graphs. In the regime of undirected graphs, the strongest amplifier known has been the Star graph, and the existence of undirected graphs with stronger amplification properties has remained open for over a decade.\r\nIn this work we present the Comet and Comet-swarm families of undirected graphs. We show that for a range of fitness values of the mutants, the Comet and Comet-swarm graphs have fixation probability strictly larger than the fixation probability of the Star graph, for fixed population size and at the limit of large populations, respectively.","lang":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"day":"09","doi":"10.15479/AT:IST-2016-648-v1-1","ddc":["519"],"related_material":{"record":[{"status":"public","relation":"later_version","id":"512"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"system","file_id":"5529","relation":"main_file","access_level":"open_access","file_name":"IST-2016-648-v1+1_tr.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:58Z","file_size":1264221,"checksum":"8345a8c1e7d7f0cd92516d182b7fc59e","date_created":"2018-12-12T11:54:07Z"}]},{"oa":1,"doi":"10.15479/AT:IST-2016-728-v1-1","publication_identifier":{"issn":["2664-1690"]},"day":"30","date_published":"2016-12-30T00:00:00Z","type":"technical_report","date_updated":"2023-02-23T12:27:05Z","year":"2016","citation":{"ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, <i>Strong amplifiers of natural selection</i>. IST Austria, 2016.","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. <i>Strong Amplifiers of Natural Selection</i>. IST Austria, 2016. <a href=\"https://doi.org/10.15479/AT:IST-2016-728-v1-1\">https://doi.org/10.15479/AT:IST-2016-728-v1-1</a>.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., &#38; Nowak, M. (2016). <i>Strong amplifiers of natural selection</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2016-728-v1-1\">https://doi.org/10.15479/AT:IST-2016-728-v1-1</a>","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. <i>Strong Amplifiers of Natural Selection</i>. IST Austria; 2016. doi:<a href=\"https://doi.org/10.15479/AT:IST-2016-728-v1-1\">10.15479/AT:IST-2016-728-v1-1</a>","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Strong amplifiers of natural selection, IST Austria, 34p.","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Strong Amplifiers of Natural Selection, IST Austria, 2016.","mla":"Pavlogiannis, Andreas, et al. <i>Strong Amplifiers of Natural Selection</i>. IST Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:IST-2016-728-v1-1\">10.15479/AT:IST-2016-728-v1-1</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"status":"public","file":[{"creator":"system","file_id":"5465","access_level":"open_access","relation":"main_file","file_name":"IST-2016-728-v1+1_main.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:59Z","file_size":1014732,"checksum":"7b8bb17c322c0556acba6ac169fa71c1","date_created":"2018-12-12T11:53:04Z"}],"title":"Strong amplifiers of natural selection","month":"12","alternative_title":["IST Austria Technical Report"],"pubrep_id":"728","oa_version":"Published Version","publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:24Z","author":[{"first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"_id":"5451","has_accepted_license":"1","publisher":"IST Austria","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:59Z","page":"34"},{"has_accepted_license":"1","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"oa_version":"Published Version","month":"12","language":[{"iso":"eng"}],"type":"technical_report","date_published":"2016-12-30T00:00:00Z","publication_identifier":{"issn":["2664-1690"]},"oa":1,"file":[{"relation":"main_file","access_level":"open_access","file_id":"5460","creator":"system","date_created":"2018-12-12T11:52:59Z","checksum":"58e895f26c82f560c0f0989bf8b08599","file_size":811558,"date_updated":"2020-07-14T12:46:59Z","file_name":"IST-2017-728-v2+1_main.pdf","content_type":"application/pdf"}],"related_material":{"record":[{"id":"5453","relation":"later_version","status":"public"},{"status":"public","id":"5559","relation":"popular_science"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","_id":"5452","author":[{"first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"department":[{"_id":"KrCh"}],"article_processing_charge":"No","date_created":"2018-12-12T11:39:25Z","publication_status":"published","title":"Arbitrarily strong amplifiers of natural selection","pubrep_id":"750","alternative_title":["IST Austria Technical Report"],"ec_funded":1,"page":"32","file_date_updated":"2020-07-14T12:46:59Z","publisher":"IST Austria","year":"2016","citation":{"short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016.","mla":"Pavlogiannis, Andreas, et al. <i>Arbitrarily Strong Amplifiers of Natural Selection</i>. IST Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-728-v2-1\">10.15479/AT:IST-2017-728-v2-1</a>.","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Arbitrarily strong amplifiers of natural selection, IST Austria, 32p.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., &#38; Nowak, M. (2016). <i>Arbitrarily strong amplifiers of natural selection</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2017-728-v2-1\">https://doi.org/10.15479/AT:IST-2017-728-v2-1</a>","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. <i>Arbitrarily Strong Amplifiers of Natural Selection</i>. IST Austria; 2016. doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-728-v2-1\">10.15479/AT:IST-2017-728-v2-1</a>","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. <i>Arbitrarily Strong Amplifiers of Natural Selection</i>. IST Austria, 2016. <a href=\"https://doi.org/10.15479/AT:IST-2017-728-v2-1\">https://doi.org/10.15479/AT:IST-2017-728-v2-1</a>.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, <i>Arbitrarily strong amplifiers of natural selection</i>. IST Austria, 2016."},"date_updated":"2024-02-21T13:48:42Z","day":"30","doi":"10.15479/AT:IST-2017-728-v2-1","ddc":["000"]},{"oa":1,"doi":"10.15479/AT:IST-2017-749-v3-1","day":"30","publication_identifier":{"issn":["2664-1690"]},"date_published":"2016-12-30T00:00:00Z","type":"technical_report","date_updated":"2023-02-23T12:27:07Z","citation":{"short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016.","mla":"Pavlogiannis, Andreas, et al. <i>Arbitrarily Strong Amplifiers of Natural Selection</i>. IST Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-749-v3-1\">10.15479/AT:IST-2017-749-v3-1</a>.","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Arbitrarily strong amplifiers of natural selection, IST Austria, 34p.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., &#38; Nowak, M. (2016). <i>Arbitrarily strong amplifiers of natural selection</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2017-749-v3-1\">https://doi.org/10.15479/AT:IST-2017-749-v3-1</a>","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. <i>Arbitrarily Strong Amplifiers of Natural Selection</i>. IST Austria; 2016. doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-749-v3-1\">10.15479/AT:IST-2017-749-v3-1</a>","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. <i>Arbitrarily Strong Amplifiers of Natural Selection</i>. IST Austria, 2016. <a href=\"https://doi.org/10.15479/AT:IST-2017-749-v3-1\">https://doi.org/10.15479/AT:IST-2017-749-v3-1</a>.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, <i>Arbitrarily strong amplifiers of natural selection</i>. IST Austria, 2016."},"year":"2016","related_material":{"record":[{"status":"public","id":"5452","relation":"earlier_version"}]},"ddc":["000"],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_created":"2018-12-12T11:53:13Z","checksum":"83b0313dab3bff4bdb6ac38695026fda","file_size":1015647,"date_updated":"2020-07-14T12:46:59Z","file_name":"IST-2017-749-v3+1_main.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5474","creator":"system"}],"pubrep_id":"755","alternative_title":["IST Austria Technical Report"],"title":"Arbitrarily strong amplifiers of natural selection","month":"12","publication_status":"published","oa_version":"Published Version","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:25Z","author":[{"id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"_id":"5453","has_accepted_license":"1","publisher":"IST Austria","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:59Z","page":"34"},{"related_material":{"record":[{"relation":"earlier_version","id":"5441","status":"public"},{"status":"public","relation":"earlier_version","id":"5442"},{"relation":"dissertation_contains","id":"821","status":"public"},{"relation":"later_version","id":"6009","status":"public"},{"status":"public","id":"8934","relation":"dissertation_contains"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1510.07565"}],"publist_id":"5761","oa":1,"type":"conference","date_published":"2016-01-11T00:00:00Z","conference":{"start_date":"2016-01-20","name":"POPL: Principles of Programming Languages","location":"St. Petersburg, FL, USA","end_date":"2016-01-22"},"language":[{"iso":"eng"}],"month":"01","project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","volume":"20-22","abstract":[{"text":"We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.","lang":"eng"}],"day":"11","arxiv":1,"doi":"10.1145/2837614.2837624","external_id":{"arxiv":["1510.07565"]},"citation":{"ieee":"K. Chatterjee, A. K. Goharshady, R. Ibsen-Jensen, and A. Pavlogiannis, “Algorithms for algebraic path properties in concurrent systems of constant treewidth components,” presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA, 2016, vol. 20–22, pp. 733–747.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components,” 20–22:733–47. ACM, 2016. <a href=\"https://doi.org/10.1145/2837614.2837624\">https://doi.org/10.1145/2837614.2837624</a>.","ama":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In: Vol 20-22. ACM; 2016:733-747. doi:<a href=\"https://doi.org/10.1145/2837614.2837624\">10.1145/2837614.2837624</a>","apa":"Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2016). Algorithms for algebraic path properties in concurrent systems of constant treewidth components (Vol. 20–22, pp. 733–747). Presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA: ACM. <a href=\"https://doi.org/10.1145/2837614.2837624\">https://doi.org/10.1145/2837614.2837624</a>","ista":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2016. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. POPL: Principles of Programming Languages, POPL, vol. 20–22, 733–747.","short":"K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, ACM, 2016, pp. 733–747.","mla":"Chatterjee, Krishnendu, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. Vol. 20–22, ACM, 2016, pp. 733–47, doi:<a href=\"https://doi.org/10.1145/2837614.2837624\">10.1145/2837614.2837624</a>."},"year":"2016","date_updated":"2024-03-25T23:30:18Z","publisher":"ACM","quality_controlled":"1","ec_funded":1,"page":"733 - 747","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","alternative_title":["POPL"],"date_created":"2018-12-11T11:52:01Z","department":[{"_id":"KrCh"}],"publication_status":"published","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Goharshady, Amir","orcid":"0000-0003-1702-6584","last_name":"Goharshady","first_name":"Amir","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis"}],"scopus_import":1,"_id":"1437"},{"conference":{"name":"POPL: Principles of Programming Languages","start_date":"2016-01-20","location":"St. Petersburg, FL, USA","end_date":"2016-01-22"},"language":[{"iso":"eng"}],"month":"01","oa_version":"Preprint","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"status":"public","id":"5993","relation":"later_version"}]},"main_file_link":[{"url":"http://arxiv.org/abs/1510.08517","open_access":"1"}],"oa":1,"publist_id":"5760","date_published":"2016-01-11T00:00:00Z","type":"conference","publisher":"ACM","page":"327 - 342","quality_controlled":"1","ec_funded":1,"title":"Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs","alternative_title":["POPL"],"publication_status":"published","date_created":"2018-12-11T11:52:01Z","department":[{"_id":"KrCh"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Fu","first_name":"Hongfei","full_name":"Fu, Hongfei","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87"},{"id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","last_name":"Novotny","first_name":"Petr","full_name":"Novotny, Petr"},{"first_name":"Rouzbeh","last_name":"Hasheminezhad","full_name":"Hasheminezhad, Rouzbeh"}],"_id":"1438","scopus_import":1,"volume":"20-22","acknowledgement":"Supported by the Natural Science Foundation of China (NSFC) under Grant No. 61532019 ","abstract":[{"text":"In this paper, we consider termination of probabilistic programs with real-valued variables. The questions concerned are: (a) qualitative ones that ask (i) whether the program terminates with probability 1 (almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); (b) quantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) to compute a bound B such that the probability to terminate after B steps decreases exponentially (concentration problem). To solve these questions, we utilize the notion of ranking supermartingales which is a powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmic synthesis of linear ranking-supermartingales over affine probabilistic programs (APP's) with both angelic and demonic non-determinism. An important subclass of APP's is LRAPP which is defined as the class of all APP's over which a linear ranking-supermartingale exists. Our main contributions are as follows. Firstly, we show that the membership problem of LRAPP (i) can be decided in polynomial time for APP's with at most demonic non-determinism, and (ii) is NP-hard and in PSPACE for APP's with angelic non-determinism; moreover, the NP-hardness result holds already for APP's without probability and demonic non-determinism. Secondly, we show that the concentration problem over LRAPP can be solved in the same complexity as for the membership problem of LRAPP. Finally, we show that the expectation problem over LRAPP can be solved in 2EXPTIME and is PSPACE-hard even for APP's without probability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate the effectiveness of our approach to answer the qualitative and quantitative questions over APP's with at most demonic non-determinism.","lang":"eng"}],"arxiv":1,"doi":"10.1145/2837614.2837639","day":"11","external_id":{"arxiv":["1510.08517"]},"date_updated":"2023-09-19T14:38:41Z","year":"2016","citation":{"ieee":"K. Chatterjee, H. Fu, P. Novotný, and R. Hasheminezhad, “Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs,” presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA, 2016, vol. 20–22, pp. 327–342.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, Petr Novotný, and Rouzbeh Hasheminezhad. “Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs,” 20–22:327–42. ACM, 2016. <a href=\"https://doi.org/10.1145/2837614.2837639\">https://doi.org/10.1145/2837614.2837639</a>.","ama":"Chatterjee K, Fu H, Novotný P, Hasheminezhad R. Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. In: Vol 20-22. ACM; 2016:327-342. doi:<a href=\"https://doi.org/10.1145/2837614.2837639\">10.1145/2837614.2837639</a>","apa":"Chatterjee, K., Fu, H., Novotný, P., &#38; Hasheminezhad, R. (2016). Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs (Vol. 20–22, pp. 327–342). Presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA: ACM. <a href=\"https://doi.org/10.1145/2837614.2837639\">https://doi.org/10.1145/2837614.2837639</a>","ista":"Chatterjee K, Fu H, Novotný P, Hasheminezhad R. 2016. Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. POPL: Principles of Programming Languages, POPL, vol. 20–22, 327–342.","short":"K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, in:, ACM, 2016, pp. 327–342.","mla":"Chatterjee, Krishnendu, et al. <i>Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs</i>. Vol. 20–22, ACM, 2016, pp. 327–42, doi:<a href=\"https://doi.org/10.1145/2837614.2837639\">10.1145/2837614.2837639</a>."}},{"abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples.","lang":"eng"}],"doi":"10.1016/j.jcss.2016.02.009","arxiv":1,"day":"01","external_id":{"arxiv":["1309.2802"]},"date_updated":"2023-02-23T12:24:38Z","citation":{"ama":"Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable Markov decision processes with ω-regular objectives. <i>Journal of Computer and System Sciences</i>. 2016;82(5):878-911. doi:<a href=\"https://doi.org/10.1016/j.jcss.2016.02.009\">10.1016/j.jcss.2016.02.009</a>","apa":"Chatterjee, K., Chmelik, M., &#38; Tracol, M. (2016). What is decidable about partially observable Markov decision processes with ω-regular objectives. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2016.02.009\">https://doi.org/10.1016/j.jcss.2016.02.009</a>","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2016. <a href=\"https://doi.org/10.1016/j.jcss.2016.02.009\">https://doi.org/10.1016/j.jcss.2016.02.009</a>.","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially observable Markov decision processes with ω-regular objectives,” <i>Journal of Computer and System Sciences</i>, vol. 82, no. 5. Elsevier, pp. 878–911, 2016.","mla":"Chatterjee, Krishnendu, et al. “What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives.” <i>Journal of Computer and System Sciences</i>, vol. 82, no. 5, Elsevier, 2016, pp. 878–911, doi:<a href=\"https://doi.org/10.1016/j.jcss.2016.02.009\">10.1016/j.jcss.2016.02.009</a>.","short":"K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.","ista":"Chatterjee K, Chmelik M, Tracol M. 2016. What is decidable about partially observable Markov decision processes with ω-regular objectives. Journal of Computer and System Sciences. 82(5), 878–911."},"year":"2016","volume":82,"title":"What is decidable about partially observable Markov decision processes with ω-regular objectives","intvolume":"        82","publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T11:52:15Z","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"},{"full_name":"Tracol, Mathieu","first_name":"Mathieu","last_name":"Tracol","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87"}],"issue":"5","_id":"1477","scopus_import":1,"publisher":"Elsevier","page":"878 - 911","quality_controlled":"1","ec_funded":1,"publist_id":"5718","oa":1,"date_published":"2016-08-01T00:00:00Z","type":"journal_article","related_material":{"record":[{"relation":"earlier_version","id":"2295","status":"public"},{"id":"5400","relation":"earlier_version","status":"public"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1309.2802"}],"month":"08","oa_version":"Preprint","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"publication":"Journal of Computer and System Sciences","language":[{"iso":"eng"}]},{"scopus_import":"1","_id":"1518","pmid":1,"issue":"2","author":[{"full_name":"Lohse, Konrad","last_name":"Lohse","first_name":"Konrad"},{"full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Martin, Simon","last_name":"Martin","first_name":"Simon"},{"orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","first_name":"Nicholas H","last_name":"Barton","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","department":[{"_id":"KrCh"},{"_id":"NiBa"}],"date_created":"2018-12-11T11:52:29Z","publication_status":"published","intvolume":"       202","title":"Efficient strategies for calculating blockwise likelihoods under the coalescent","pubrep_id":"561","quality_controlled":"1","ec_funded":1,"page":"775 - 786","file_date_updated":"2020-07-14T12:45:00Z","publisher":"Genetics Society of America","article_type":"original","citation":{"ista":"Lohse K, Chmelik M, Martin S, Barton NH. 2016. Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics. 202(2), 775–786.","short":"K. Lohse, M. Chmelik, S. Martin, N.H. Barton, Genetics 202 (2016) 775–786.","mla":"Lohse, Konrad, et al. “Efficient Strategies for Calculating Blockwise Likelihoods under the Coalescent.” <i>Genetics</i>, vol. 202, no. 2, Genetics Society of America, 2016, pp. 775–86, doi:<a href=\"https://doi.org/10.1534/genetics.115.183814\">10.1534/genetics.115.183814</a>.","chicago":"Lohse, Konrad, Martin Chmelik, Simon Martin, and Nicholas H Barton. “Efficient Strategies for Calculating Blockwise Likelihoods under the Coalescent.” <i>Genetics</i>. Genetics Society of America, 2016. <a href=\"https://doi.org/10.1534/genetics.115.183814\">https://doi.org/10.1534/genetics.115.183814</a>.","ieee":"K. Lohse, M. Chmelik, S. Martin, and N. H. Barton, “Efficient strategies for calculating blockwise likelihoods under the coalescent,” <i>Genetics</i>, vol. 202, no. 2. Genetics Society of America, pp. 775–786, 2016.","ama":"Lohse K, Chmelik M, Martin S, Barton NH. Efficient strategies for calculating blockwise likelihoods under the coalescent. <i>Genetics</i>. 2016;202(2):775-786. doi:<a href=\"https://doi.org/10.1534/genetics.115.183814\">10.1534/genetics.115.183814</a>","apa":"Lohse, K., Chmelik, M., Martin, S., &#38; Barton, N. H. (2016). Efficient strategies for calculating blockwise likelihoods under the coalescent. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1534/genetics.115.183814\">https://doi.org/10.1534/genetics.115.183814</a>"},"year":"2016","date_updated":"2025-05-28T11:42:48Z","external_id":{"pmid":["26715666"]},"day":"01","doi":"10.1534/genetics.115.183814","abstract":[{"lang":"eng","text":"The inference of demographic history from genome data is hindered by a lack of efficient computational approaches. In particular, it has proved difficult to exploit the information contained in the distribution of genealogies across the genome. We have previously shown that the generating function (GF) of genealogies can be used to analytically compute likelihoods of demographic models from configurations of mutations in short sequence blocks (Lohse et al. 2011). Although the GF has a simple, recursive form, the size of such likelihood calculations explodes quickly with the number of individuals and applications of this framework have so far been mainly limited to small samples (pairs and triplets) for which the GF can be written by hand. Here we investigate several strategies for exploiting the inherent symmetries of the coalescent. In particular, we show that the GF of genealogies can be decomposed into a set of equivalence classes that allows likelihood calculations from nontrivial samples. Using this strategy, we automated blockwise likelihood calculations for a general set of demographic scenarios in Mathematica. These histories may involve population size changes, continuous migration, discrete divergence, and admixture between multiple populations. To give a concrete example, we calculate the likelihood for a model of isolation with migration (IM), assuming two diploid samples without phase and outgroup information. We demonstrate the new inference scheme with an analysis of two individual butterfly genomes from the sister species Heliconius melpomene rosina and H. cydno."}],"acknowledgement":"We thank Lynsey Bunnefeld for discussions throughout the project and Joshua Schraiber and one anonymous reviewer\r\nfor constructive comments on an earlier version of this manuscript. This work was supported by funding from the\r\nUnited Kingdom Natural Environment Research Council (to K.L.) (NE/I020288/1) and a grant from the European\r\nResearch Council (250152) (to N.H.B.).","volume":202,"ddc":["570"],"has_accepted_license":"1","publication":"Genetics","project":[{"grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation","call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","month":"02","language":[{"iso":"eng"}],"type":"journal_article","date_published":"2016-02-01T00:00:00Z","oa":1,"publist_id":"5658","file":[{"content_type":"application/pdf","file_name":"IST-2016-561-v1+1_Lohse_et_al_Genetics_2015.pdf","date_updated":"2020-07-14T12:45:00Z","file_size":957466,"checksum":"41c9b5d72e7fe4624dd22dfe622337d5","date_created":"2018-12-12T10:16:51Z","creator":"system","file_id":"5241","access_level":"open_access","relation":"main_file"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"publist_id":"5642","oa":1,"type":"journal_article","date_published":"2016-05-01T00:00:00Z","main_file_link":[{"url":"http://arxiv.org/abs/1411.3880","open_access":"1"}],"status":"public","related_material":{"record":[{"status":"public","id":"1820","relation":"earlier_version"},{"relation":"earlier_version","id":"5425","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"oa_version":"Preprint","month":"05","publication":"Artificial Intelligence","language":[{"iso":"eng"}],"day":"01","doi":"10.1016/j.artint.2016.01.007","arxiv":1,"abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs) with a set of target states and an integer cost associated with every transition. The optimization objective we study asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest."}],"citation":{"ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability in POMDPs. <i>Artificial Intelligence</i>. 2016;234:26-48. doi:<a href=\"https://doi.org/10.1016/j.artint.2016.01.007\">10.1016/j.artint.2016.01.007</a>","apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2016). Optimal cost almost-sure reachability in POMDPs. <i>Artificial Intelligence</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.artint.2016.01.007\">https://doi.org/10.1016/j.artint.2016.01.007</a>","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure reachability in POMDPs,” <i>Artificial Intelligence</i>, vol. 234. Elsevier, pp. 26–48, 2016.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Optimal Cost Almost-Sure Reachability in POMDPs.” <i>Artificial Intelligence</i>. Elsevier, 2016. <a href=\"https://doi.org/10.1016/j.artint.2016.01.007\">https://doi.org/10.1016/j.artint.2016.01.007</a>.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Artificial Intelligence 234 (2016) 26–48.","mla":"Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.” <i>Artificial Intelligence</i>, vol. 234, Elsevier, 2016, pp. 26–48, doi:<a href=\"https://doi.org/10.1016/j.artint.2016.01.007\">10.1016/j.artint.2016.01.007</a>.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2016. Optimal cost almost-sure reachability in POMDPs. Artificial Intelligence. 234, 26–48."},"year":"2016","date_updated":"2023-02-23T12:25:49Z","external_id":{"arxiv":["1411.3880"]},"volume":234,"acknowledgement":"We thank Blai Bonet for helping us with RTDP-Bel. The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T11:52:33Z","article_processing_charge":"No","publication_status":"published","intvolume":"       234","title":"Optimal cost almost-sure reachability in POMDPs","scopus_import":1,"_id":"1529","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin"},{"full_name":"Gupta, Raghav","first_name":"Raghav","last_name":"Gupta"},{"first_name":"Ayush","last_name":"Kanodia","full_name":"Kanodia, Ayush"}],"publisher":"Elsevier","quality_controlled":"1","ec_funded":1,"page":"26 - 48"},{"type":"journal_article","date_published":"2016-10-04T00:00:00Z","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)"},"oa":1,"publist_id":"5948","related_material":{"record":[{"relation":"research_data","id":"9867","status":"public"},{"relation":"research_data","id":"9868","status":"public"}]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"creator":"system","file_id":"4668","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_name":"IST-2016-716-v1+1_journal.pone.0163867.PDF","date_updated":"2020-07-14T12:44:44Z","checksum":"6b33e394003dfe8b4ca6be1858aaa8e3","file_size":2077905,"date_created":"2018-12-12T10:08:08Z"}],"has_accepted_license":"1","publication":"PLoS One","article_number":"e0163867","month":"10","oa_version":"Published Version","language":[{"iso":"eng"}],"citation":{"ama":"Hilbe C, Hagel K, Milinski M. Asymmetric power boosts extortion in an economic experiment. <i>PLoS One</i>. 2016;11(10). doi:<a href=\"https://doi.org/10.1371/journal.pone.0163867\">10.1371/journal.pone.0163867</a>","apa":"Hilbe, C., Hagel, K., &#38; Milinski, M. (2016). Asymmetric power boosts extortion in an economic experiment. <i>PLoS One</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0163867\">https://doi.org/10.1371/journal.pone.0163867</a>","chicago":"Hilbe, Christian, Kristin Hagel, and Manfred Milinski. “Asymmetric Power Boosts Extortion in an Economic Experiment.” <i>PLoS One</i>. Public Library of Science, 2016. <a href=\"https://doi.org/10.1371/journal.pone.0163867\">https://doi.org/10.1371/journal.pone.0163867</a>.","ieee":"C. Hilbe, K. Hagel, and M. Milinski, “Asymmetric power boosts extortion in an economic experiment,” <i>PLoS One</i>, vol. 11, no. 10. Public Library of Science, 2016.","mla":"Hilbe, Christian, et al. “Asymmetric Power Boosts Extortion in an Economic Experiment.” <i>PLoS One</i>, vol. 11, no. 10, e0163867, Public Library of Science, 2016, doi:<a href=\"https://doi.org/10.1371/journal.pone.0163867\">10.1371/journal.pone.0163867</a>.","short":"C. Hilbe, K. Hagel, M. Milinski, PLoS One 11 (2016).","ista":"Hilbe C, Hagel K, Milinski M. 2016. Asymmetric power boosts extortion in an economic experiment. PLoS One. 11(10), e0163867."},"year":"2016","date_updated":"2023-02-23T14:11:27Z","abstract":[{"lang":"eng","text":"Direct reciprocity is a major mechanism for the evolution of cooperation. Several classical studies have suggested that humans should quickly learn to adopt reciprocal strategies to establish mutual cooperation in repeated interactions. On the other hand, the recently discovered theory of ZD strategies has found that subjects who use extortionate strategies are able to exploit and subdue cooperators. Although such extortioners have been predicted to succeed in any population of adaptive opponents, theoretical follow-up studies questioned whether extortion can evolve in reality. However, most of these studies presumed that individuals have similar strategic possibilities and comparable outside options, whereas asymmetries are ubiquitous in real world applications. Here we show with a model and an economic experiment that extortionate strategies readily emerge once subjects differ in their strategic power. Our experiment combines a repeated social dilemma with asymmetric partner choice. In our main treatment there is one randomly chosen group member who is unilaterally allowed to exchange one of the other group members after every ten rounds of the social dilemma. We find that this asymmetric replacement opportunity generally promotes cooperation, but often the resulting payoff distribution reflects the underlying power structure. Almost half of the subjects in a better strategic position turn into extortioners, who quickly proceed to exploit their peers. By adapting their cooperation probabilities consistent with ZD theory, extortioners force their co-players to cooperate without being similarly cooperative themselves. Comparison to non-extortionate players under the same conditions indicates a substantial net gain to extortion. Our results thus highlight how power asymmetries can endanger mutually beneficial interactions, and transform them into exploitative relationships. In particular, our results indicate that the extortionate strategies predicted from ZD theory could play a more prominent role in our daily interactions than previously thought."}],"day":"04","doi":"10.1371/journal.pone.0163867","ddc":["004","006"],"volume":11,"acknowledgement":"CH was funded by the Schrödinger program of the Austrian Science Fund (FWF) J3475. ","issue":"10","author":[{"first_name":"Christian","last_name":"Hilbe","orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Hagel","first_name":"Kristin","full_name":"Hagel, Kristin"},{"full_name":"Milinski, Manfred","last_name":"Milinski","first_name":"Manfred"}],"scopus_import":1,"_id":"1322","intvolume":"        11","title":"Asymmetric power boosts extortion in an economic experiment","pubrep_id":"716","date_created":"2018-12-11T11:51:22Z","department":[{"_id":"KrCh"}],"publication_status":"published","file_date_updated":"2020-07-14T12:44:44Z","quality_controlled":"1","publisher":"Public Library of Science"},{"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","volume":"2016-January","main_file_link":[{"url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/12999"}],"abstract":[{"text":"DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. Copyright ","lang":"eng"}],"publist_id":"5946","day":"01","date_published":"2016-01-01T00:00:00Z","type":"conference","date_updated":"2021-01-12T06:49:53Z","year":"2016","citation":{"chicago":"Chatterjee, Krishnendu, and Martin Chmelik. “Indefinite-Horizon Reachability in Goal-DEC-POMDPs.” In <i>Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling</i>, 2016–January:88–96. AAAI Press, 2016.","ieee":"K. Chatterjee and M. Chmelik, “Indefinite-horizon reachability in Goal-DEC-POMDPs,” in <i>Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling</i>, London, United Kingdom, 2016, vol. 2016–January, pp. 88–96.","ama":"Chatterjee K, Chmelik M. Indefinite-horizon reachability in Goal-DEC-POMDPs. In: <i>Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling</i>. Vol 2016-January. AAAI Press; 2016:88-96.","apa":"Chatterjee, K., &#38; Chmelik, M. (2016). Indefinite-horizon reachability in Goal-DEC-POMDPs. In <i>Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling</i> (Vol. 2016–January, pp. 88–96). London, United Kingdom: AAAI Press.","ista":"Chatterjee K, Chmelik M. 2016. Indefinite-horizon reachability in Goal-DEC-POMDPs. Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling. ICAPS: International Conference on Automated Planning and Scheduling vol. 2016–January, 88–96.","mla":"Chatterjee, Krishnendu, and Martin Chmelik. “Indefinite-Horizon Reachability in Goal-DEC-POMDPs.” <i>Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling</i>, vol. 2016–January, AAAI Press, 2016, pp. 88–96.","short":"K. Chatterjee, M. Chmelik, in:, Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, 2016, pp. 88–96."},"conference":{"location":"London, United Kingdom","end_date":"2016-06-17","name":"ICAPS: International Conference on Automated Planning and Scheduling","start_date":"2016-06-12"},"publisher":"AAAI Press","language":[{"iso":"eng"}],"page":"88 - 96","ec_funded":1,"quality_controlled":"1","title":"Indefinite-horizon reachability in Goal-DEC-POMDPs","month":"01","publication_status":"published","oa_version":"None","department":[{"_id":"KrCh"}],"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"date_created":"2018-12-11T11:51:22Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"publication":"Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling","_id":"1324","scopus_import":1},{"abstract":[{"text":"We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.","lang":"eng"}],"day":"01","doi":"10.4230/LIPIcs.CONCUR.2016.10","citation":{"ama":"Brázdil T, Forejt V, Kučera A, Novotný P. Stability in graphs and games. In: Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.10\">10.4230/LIPIcs.CONCUR.2016.10</a>","apa":"Brázdil, T., Forejt, V., Kučera, A., &#38; Novotný, P. (2016). Stability in graphs and games (Vol. 59). Presented at the CONCUR: Concurrency Theory, Quebec City, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.10\">https://doi.org/10.4230/LIPIcs.CONCUR.2016.10</a>","chicago":"Brázdil, Tomáš, Vojtěch Forejt, Antonín Kučera, and Petr Novotný. “Stability in Graphs and Games,” Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.10\">https://doi.org/10.4230/LIPIcs.CONCUR.2016.10</a>.","ieee":"T. Brázdil, V. Forejt, A. Kučera, and P. Novotný, “Stability in graphs and games,” presented at the CONCUR: Concurrency Theory, Quebec City, Canada, 2016, vol. 59.","short":"T. Brázdil, V. Forejt, A. Kučera, P. Novotný, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","mla":"Brázdil, Tomáš, et al. <i>Stability in Graphs and Games</i>. Vol. 59, 10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.10\">10.4230/LIPIcs.CONCUR.2016.10</a>.","ista":"Brázdil T, Forejt V, Kučera A, Novotný P. 2016. Stability in graphs and games. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 10."},"year":"2016","date_updated":"2021-01-12T06:49:53Z","ddc":["004"],"volume":59,"acknowledgement":"The work has been supported by the Czech Science Foundation, grant No. 15-17564S, by EPSRC grant\r\nEP/M023656/1, and by the People Programme (Marie Curie Actions) of the European Union’s Seventh\r\nFramework Programme (FP7/2007-2013) under REA grant agreement no [291734]","intvolume":"        59","title":"Stability in graphs and games","pubrep_id":"665","alternative_title":["LIPIcs"],"date_created":"2018-12-11T11:51:23Z","department":[{"_id":"KrCh"}],"publication_status":"published","author":[{"last_name":"Brázdil","first_name":"Tomáš","full_name":"Brázdil, Tomáš"},{"full_name":"Forejt, Vojtěch","first_name":"Vojtěch","last_name":"Forejt"},{"last_name":"Kučera","first_name":"Antonín","full_name":"Kučera, Antonín"},{"id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr","last_name":"Novotny","full_name":"Novotny, Petr"}],"scopus_import":1,"_id":"1325","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:44:44Z","ec_funded":1,"quality_controlled":"1","oa":1,"publist_id":"5944","type":"conference","date_published":"2016-08-01T00:00:00Z","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)"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"creator":"system","file_id":"5229","access_level":"open_access","relation":"main_file","file_name":"IST-2016-665-v1+1_Forejt_et_al__Stability_in_graphs_and_games.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:44:44Z","checksum":"3c2dc6ab0358f8aa8f7aa7d6c1293159","file_size":553648,"date_created":"2018-12-12T10:16:40Z"}],"article_number":"10","month":"08","project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"oa_version":"Published Version","has_accepted_license":"1","conference":{"end_date":"2016-08-26","location":"Quebec City, Canada","name":"CONCUR: Concurrency Theory","start_date":"2016-08-23"},"language":[{"iso":"eng"}]},{"intvolume":"      9938","alternative_title":["LNCS"],"title":"Optimizing the expected mean payoff in Energy Markov Decision Processes","date_created":"2018-12-11T11:51:23Z","department":[{"_id":"KrCh"}],"publication_status":"published","author":[{"full_name":"Brázdil, Tomáš","last_name":"Brázdil","first_name":"Tomáš"},{"full_name":"Kučera, Antonín","first_name":"Antonín","last_name":"Kučera"},{"full_name":"Novotny, Petr","last_name":"Novotny","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"_id":"1326","publisher":"Springer","ec_funded":1,"quality_controlled":"1","page":"32 - 49","abstract":[{"text":"Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff. ","lang":"eng"}],"day":"22","doi":"10.1007/978-3-319-46520-3_3","year":"2016","citation":{"ama":"Brázdil T, Kučera A, Novotný P. Optimizing the expected mean payoff in Energy Markov Decision Processes. In: Vol 9938. Springer; 2016:32-49. doi:<a href=\"https://doi.org/10.1007/978-3-319-46520-3_3\">10.1007/978-3-319-46520-3_3</a>","apa":"Brázdil, T., Kučera, A., &#38; Novotný, P. (2016). Optimizing the expected mean payoff in Energy Markov Decision Processes (Vol. 9938, pp. 32–49). Presented at the ATVA: Automated Technology for Verification and Analysis, Chiba, Japan: Springer. <a href=\"https://doi.org/10.1007/978-3-319-46520-3_3\">https://doi.org/10.1007/978-3-319-46520-3_3</a>","chicago":"Brázdil, Tomáš, Antonín Kučera, and Petr Novotný. “Optimizing the Expected Mean Payoff in Energy Markov Decision Processes,” 9938:32–49. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-46520-3_3\">https://doi.org/10.1007/978-3-319-46520-3_3</a>.","ieee":"T. Brázdil, A. Kučera, and P. Novotný, “Optimizing the expected mean payoff in Energy Markov Decision Processes,” presented at the ATVA: Automated Technology for Verification and Analysis, Chiba, Japan, 2016, vol. 9938, pp. 32–49.","short":"T. Brázdil, A. Kučera, P. Novotný, in:, Springer, 2016, pp. 32–49.","mla":"Brázdil, Tomáš, et al. <i>Optimizing the Expected Mean Payoff in Energy Markov Decision Processes</i>. Vol. 9938, Springer, 2016, pp. 32–49, doi:<a href=\"https://doi.org/10.1007/978-3-319-46520-3_3\">10.1007/978-3-319-46520-3_3</a>.","ista":"Brázdil T, Kučera A, Novotný P. 2016. Optimizing the expected mean payoff in Energy Markov Decision Processes. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 9938, 32–49."},"date_updated":"2021-01-12T06:49:53Z","acknowledgement":"The research was funded by the Czech Science Foundation Grant No. P202/12/G061 and by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].","volume":9938,"month":"09","project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"oa_version":"Preprint","conference":{"name":"ATVA: Automated Technology for Verification and Analysis","start_date":"2016-10-17","location":"Chiba, Japan","end_date":"2016-10-20"},"language":[{"iso":"eng"}],"publist_id":"5943","oa":1,"type":"conference","date_published":"2016-09-22T00:00:00Z","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1607.00678"}]},{"title":"Stochastic shortest path with energy constraints in POMDPs","month":"01","date_created":"2018-12-11T11:51:23Z","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"}],"oa_version":"Preprint","publication_status":"published","author":[{"last_name":"Brázdil","first_name":"Tomáš","full_name":"Brázdil, Tomáš"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin"},{"full_name":"Gupta, Anchit","last_name":"Gupta","first_name":"Anchit"},{"last_name":"Novotny","first_name":"Petr","full_name":"Novotny, Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"publication":"Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems","_id":"1327","conference":{"name":"AAMAS: Autonomous Agents & Multiagent Systems","start_date":"2016-05-09","location":"Singapore","end_date":"2016-05-13"},"publisher":"ACM","language":[{"iso":"eng"}],"quality_controlled":"1","ec_funded":1,"page":"1465 - 1466","oa":1,"publist_id":"5942","abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels. "}],"day":"01","type":"conference","date_published":"2016-01-01T00:00:00Z","year":"2016","citation":{"ieee":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, and P. Novotný, “Stochastic shortest path with energy constraints in POMDPs,” in <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>, Singapore, 2016, pp. 1465–1466.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Anchit Gupta, and Petr Novotný. “Stochastic Shortest Path with Energy Constraints in POMDPs.” In <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>, 1465–66. ACM, 2016.","apa":"Brázdil, T., Chatterjee, K., Chmelik, M., Gupta, A., &#38; Novotný, P. (2016). Stochastic shortest path with energy constraints in POMDPs. In <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i> (pp. 1465–1466). Singapore: ACM.","ama":"Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. Stochastic shortest path with energy constraints in POMDPs. In: <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>. ACM; 2016:1465-1466.","ista":"Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. 2016. Stochastic shortest path with energy constraints in POMDPs. Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. AAMAS: Autonomous Agents &#38; Multiagent Systems, 1465–1466.","short":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.","mla":"Brázdil, Tomáš, et al. “Stochastic Shortest Path with Energy Constraints in POMDPs.” <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>, ACM, 2016, pp. 1465–66."},"date_updated":"2021-01-12T06:49:54Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.07565"}]},{"publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T11:51:25Z","pubrep_id":"661","title":"Humans choose representatives who enforce cooperation in social dilemmas through extortion","intvolume":"         7","_id":"1333","scopus_import":1,"author":[{"full_name":"Milinski, Manfred","first_name":"Manfred","last_name":"Milinski"},{"last_name":"Hilbe","first_name":"Christian","full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Semmann, Dirk","first_name":"Dirk","last_name":"Semmann"},{"first_name":"Ralf","last_name":"Sommerfeld","full_name":"Sommerfeld, Ralf"},{"full_name":"Marotzke, Jochem","first_name":"Jochem","last_name":"Marotzke"}],"publisher":"Nature Publishing Group","quality_controlled":"1","file_date_updated":"2020-07-14T12:44:44Z","doi":"10.1038/ncomms10915","day":"07","abstract":[{"lang":"eng","text":"Social dilemmas force players to balance between personal and collective gain. In many dilemmas, such as elected governments negotiating climate-change mitigation measures, the decisions are made not by individual players but by their representatives. However, the behaviour of representatives in social dilemmas has not been investigated experimentally. Here inspired by the negotiations for greenhouse-gas emissions reductions, we experimentally study a collective-risk social dilemma that involves representatives deciding on behalf of their fellow group members. Representatives can be re-elected or voted out after each consecutive collective-risk game. Selfish players are preferentially elected and are hence found most frequently in the &quot;representatives&quot; treatment. Across all treatments, we identify the selfish players as extortioners. As predicted by our mathematical model, their steadfast strategies enforce cooperation from fair players who finally compensate almost completely the deficit caused by the extortionate co-players. Everybody gains, but the extortionate representatives and their groups gain the most."}],"date_updated":"2021-01-12T06:49:57Z","year":"2016","citation":{"ieee":"M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, and J. Marotzke, “Humans choose representatives who enforce cooperation in social dilemmas through extortion,” <i>Nature Communications</i>, vol. 7. Nature Publishing Group, 2016.","chicago":"Milinski, Manfred, Christian Hilbe, Dirk Semmann, Ralf Sommerfeld, and Jochem Marotzke. “Humans Choose Representatives Who Enforce Cooperation in Social Dilemmas through Extortion.” <i>Nature Communications</i>. Nature Publishing Group, 2016. <a href=\"https://doi.org/10.1038/ncomms10915\">https://doi.org/10.1038/ncomms10915</a>.","ama":"Milinski M, Hilbe C, Semmann D, Sommerfeld R, Marotzke J. Humans choose representatives who enforce cooperation in social dilemmas through extortion. <i>Nature Communications</i>. 2016;7. doi:<a href=\"https://doi.org/10.1038/ncomms10915\">10.1038/ncomms10915</a>","apa":"Milinski, M., Hilbe, C., Semmann, D., Sommerfeld, R., &#38; Marotzke, J. (2016). Humans choose representatives who enforce cooperation in social dilemmas through extortion. <i>Nature Communications</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/ncomms10915\">https://doi.org/10.1038/ncomms10915</a>","ista":"Milinski M, Hilbe C, Semmann D, Sommerfeld R, Marotzke J. 2016. Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature Communications. 7, 10915.","mla":"Milinski, Manfred, et al. “Humans Choose Representatives Who Enforce Cooperation in Social Dilemmas through Extortion.” <i>Nature Communications</i>, vol. 7, 10915, Nature Publishing Group, 2016, doi:<a href=\"https://doi.org/10.1038/ncomms10915\">10.1038/ncomms10915</a>.","short":"M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, J. Marotzke, Nature Communications 7 (2016)."},"acknowledgement":"We thank the students for participation; H.-J. Krambeck for writing the software for the game; H. Arndt, T. Bakker, L. Becks, H. Brendelberger, S. Dobler and T. Reusch for support; and the Max Planck Society for the Advancement of Science for funding.","volume":7,"ddc":["519","530","599"],"oa_version":"Published Version","month":"03","article_number":"10915","publication":"Nature Communications","has_accepted_license":"1","language":[{"iso":"eng"}],"oa":1,"publist_id":"5935","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)"},"date_published":"2016-03-07T00:00:00Z","type":"journal_article","file":[{"checksum":"9ea0d7ce59a555a1cb8353d5559407cb","file_size":1432577,"date_created":"2018-12-12T10:10:44Z","file_name":"IST-2016-661-v1+1_ncomms10915.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:44:44Z","access_level":"open_access","relation":"main_file","creator":"system","file_id":"4834"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"}]