[{"article_number":"25676","title":"Comparing reactive and memory-one strategies of direct reciprocity","publist_id":"5784","author":[{"last_name":"Baek","full_name":"Baek, Seung","first_name":"Seung"},{"last_name":"Jeong","full_name":"Jeong, Hyeongchai","first_name":"Hyeongchai"},{"id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian","orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian","last_name":"Hilbe"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Baek, Seung, Hyeongchai Jeong, Christian Hilbe, and Martin Nowak. “Comparing Reactive and Memory-One Strategies of Direct Reciprocity.” Scientific Reports. Nature Publishing Group, 2016. https://doi.org/10.1038/srep25676.","ista":"Baek S, Jeong H, Hilbe C, Nowak M. 2016. Comparing reactive and memory-one strategies of direct reciprocity. Scientific Reports. 6, 25676.","mla":"Baek, Seung, et al. “Comparing Reactive and Memory-One Strategies of Direct Reciprocity.” Scientific Reports, vol. 6, 25676, Nature Publishing Group, 2016, doi:10.1038/srep25676.","short":"S. Baek, H. Jeong, C. Hilbe, M. Nowak, Scientific Reports 6 (2016).","ieee":"S. Baek, H. Jeong, C. Hilbe, and M. Nowak, “Comparing reactive and memory-one strategies of direct reciprocity,” Scientific Reports, vol. 6. Nature Publishing Group, 2016.","apa":"Baek, S., Jeong, H., Hilbe, C., & Nowak, M. (2016). Comparing reactive and memory-one strategies of direct reciprocity. Scientific Reports. Nature Publishing Group. https://doi.org/10.1038/srep25676","ama":"Baek S, Jeong H, Hilbe C, Nowak M. Comparing reactive and memory-one strategies of direct reciprocity. Scientific Reports. 2016;6. doi:10.1038/srep25676"},"publisher":"Nature Publishing Group","quality_controlled":"1","oa":1,"acknowledgement":"C.H. acknowledges generous funding from the Schrödinger scholarship of the Austrian Science Fund (FWF), J3475.","doi":"10.1038/srep25676","date_published":"2016-05-10T00:00:00Z","date_created":"2018-12-11T11:51:56Z","day":"10","publication":"Scientific Reports","has_accepted_license":"1","year":"2016","status":"public","pubrep_id":"590","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"1423","file_date_updated":"2020-07-14T12:44:53Z","department":[{"_id":"KrCh"}],"ddc":["000"],"date_updated":"2021-01-12T06:50:38Z","month":"05","intvolume":" 6","scopus_import":1,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Direct reciprocity is a mechanism for the evolution of cooperation based on repeated interactions. When individuals meet repeatedly, they can use conditional strategies to enforce cooperative outcomes that would not be feasible in one-shot social dilemmas. Direct reciprocity requires that individuals keep track of their past interactions and find the right response. However, there are natural bounds on strategic complexity: Humans find it difficult to remember past interactions accurately, especially over long timespans. Given these limitations, it is natural to ask how complex strategies need to be for cooperation to evolve. Here, we study stochastic evolutionary game dynamics in finite populations to systematically compare the evolutionary performance of reactive strategies, which only respond to the co-player's previous move, and memory-one strategies, which take into account the own and the co-player's previous move. In both cases, we compare deterministic strategy and stochastic strategy spaces. For reactive strategies and small costs, we find that stochasticity benefits cooperation, because it allows for generous-tit-for-tat. For memory one strategies and small costs, we find that stochasticity does not increase the propensity for cooperation, because the deterministic rule of win-stay, lose-shift works best. For memory one strategies and large costs, however, stochasticity can augment cooperation."}],"volume":6,"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"5327","checksum":"ee17c482370d2e1b3add393710d3c696","creator":"system","file_size":1349915,"date_updated":"2020-07-14T12:44:53Z","file_name":"IST-2016-590-v1+1_srep25676.pdf","date_created":"2018-12-12T10:18:08Z"}],"language":[{"iso":"eng"}],"publication_status":"published"},{"status":"public","pubrep_id":"561","type":"journal_article","article_type":"original","_id":"1518","department":[{"_id":"KrCh"},{"_id":"NiBa"}],"file_date_updated":"2020-07-14T12:45:00Z","ddc":["570"],"date_updated":"2022-05-24T09:16:22Z","month":"02","intvolume":" 202","scopus_import":"1","oa_version":"Preprint","pmid":1,"abstract":[{"text":"The inference of demographic history from genome data is hindered by a lack of efficient computational approaches. In particular, it has proved difficult to exploit the information contained in the distribution of genealogies across the genome. We have previously shown that the generating function (GF) of genealogies can be used to analytically compute likelihoods of demographic models from configurations of mutations in short sequence blocks (Lohse et al. 2011). Although the GF has a simple, recursive form, the size of such likelihood calculations explodes quickly with the number of individuals and applications of this framework have so far been mainly limited to small samples (pairs and triplets) for which the GF can be written by hand. Here we investigate several strategies for exploiting the inherent symmetries of the coalescent. In particular, we show that the GF of genealogies can be decomposed into a set of equivalence classes that allows likelihood calculations from nontrivial samples. Using this strategy, we automated blockwise likelihood calculations for a general set of demographic scenarios in Mathematica. These histories may involve population size changes, continuous migration, discrete divergence, and admixture between multiple populations. To give a concrete example, we calculate the likelihood for a model of isolation with migration (IM), assuming two diploid samples without phase and outgroup information. We demonstrate the new inference scheme with an analysis of two individual butterfly genomes from the sister species Heliconius melpomene rosina and H. cydno.","lang":"eng"}],"volume":202,"issue":"2","ec_funded":1,"file":[{"creator":"system","file_size":957466,"date_updated":"2020-07-14T12:45:00Z","file_name":"IST-2016-561-v1+1_Lohse_et_al_Genetics_2015.pdf","date_created":"2018-12-12T10:16:51Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"41c9b5d72e7fe4624dd22dfe622337d5","file_id":"5241"}],"language":[{"iso":"eng"}],"publication_status":"published","project":[{"grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation","call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425"}],"title":"Efficient strategies for calculating blockwise likelihoods under the coalescent","publist_id":"5658","author":[{"first_name":"Konrad","full_name":"Lohse, Konrad","last_name":"Lohse"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Chmelik, Martin","last_name":"Chmelik"},{"last_name":"Martin","full_name":"Martin, Simon","first_name":"Simon"},{"last_name":"Barton","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"pmid":["26715666"]},"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Lohse, Konrad, Martin Chmelik, Simon Martin, and Nicholas H Barton. “Efficient Strategies for Calculating Blockwise Likelihoods under the Coalescent.” Genetics. Genetics Society of America, 2016. https://doi.org/10.1534/genetics.115.183814.","ista":"Lohse K, Chmelik M, Martin S, Barton NH. 2016. Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics. 202(2), 775–786.","mla":"Lohse, Konrad, et al. “Efficient Strategies for Calculating Blockwise Likelihoods under the Coalescent.” Genetics, vol. 202, no. 2, Genetics Society of America, 2016, pp. 775–86, doi:10.1534/genetics.115.183814.","ama":"Lohse K, Chmelik M, Martin S, Barton NH. Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics. 2016;202(2):775-786. doi:10.1534/genetics.115.183814","apa":"Lohse, K., Chmelik, M., Martin, S., & Barton, N. H. (2016). Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics. Genetics Society of America. https://doi.org/10.1534/genetics.115.183814","ieee":"K. Lohse, M. Chmelik, S. Martin, and N. H. Barton, “Efficient strategies for calculating blockwise likelihoods under the coalescent,” Genetics, vol. 202, no. 2. Genetics Society of America, pp. 775–786, 2016.","short":"K. Lohse, M. Chmelik, S. Martin, N.H. Barton, Genetics 202 (2016) 775–786."},"publisher":"Genetics Society of America","quality_controlled":"1","oa":1,"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.).","doi":"10.1534/genetics.115.183814","date_published":"2016-02-01T00:00:00Z","date_created":"2018-12-11T11:52:29Z","page":"775 - 786","day":"01","publication":"Genetics","has_accepted_license":"1","year":"2016"},{"date_updated":"2021-01-12T08:00:54Z","ddc":["004"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:35Z","_id":"478","conference":{"start_date":"2016-08-29","end_date":"2016-09-02","location":"The Hague, Netherlands","name":"ECAI: European Conference on Artificial Intelligence"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"type":"conference","pubrep_id":"950","status":"public","publication_status":"published","language":[{"iso":"eng"}],"file":[{"file_name":"IST-2018-950-v1+1_2016_Chatterjee_The_complexity.pdf","date_created":"2018-12-12T10:07:59Z","creator":"system","file_size":2116225,"date_updated":"2020-07-14T12:46:35Z","file_id":"4658","checksum":"848043c812ace05e459579c923f3d3cf","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"license":"https://creativecommons.org/licenses/by-nc/4.0/","volume":285,"abstract":[{"text":"Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic.","lang":"eng"}],"oa_version":"Published Version","scopus_import":1,"alternative_title":["Frontiers in Artificial Intelligence and Applications"],"intvolume":" 285","month":"01","citation":{"mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Deciding Legality of a Single Step of Magic: The Gathering. Vol. 285, IOS Press, 2016, pp. 1432–39, doi:10.3233/978-1-61499-672-9-1432.","short":"K. Chatterjee, R. Ibsen-Jensen, in:, IOS Press, 2016, pp. 1432–1439.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The complexity of deciding legality of a single step of magic: The gathering,” presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands, 2016, vol. 285, pp. 1432–1439.","ama":"Chatterjee K, Ibsen-Jensen R. The complexity of deciding legality of a single step of magic: The gathering. In: Vol 285. IOS Press; 2016:1432-1439. doi:10.3233/978-1-61499-672-9-1432","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2016). The complexity of deciding legality of a single step of magic: The gathering (Vol. 285, pp. 1432–1439). Presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands: IOS Press. https://doi.org/10.3233/978-1-61499-672-9-1432","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Deciding Legality of a Single Step of Magic: The Gathering,” 285:1432–39. IOS Press, 2016. https://doi.org/10.3233/978-1-61499-672-9-1432.","ista":"Chatterjee K, Ibsen-Jensen R. 2016. The complexity of deciding legality of a single step of magic: The gathering. ECAI: European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, vol. 285, 1432–1439."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"}],"publist_id":"7342","title":"The complexity of deciding legality of a single step of magic: The gathering","year":"2016","has_accepted_license":"1","day":"01","page":"1432 - 1439","date_created":"2018-12-11T11:46:41Z","date_published":"2016-01-01T00:00:00Z","doi":"10.3233/978-1-61499-672-9-1432","oa":1,"quality_controlled":"1","publisher":"IOS Press"},{"department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T08:00:56Z","type":"conference","conference":{"end_date":"2016-07-08","location":"New York, NY, USA","start_date":"2016-07-05","name":"LICS: Logic in Computer Science"},"status":"public","_id":"480","volume":"05-08-July-2016","ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"alternative_title":["Proceedings Symposium on Logic in Computer Science"],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.06376"}],"month":"07","abstract":[{"lang":"eng","text":"Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements."}],"oa_version":"Preprint","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Doyen","full_name":"Doyen, Laurent","first_name":"Laurent"}],"publist_id":"7340","title":"Perfect-information stochastic games with generalized mean-payoff objectives","citation":{"mla":"Chatterjee, Krishnendu, and Laurent Doyen. Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives. Vol. 05-08-July-2016, IEEE, 2016, pp. 247–56, doi:10.1145/2933575.2934513.","apa":"Chatterjee, K., & Doyen, L. (2016). Perfect-information stochastic games with generalized mean-payoff objectives (Vol. 05-08-July-2016, pp. 247–256). Presented at the LICS: Logic in Computer Science, New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2934513","ama":"Chatterjee K, Doyen L. Perfect-information stochastic games with generalized mean-payoff objectives. In: Vol 05-08-July-2016. IEEE; 2016:247-256. doi:10.1145/2933575.2934513","short":"K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256.","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. https://doi.org/10.1145/2933575.2934513.","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."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_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"},{"name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425"}],"page":"247 - 256","date_published":"2016-07-05T00:00:00Z","doi":"10.1145/2933575.2934513","date_created":"2018-12-11T11:46:42Z","year":"2016","day":"05","publisher":"IEEE","quality_controlled":"1","oa":1},{"title":"What is decidable about partially observable Markov decision processes with ω-regular objectives","external_id":{"arxiv":["1309.2802"]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik"},{"full_name":"Tracol, Mathieu","last_name":"Tracol","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","first_name":"Mathieu"}],"publist_id":"5718","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives.” Journal of Computer and System Sciences. Elsevier, 2016. https://doi.org/10.1016/j.jcss.2016.02.009.","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.","mla":"Chatterjee, Krishnendu, et al. “What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives.” Journal of Computer and System Sciences, vol. 82, no. 5, Elsevier, 2016, pp. 878–911, doi:10.1016/j.jcss.2016.02.009.","short":"K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially observable Markov decision processes with ω-regular objectives,” Journal of Computer and System Sciences, vol. 82, no. 5. Elsevier, pp. 878–911, 2016.","ama":"Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable Markov decision processes with ω-regular objectives. Journal of Computer and System Sciences. 2016;82(5):878-911. doi:10.1016/j.jcss.2016.02.009","apa":"Chatterjee, K., Chmelik, M., & Tracol, M. (2016). What is decidable about partially observable Markov decision processes with ω-regular objectives. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2016.02.009"},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"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"}],"date_created":"2018-12-11T11:52:15Z","doi":"10.1016/j.jcss.2016.02.009","date_published":"2016-08-01T00:00:00Z","page":"878 - 911","publication":"Journal of Computer and System Sciences","day":"01","year":"2016","oa":1,"quality_controlled":"1","publisher":"Elsevier","department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:24:38Z","status":"public","type":"journal_article","_id":"1477","ec_funded":1,"volume":82,"issue":"5","related_material":{"record":[{"status":"public","id":"2295","relation":"earlier_version"},{"relation":"earlier_version","status":"public","id":"5400"}]},"language":[{"iso":"eng"}],"publication_status":"published","intvolume":" 82","month":"08","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1309.2802"}],"scopus_import":1,"oa_version":"Preprint","abstract":[{"lang":"eng","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."}]}]