[{"date_published":"2017-07-13T00:00:00Z","page":"201 - 221","citation":{"short":"P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, T. Meggendorfer, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 201–221.","mla":"Ashok, Pranav, et al. Value Iteration for Long Run Average Reward in Markov Decision Processes. Edited by Rupak Majumdar and Viktor Kunčak, vol. 10426, Springer, 2017, pp. 201–21, doi:10.1007/978-3-319-63387-9_10.","chicago":"Ashok, Pranav, Krishnendu Chatterjee, Przemyslaw Daca, Jan Kretinsky, and Tobias Meggendorfer. “Value Iteration for Long Run Average Reward in Markov Decision Processes.” edited by Rupak Majumdar and Viktor Kunčak, 10426:201–21. Springer, 2017. https://doi.org/10.1007/978-3-319-63387-9_10.","ama":"Ashok P, Chatterjee K, Daca P, Kretinsky J, Meggendorfer T. Value iteration for long run average reward in markov decision processes. In: Majumdar R, Kunčak V, eds. Vol 10426. Springer; 2017:201-221. doi:10.1007/978-3-319-63387-9_10","ieee":"P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, and T. Meggendorfer, “Value iteration for long run average reward in markov decision processes,” presented at the CAV: Computer Aided Verification, Heidelberg, Germany, 2017, vol. 10426, pp. 201–221.","apa":"Ashok, P., Chatterjee, K., Daca, P., Kretinsky, J., & Meggendorfer, T. (2017). Value iteration for long run average reward in markov decision processes. In R. Majumdar & V. Kunčak (Eds.) (Vol. 10426, pp. 201–221). Presented at the CAV: Computer Aided Verification, Heidelberg, Germany: Springer. https://doi.org/10.1007/978-3-319-63387-9_10","ista":"Ashok P, Chatterjee K, Daca P, Kretinsky J, Meggendorfer T. 2017. Value iteration for long run average reward in markov decision processes. CAV: Computer Aided Verification, LNCS, vol. 10426, 201–221."},"day":"13","scopus_import":1,"oa_version":"Submitted Version","status":"public","title":"Value iteration for long run average reward in markov decision processes","intvolume":" 10426","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"645","abstract":[{"text":"Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Long-run average rewards provide a mathematically elegant formalism for expressing long term performance. Value iteration (VI) is one of the simplest and most efficient algorithmic approaches to MDPs with other properties, such as reachability objectives. Unfortunately, a naive extension of VI does not work for MDPs with long-run average rewards, as there is no known stopping criterion. In this work our contributions are threefold. (1) We refute a conjecture related to stopping criteria for MDPs with long-run average rewards. (2) We present two practical algorithms for MDPs with long-run average rewards based on VI. First, we show that a combination of applying VI locally for each maximal end-component (MEC) and VI for reachability objectives can provide approximation guarantees. Second, extending the above approach with a simulation-guided on-demand variant of VI, we present an anytime algorithm that is able to deal with very large models. (3) Finally, we present experimental results showing that our methods significantly outperform the standard approaches on several benchmarks.","lang":"eng"}],"alternative_title":["LNCS"],"type":"conference","language":[{"iso":"eng"}],"conference":{"name":"CAV: Computer Aided Verification","location":"Heidelberg, Germany","start_date":"2017-07-24","end_date":"2017-07-28"},"doi":"10.1007/978-3-319-63387-9_10","quality_controlled":"1","project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1705.02326"}],"oa":1,"month":"07","publication_identifier":{"isbn":["978-331963386-2"]},"date_updated":"2021-01-12T08:07:32Z","date_created":"2018-12-11T11:47:41Z","volume":10426,"author":[{"last_name":"Ashok","first_name":"Pranav","full_name":"Ashok, Pranav"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Daca, Przemyslaw","first_name":"Przemyslaw","last_name":"Daca","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kretinsky, Jan","first_name":"Jan","last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881"},{"first_name":"Tobias","last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias"}],"publication_status":"published","publisher":"Springer","editor":[{"full_name":"Majumdar, Rupak","last_name":"Majumdar","first_name":"Rupak"},{"full_name":"Kunčak, Viktor","first_name":"Viktor","last_name":"Kunčak"}],"department":[{"_id":"KrCh"}],"year":"2017","publist_id":"7135","ec_funded":1},{"title":"Improved set-based symbolic algorithms for parity games","status":"public","ddc":["004"],"intvolume":" 82","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6519","oa_version":"Published Version","file":[{"file_id":"6520","relation":"main_file","checksum":"7c2c9d09970af79026d7e37d9b632ef8","date_created":"2019-06-04T12:56:52Z","date_updated":"2020-07-14T12:47:33Z","access_level":"open_access","file_name":"2017_LIPIcs-Chatterjee.pdf","creator":"kschuh","file_size":710185,"content_type":"application/pdf"}],"type":"conference","abstract":[{"lang":"eng","text":"Graph games with omega-regular winning conditions provide a mathematical framework to analyze a wide range of problems in the analysis of reactive systems and programs (such as the synthesis of reactive systems, program repair, and the verification of branching time properties). Parity conditions are canonical forms to specify omega-regular winning conditions. Graph games with parity conditions are equivalent to mu-calculus model checking, and thus a very important algorithmic problem. Symbolic algorithms are of great significance because they provide scalable algorithms for the analysis of large finite-state systems, as well as algorithms for the analysis of infinite-state systems with finite quotient. A set-based symbolic algorithm uses the basic set operations and the one-step predecessor operators. We consider graph games with n vertices and parity conditions with c priorities (equivalently, a mu-calculus formula with c alternations of least and greatest fixed points). While many explicit algorithms exist for graph games with parity conditions, for set-based symbolic algorithms there are only two algorithms (notice that we use space to refer to the number of sets stored by a symbolic algorithm): (a) the basic algorithm that requires O(n^c) symbolic operations and linear space; and (b) an improved algorithm that requires O(n^{c/2+1}) symbolic operations but also O(n^{c/2+1}) space (i.e., exponential space). In this work we present two set-based symbolic algorithms for parity games: (a) our first algorithm requires O(n^{c/2+1}) symbolic operations and only requires linear space; and (b) developing on our first algorithm, we present an algorithm that requires O(n^{c/3+1}) symbolic operations and only linear space. We also present the first linear space set-based symbolic algorithm for parity games that requires at most a sub-exponential number of symbolic operations. "}],"citation":{"apa":"Chatterjee, K., Dvorák, W., Henzinger, M. H., & Loitzenbauer, V. (2017). Improved set-based symbolic algorithms for parity games (Vol. 82). Presented at the CSL: Conference on Computer Science Logic, Stockholm, Sweden: Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPICS.CSL.2017.18","ieee":"K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Improved set-based symbolic algorithms for parity games,” presented at the CSL: Conference on Computer Science Logic, Stockholm, Sweden, 2017, vol. 82.","ista":"Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. 2017. Improved set-based symbolic algorithms for parity games. CSL: Conference on Computer Science Logic vol. 82, 18.","ama":"Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Improved set-based symbolic algorithms for parity games. In: Vol 82. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik; 2017. doi:10.4230/LIPICS.CSL.2017.18","chicago":"Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Set-Based Symbolic Algorithms for Parity Games,” Vol. 82. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017. https://doi.org/10.4230/LIPICS.CSL.2017.18.","short":"K. Chatterjee, W. Dvorák, M.H. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017.","mla":"Chatterjee, Krishnendu, et al. Improved Set-Based Symbolic Algorithms for Parity Games. Vol. 82, 18, Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017, doi:10.4230/LIPICS.CSL.2017.18."},"date_published":"2017-08-01T00:00:00Z","scopus_import":"1","day":"01","has_accepted_license":"1","article_processing_charge":"No","publication_status":"published","publisher":"Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik","department":[{"_id":"KrCh"}],"year":"2017","date_created":"2019-06-04T12:42:43Z","date_updated":"2023-02-14T10:08:25Z","volume":82,"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Wolfgang","last_name":"Dvorák","full_name":"Dvorák, Wolfgang"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer","first_name":"Veronika"}],"article_number":"18","license":"https://creativecommons.org/licenses/by/3.0/","file_date_updated":"2020-07-14T12:47:33Z","ec_funded":1,"quality_controlled":"1","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","short":"CC BY (3.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"conference":{"end_date":"2017-08-24","start_date":"2017-08-20","location":"Stockholm, Sweden","name":"CSL: Conference on Computer Science Logic"},"doi":"10.4230/LIPICS.CSL.2017.18","month":"08"},{"publication_identifier":{"issn":["10614036"]},"month":"03","doi":"10.1038/ng.3764","language":[{"iso":"eng"}],"oa":1,"external_id":{"pmid":["28092682"]},"project":[{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"}],"quality_controlled":"1","ec_funded":1,"publist_id":"7092","file_date_updated":"2020-07-14T12:47:33Z","author":[{"full_name":"Makohon Moore, Alvin","last_name":"Makohon Moore","first_name":"Alvin"},{"full_name":"Zhang, Ming","first_name":"Ming","last_name":"Zhang"},{"full_name":"Reiter, Johannes","orcid":"0000-0002-0170-7353","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter","first_name":"Johannes"},{"last_name":"Božić","first_name":"Ivana","full_name":"Božić, Ivana"},{"full_name":"Allen, Benjamin","last_name":"Allen","first_name":"Benjamin"},{"full_name":"Kundu, Deepanjan","last_name":"Kundu","first_name":"Deepanjan","id":"1d4c0f4f-e8a3-11ec-a351-e36772758c45"},{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Wong, Fay","first_name":"Fay","last_name":"Wong"},{"first_name":"Yuchen","last_name":"Jiao","full_name":"Jiao, Yuchen"},{"full_name":"Kohutek, Zachary","last_name":"Kohutek","first_name":"Zachary"},{"full_name":"Hong, Jungeui","first_name":"Jungeui","last_name":"Hong"},{"first_name":"Marc","last_name":"Attiyeh","full_name":"Attiyeh, Marc"},{"last_name":"Javier","first_name":"Breanna","full_name":"Javier, Breanna"},{"first_name":"Laura","last_name":"Wood","full_name":"Wood, Laura"},{"first_name":"Ralph","last_name":"Hruban","full_name":"Hruban, Ralph"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"},{"full_name":"Papadopoulos, Nickolas","last_name":"Papadopoulos","first_name":"Nickolas"},{"full_name":"Kinzler, Kenneth","first_name":"Kenneth","last_name":"Kinzler"},{"first_name":"Bert","last_name":"Vogelstein","full_name":"Vogelstein, Bert"},{"full_name":"Iacobuzio Donahue, Christine","last_name":"Iacobuzio Donahue","first_name":"Christine"}],"volume":49,"date_updated":"2022-06-10T09:55:08Z","date_created":"2018-12-11T11:47:43Z","pmid":1,"year":"2017","acknowledgement":"We thank the Memorial Sloan Kettering Cancer Center Molecular Cytology core facility for immunohistochemistry staining. This work was supported by Office of Naval Research grant N00014-16-1-2914, the Bill and Melinda Gates Foundation (OPP1148627), and a gift from B. Wu and E. Larson (M.A.N.), National Institutes of Health grants CA179991 (C.A.I.-D. and I.B.), F31 CA180682 (A.P.M.-M.), CA43460 (B.V.), and P50 CA62924, the Monastra Foundation, the Virginia and D.K. Ludwig Fund for Cancer Research, the Lustgarten Foundation for Pancreatic Cancer Research, the Sol Goldman Center for Pancreatic Cancer Research, the Sol Goldman Sequencing Center, ERC Start grant 279307: Graph Games (J.G.R., D.K., and C.K.), Austrian Science Fund (FWF) grant P23499-N23 (J.G.R., D.K., and C.K.), and FWF NFN grant S11407-N23 RiSE/SHiNE (J.G.R., D.K., and C.K.).","department":[{"_id":"KrCh"}],"publisher":"Nature Publishing Group","publication_status":"published","article_processing_charge":"No","has_accepted_license":"1","day":"01","scopus_import":"1","date_published":"2017-03-01T00:00:00Z","citation":{"mla":"Makohon Moore, Alvin, et al. “Limited Heterogeneity of Known Driver Gene Mutations among the Metastases of Individual Patients with Pancreatic Cancer.” Nature Genetics, vol. 49, no. 3, Nature Publishing Group, 2017, pp. 358–66, doi:10.1038/ng.3764.","short":"A. Makohon Moore, M. Zhang, J. Reiter, I. Božić, B. Allen, D. Kundu, K. Chatterjee, F. Wong, Y. Jiao, Z. Kohutek, J. Hong, M. Attiyeh, B. Javier, L. Wood, R. Hruban, M. Nowak, N. Papadopoulos, K. Kinzler, B. Vogelstein, C. Iacobuzio Donahue, Nature Genetics 49 (2017) 358–366.","chicago":"Makohon Moore, Alvin, Ming Zhang, Johannes Reiter, Ivana Božić, Benjamin Allen, Deepanjan Kundu, Krishnendu Chatterjee, et al. “Limited Heterogeneity of Known Driver Gene Mutations among the Metastases of Individual Patients with Pancreatic Cancer.” Nature Genetics. Nature Publishing Group, 2017. https://doi.org/10.1038/ng.3764.","ama":"Makohon Moore A, Zhang M, Reiter J, et al. Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer. Nature Genetics. 2017;49(3):358-366. doi:10.1038/ng.3764","ista":"Makohon Moore A, Zhang M, Reiter J, Božić I, Allen B, Kundu D, Chatterjee K, Wong F, Jiao Y, Kohutek Z, Hong J, Attiyeh M, Javier B, Wood L, Hruban R, Nowak M, Papadopoulos N, Kinzler K, Vogelstein B, Iacobuzio Donahue C. 2017. Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer. Nature Genetics. 49(3), 358–366.","apa":"Makohon Moore, A., Zhang, M., Reiter, J., Božić, I., Allen, B., Kundu, D., … Iacobuzio Donahue, C. (2017). Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer. Nature Genetics. Nature Publishing Group. https://doi.org/10.1038/ng.3764","ieee":"A. Makohon Moore et al., “Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer,” Nature Genetics, vol. 49, no. 3. Nature Publishing Group, pp. 358–366, 2017."},"publication":"Nature Genetics","page":"358 - 366","article_type":"original","issue":"3","abstract":[{"lang":"eng","text":"The extent of heterogeneity among driver gene mutations present in naturally occurring metastases - that is, treatment-naive metastatic disease - is largely unknown. To address this issue, we carried out 60× whole-genome sequencing of 26 metastases from four patients with pancreatic cancer. We found that identical mutations in known driver genes were present in every metastatic lesion for each patient studied. Passenger gene mutations, which do not have known or predicted functional consequences, accounted for all intratumoral heterogeneity. Even with respect to these passenger mutations, our analysis suggests that the genetic similarity among the founding cells of metastases was higher than that expected for any two cells randomly taken from a normal tissue. The uniformity of known driver gene mutations among metastases in the same patient has critical and encouraging implications for the success of future targeted therapies in advanced-stage disease."}],"type":"journal_article","oa_version":"Submitted Version","file":[{"checksum":"e442dc3b7420a36ec805e9bb45cc1a2e","date_created":"2019-11-19T08:13:50Z","date_updated":"2020-07-14T12:47:33Z","file_id":"7050","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_size":908099,"access_level":"open_access","file_name":"2017_NatureGenetics_Makohon.pdf"}],"_id":"653","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 49","title":"Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer","ddc":["000"],"status":"public"},{"volume":114,"date_created":"2018-12-11T11:47:50Z","date_updated":"2021-01-12T08:08:37Z","author":[{"full_name":"Hilbe, Christian","first_name":"Christian","last_name":"Hilbe","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5116-955X"},{"last_name":"Martinez","first_name":"Vaquero","full_name":"Martinez, Vaquero"},{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"publisher":"National Academy of Sciences","department":[{"_id":"KrCh"}],"publication_status":"published","pmid":1,"year":"2017","ec_funded":1,"publist_id":"7053","language":[{"iso":"eng"}],"doi":"10.1073/pnas.1621239114","project":[{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5422766/"}],"external_id":{"pmid":["28420786"]},"publication_identifier":{"issn":["00278424"]},"month":"05","oa_version":"Published Version","intvolume":" 114","title":"Memory-n strategies of direct reciprocity","status":"public","_id":"671","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","issue":"18","abstract":[{"lang":"eng","text":"Humans routinely use conditionally cooperative strategies when interacting in repeated social dilemmas. They are more likely to cooperate if others cooperated before, and are ready to retaliate if others defected. To capture the emergence of reciprocity, most previous models consider subjects who can only choose from a restricted set of representative strategies, or who react to the outcome of the very last round only. As players memorize more rounds, the dimension of the strategy space increases exponentially. This increasing computational complexity renders simulations for individuals with higher cognitive abilities infeasible, especially if multiplayer interactions are taken into account. Here, we take an axiomatic approach instead. We propose several properties that a robust cooperative strategy for a repeated multiplayer dilemma should have. These properties naturally lead to a unique class of cooperative strategies, which contains the classical Win-Stay Lose-Shift rule as a special case. A comprehensive numerical analysis for the prisoner's dilemma and for the public goods game suggests that strategies of this class readily evolve across various memory-n spaces. Our results reveal that successful strategies depend not only on how cooperative others were in the past but also on the respective context of cooperation."}],"type":"journal_article","date_published":"2017-05-02T00:00:00Z","page":"4715 - 4720","citation":{"ista":"Hilbe C, Martinez V, Chatterjee K, Nowak M. 2017. Memory-n strategies of direct reciprocity. PNAS. 114(18), 4715–4720.","ieee":"C. Hilbe, V. Martinez, K. Chatterjee, and M. Nowak, “Memory-n strategies of direct reciprocity,” PNAS, vol. 114, no. 18. National Academy of Sciences, pp. 4715–4720, 2017.","apa":"Hilbe, C., Martinez, V., Chatterjee, K., & Nowak, M. (2017). Memory-n strategies of direct reciprocity. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.1621239114","ama":"Hilbe C, Martinez V, Chatterjee K, Nowak M. Memory-n strategies of direct reciprocity. PNAS. 2017;114(18):4715-4720. doi:10.1073/pnas.1621239114","chicago":"Hilbe, Christian, Vaquero Martinez, Krishnendu Chatterjee, and Martin Nowak. “Memory-n Strategies of Direct Reciprocity.” PNAS. National Academy of Sciences, 2017. https://doi.org/10.1073/pnas.1621239114.","mla":"Hilbe, Christian, et al. “Memory-n Strategies of Direct Reciprocity.” PNAS, vol. 114, no. 18, National Academy of Sciences, 2017, pp. 4715–20, doi:10.1073/pnas.1621239114.","short":"C. Hilbe, V. Martinez, K. Chatterjee, M. Nowak, PNAS 114 (2017) 4715–4720."},"publication":"PNAS","article_processing_charge":"Yes (in subscription journal)","day":"02","scopus_import":1},{"article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2017-06-01T00:00:00Z","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, Emmanuel Filiot, and Jean Raskin. “Doomsday Equilibria for Omega-Regular Games.” Information and Computation. Elsevier, 2017. https://doi.org/10.1016/j.ic.2016.10.012.","short":"K. Chatterjee, L. Doyen, E. Filiot, J. Raskin, Information and Computation 254 (2017) 296–315.","mla":"Chatterjee, Krishnendu, et al. “Doomsday Equilibria for Omega-Regular Games.” Information and Computation, vol. 254, Elsevier, 2017, pp. 296–315, doi:10.1016/j.ic.2016.10.012.","ieee":"K. Chatterjee, L. Doyen, E. Filiot, and J. Raskin, “Doomsday equilibria for omega-regular games,” Information and Computation, vol. 254. Elsevier, pp. 296–315, 2017.","apa":"Chatterjee, K., Doyen, L., Filiot, E., & Raskin, J. (2017). Doomsday equilibria for omega-regular games. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2016.10.012","ista":"Chatterjee K, Doyen L, Filiot E, Raskin J. 2017. Doomsday equilibria for omega-regular games. Information and Computation. 254, 296–315.","ama":"Chatterjee K, Doyen L, Filiot E, Raskin J. Doomsday equilibria for omega-regular games. Information and Computation. 2017;254:296-315. doi:10.1016/j.ic.2016.10.012"},"publication":"Information and Computation","page":"296 - 315","article_type":"original","abstract":[{"text":"Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile where all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players' objective, then the objective of every player is violated. We present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω-regular objectives, both for imperfect-information games, and for perfect-information games. We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games.","lang":"eng"}],"type":"journal_article","oa_version":"Submitted Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"681","intvolume":" 254","title":"Doomsday equilibria for omega-regular games","status":"public","publication_identifier":{"issn":["08905401"]},"month":"06","doi":"10.1016/j.ic.2016.10.012","language":[{"iso":"eng"}],"external_id":{"arxiv":["1311.3238"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1311.3238"}],"oa":1,"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"quality_controlled":"1","publist_id":"7036","ec_funded":1,"related_material":{"record":[{"id":"10885","status":"public","relation":"earlier_version"}]},"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"first_name":"Emmanuel","last_name":"Filiot","full_name":"Filiot, Emmanuel"},{"full_name":"Raskin, Jean","first_name":"Jean","last_name":"Raskin"}],"volume":254,"date_created":"2018-12-11T11:47:53Z","date_updated":"2023-02-21T16:06:02Z","year":"2017","publisher":"Elsevier","department":[{"_id":"KrCh"}],"publication_status":"published"},{"publist_id":"7026","date_created":"2018-12-11T11:47:54Z","date_updated":"2021-04-16T12:10:53Z","volume":82,"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Piterman, Nir","last_name":"Piterman","first_name":"Nir"}],"publication_status":"published","publisher":"Cambridge University Press","department":[{"_id":"KrCh"}],"year":"2017","month":"06","publication_identifier":{"eissn":["1943-5886"],"issn":["0022-4812"]},"language":[{"iso":"eng"}],"doi":"10.1017/jsl.2016.71","quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1206.5174","open_access":"1"}],"abstract":[{"lang":"eng","text":"We generalize winning conditions in two-player games by adding a structural acceptance condition called obligations. Obligations are orthogonal to the linear winning conditions that define whether a play is winning. Obligations are a declaration that player 0 can achieve a certain value from a configuration. If the obligation is met, the value of that configuration for player 0 is 1. We define the value in such games and show that obligation games are determined. For Markov chains with Borel objectives and obligations, and finite turn-based stochastic parity games with obligations we give an alternative and simpler characterization of the value function. Based on this simpler definition we show that the decision problem of winning finite turn-based stochastic parity games with obligations is in NP∩co-NP. We also show that obligation games provide a game framework for reasoning about p-automata. © 2017 The Association for Symbolic Logic."}],"issue":"2","type":"journal_article","oa_version":"Submitted Version","title":"Obligation blackwell games and p-automata","status":"public","intvolume":" 82","_id":"684","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2017-06-01T00:00:00Z","page":"420 - 452","publication":"Journal of Symbolic Logic","citation":{"ieee":"K. Chatterjee and N. Piterman, “Obligation blackwell games and p-automata,” Journal of Symbolic Logic, vol. 82, no. 2. Cambridge University Press, pp. 420–452, 2017.","apa":"Chatterjee, K., & Piterman, N. (2017). Obligation blackwell games and p-automata. Journal of Symbolic Logic. Cambridge University Press. https://doi.org/10.1017/jsl.2016.71","ista":"Chatterjee K, Piterman N. 2017. Obligation blackwell games and p-automata. Journal of Symbolic Logic. 82(2), 420–452.","ama":"Chatterjee K, Piterman N. Obligation blackwell games and p-automata. Journal of Symbolic Logic. 2017;82(2):420-452. doi:10.1017/jsl.2016.71","chicago":"Chatterjee, Krishnendu, and Nir Piterman. “Obligation Blackwell Games and P-Automata.” Journal of Symbolic Logic. Cambridge University Press, 2017. https://doi.org/10.1017/jsl.2016.71.","short":"K. Chatterjee, N. Piterman, Journal of Symbolic Logic 82 (2017) 420–452.","mla":"Chatterjee, Krishnendu, and Nir Piterman. “Obligation Blackwell Games and P-Automata.” Journal of Symbolic Logic, vol. 82, no. 2, Cambridge University Press, 2017, pp. 420–52, doi:10.1017/jsl.2016.71."}},{"publist_id":"7002","year":"2017","pmid":1,"publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"National Academy of Sciences","author":[{"last_name":"Veller","first_name":"Carl","full_name":"Veller, Carl"},{"last_name":"Hayward","first_name":"Laura","full_name":"Hayward, Laura"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"},{"full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","last_name":"Hilbe","first_name":"Christian"}],"date_updated":"2021-01-12T08:11:21Z","date_created":"2018-12-11T11:48:00Z","volume":114,"month":"07","publication_identifier":{"issn":["00278424"]},"main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5502615/","open_access":"1"}],"oa":1,"external_id":{"pmid":["28630336"]},"quality_controlled":"1","doi":"10.1073/pnas.1702020114","language":[{"iso":"eng"}],"type":"journal_article","abstract":[{"text":"In antagonistic symbioses, such as host–parasite interactions, one population’s success is the other’s loss. In mutualistic symbioses, such as division of labor, both parties can gain, but they might have different preferences over the possible mutualistic arrangements. The rates of evolution of the two populations in a symbiosis are important determinants of which population will be more successful: Faster evolution is thought to be favored in antagonistic symbioses (the “Red Queen effect”), but disfavored in certain mutualistic symbioses (the “Red King effect”). However, it remains unclear which biological parameters drive these effects. Here, we analyze the effects of the various determinants of evolutionary rate: generation time, mutation rate, population size, and the intensity of natural selection. Our main results hold for the case where mutation is infrequent. Slower evolution causes a long-term advantage in an important class of mutualistic interactions. Surprisingly, less intense selection is the strongest driver of this Red King effect, whereas relative mutation rates and generation times have little effect. In antagonistic interactions, faster evolution by any means is beneficial. Our results provide insight into the demographic evolution of symbionts. ","lang":"eng"}],"issue":"27","_id":"699","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"The red queen and king in finite populations","intvolume":" 114","oa_version":"Submitted Version","scopus_import":1,"day":"03","publication":"PNAS","citation":{"ieee":"C. Veller, L. Hayward, M. Nowak, and C. Hilbe, “The red queen and king in finite populations,” PNAS, vol. 114, no. 27. National Academy of Sciences, pp. E5396–E5405, 2017.","apa":"Veller, C., Hayward, L., Nowak, M., & Hilbe, C. (2017). The red queen and king in finite populations. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.1702020114","ista":"Veller C, Hayward L, Nowak M, Hilbe C. 2017. The red queen and king in finite populations. PNAS. 114(27), E5396–E5405.","ama":"Veller C, Hayward L, Nowak M, Hilbe C. The red queen and king in finite populations. PNAS. 2017;114(27):E5396-E5405. doi:10.1073/pnas.1702020114","chicago":"Veller, Carl, Laura Hayward, Martin Nowak, and Christian Hilbe. “The Red Queen and King in Finite Populations.” PNAS. National Academy of Sciences, 2017. https://doi.org/10.1073/pnas.1702020114.","short":"C. Veller, L. Hayward, M. Nowak, C. Hilbe, PNAS 114 (2017) E5396–E5405.","mla":"Veller, Carl, et al. “The Red Queen and King in Finite Populations.” PNAS, vol. 114, no. 27, National Academy of Sciences, 2017, pp. E5396–405, doi:10.1073/pnas.1702020114."},"page":"E5396 - E5405","date_published":"2017-07-03T00:00:00Z"},{"month":"08","publication_identifier":{"issn":["18688969"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","conference":{"name":"28th International Conference on Concurrency Theory, CONCUR","end_date":"2017-09-08","location":"Berlin, Germany","start_date":"2017-09-05"},"doi":"10.4230/LIPIcs.CONCUR.2017.5","language":[{"iso":"eng"}],"article_number":"5","file_date_updated":"2020-07-14T12:47:49Z","publist_id":"6976","license":"https://creativecommons.org/licenses/by/4.0/","year":"2017","publication_status":"published","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"last_name":"Otop","first_name":"Jan","full_name":"Otop, Jan"}],"date_created":"2018-12-11T11:48:04Z","date_updated":"2021-01-12T08:11:53Z","volume":85,"scopus_import":1,"day":"01","has_accepted_license":"1","citation":{"short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Chatterjee, Krishnendu, et al. Bidirectional Nested Weighted Automata. Vol. 85, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.CONCUR.2017.5.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Bidirectional Nested Weighted Automata,” Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5.","ama":"Chatterjee K, Henzinger TA, Otop J. Bidirectional nested weighted automata. In: Vol 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.CONCUR.2017.5","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2017). Bidirectional nested weighted automata (Vol. 85). Presented at the 28th International Conference on Concurrency Theory, CONCUR, Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Bidirectional nested weighted automata,” presented at the 28th International Conference on Concurrency Theory, CONCUR, Berlin, Germany, 2017, vol. 85.","ista":"Chatterjee K, Henzinger TA, Otop J. 2017. Bidirectional nested weighted automata. 28th International Conference on Concurrency Theory, CONCUR, LIPIcs, vol. 85, 5."},"date_published":"2017-08-01T00:00:00Z","type":"conference","alternative_title":["LIPIcs"],"abstract":[{"text":"Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts.","lang":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"711","ddc":["004","005"],"title":"Bidirectional nested weighted automata","status":"public","intvolume":" 85","pubrep_id":"886","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"IST-2017-886-v1+1_LIPIcs-CONCUR-2017-5.pdf","content_type":"application/pdf","file_size":570294,"creator":"system","relation":"main_file","file_id":"4661","checksum":"d2bda4783821a6358333fe27f11f4737","date_updated":"2020-07-14T12:47:49Z","date_created":"2018-12-12T10:08:02Z"}]},{"year":"2017","publication_status":"published","publisher":"ACM","department":[{"_id":"KrCh"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Velner, Yaron","last_name":"Velner","first_name":"Yaron"}],"date_created":"2018-12-11T11:48:06Z","date_updated":"2021-01-12T08:12:08Z","volume":64,"publist_id":"6964","ec_funded":1,"external_id":{"arxiv":["1201.2829"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1201.2829"}],"quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"name":"Game Theory","call_identifier":"FWF","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}],"doi":"10.1145/3121408","language":[{"iso":"eng"}],"month":"09","publication_identifier":{"issn":["00045411"]},"_id":"716","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"The complexity of mean-payoff pushdown games","status":"public","intvolume":" 64","oa_version":"Preprint","type":"journal_article","abstract":[{"text":"Two-player games on graphs are central in many problems in formal verification and program analysis, such as synthesis and verification of open systems. In this work, we consider solving recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion.While pushdown games have been studied before with qualitative objectives-such as reachability and ?-regular objectives- in this work, we study for the first time such games with the most well-studied quantitative objective, the mean-payoff objective. In pushdown games, two types of strategies are relevant: (1) global strategies, which depend on the entire global history; and (2) modular strategies, which have only local memory and thus do not depend on the context of invocation but rather only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity by showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games and memoryless modular strategies are sufficient in two-player pushdown games. Finally, we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.","lang":"eng"}],"issue":"5","publication":"Journal of the ACM","citation":{"mla":"Chatterjee, Krishnendu, and Yaron Velner. “The Complexity of Mean-Payoff Pushdown Games.” Journal of the ACM, vol. 64, no. 5, ACM, 2017, p. 34, doi:10.1145/3121408.","short":"K. Chatterjee, Y. Velner, Journal of the ACM 64 (2017) 34.","chicago":"Chatterjee, Krishnendu, and Yaron Velner. “The Complexity of Mean-Payoff Pushdown Games.” Journal of the ACM. ACM, 2017. https://doi.org/10.1145/3121408.","ama":"Chatterjee K, Velner Y. The complexity of mean-payoff pushdown games. Journal of the ACM. 2017;64(5):34. doi:10.1145/3121408","ista":"Chatterjee K, Velner Y. 2017. The complexity of mean-payoff pushdown games. Journal of the ACM. 64(5), 34.","apa":"Chatterjee, K., & Velner, Y. (2017). The complexity of mean-payoff pushdown games. Journal of the ACM. ACM. https://doi.org/10.1145/3121408","ieee":"K. Chatterjee and Y. Velner, “The complexity of mean-payoff pushdown games,” Journal of the ACM, vol. 64, no. 5. ACM, p. 34, 2017."},"article_type":"original","page":"34","date_published":"2017-09-01T00:00:00Z","scopus_import":1,"day":"01"},{"date_published":"2017-09-01T00:00:00Z","citation":{"ama":"Chatterjee K, Velner Y. Hyperplane separation technique for multidimensional mean-payoff games. Journal of Computer and System Sciences. 2017;88:236-259. doi:10.1016/j.jcss.2017.04.005","ista":"Chatterjee K, Velner Y. 2017. Hyperplane separation technique for multidimensional mean-payoff games. Journal of Computer and System Sciences. 88, 236–259.","apa":"Chatterjee, K., & Velner, Y. (2017). Hyperplane separation technique for multidimensional mean-payoff games. Journal of Computer and System Sciences. Academic Press. https://doi.org/10.1016/j.jcss.2017.04.005","ieee":"K. Chatterjee and Y. Velner, “Hyperplane separation technique for multidimensional mean-payoff games,” Journal of Computer and System Sciences, vol. 88. Academic Press, pp. 236–259, 2017.","mla":"Chatterjee, Krishnendu, and Yaron Velner. “Hyperplane Separation Technique for Multidimensional Mean-Payoff Games.” Journal of Computer and System Sciences, vol. 88, Academic Press, 2017, pp. 236–59, doi:10.1016/j.jcss.2017.04.005.","short":"K. Chatterjee, Y. Velner, Journal of Computer and System Sciences 88 (2017) 236–259.","chicago":"Chatterjee, Krishnendu, and Yaron Velner. “Hyperplane Separation Technique for Multidimensional Mean-Payoff Games.” Journal of Computer and System Sciences. Academic Press, 2017. https://doi.org/10.1016/j.jcss.2017.04.005."},"publication":"Journal of Computer and System Sciences","page":"236 - 259","day":"01","scopus_import":1,"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"717","intvolume":" 88","title":"Hyperplane separation technique for multidimensional mean-payoff games","status":"public","abstract":[{"lang":"eng","text":"We consider finite-state and recursive game graphs with multidimensional mean-payoff objectives. In recursive games two types of strategies are relevant: global strategies and modular strategies. Our contributions are: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of weights are fixed; whereas for arbitrary dimensions the problem is coNP-complete. (2) We show that one-player recursive games with multidimensional mean-payoff objectives can be solved in polynomial time. Both above algorithms are based on hyperplane separation technique. (3) For recursive games we show that under modular strategies the multidimensional problem is undecidable. We show that if the number of modules, exits, and the maximal absolute value of the weights are fixed, then one-dimensional recursive mean-payoff games under modular strategies can be solved in polynomial time, whereas for unbounded number of exits or modules the problem is NP-hard."}],"type":"journal_article","doi":"10.1016/j.jcss.2017.04.005","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1210.3141"}],"oa":1,"project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","month":"09","related_material":{"record":[{"id":"2329","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Velner, Yaron","last_name":"Velner","first_name":"Yaron"}],"volume":88,"date_updated":"2023-02-23T10:38:15Z","date_created":"2018-12-11T11:48:07Z","year":"2017","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), Microsoft faculty fellows award, the RICH Model Toolkit (ICT COST Action IC0901), and was carried out in partial fulfillment of the requirements for the Ph.D. degree of the second author.","publisher":"Academic Press","department":[{"_id":"KrCh"}],"publication_status":"published","publist_id":"6963","ec_funded":1}]