[{"scopus_import":"1","doi":"10.1007/978-3-032-08707-2_19","status":"public","department":[{"_id":"KrCh"}],"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"OA_place":"repository","corr_author":"1","oa_version":"Preprint","date_published":"2025-10-26T00:00:00Z","type":"conference","intvolume":"     16145","language":[{"iso":"eng"}],"external_id":{"arxiv":["2408.03796"]},"volume":16145,"month":"10","OA_type":"green","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2408.03796"}],"quality_controlled":"1","ec_funded":1,"article_processing_charge":"No","day":"26","publication_status":"published","arxiv":1,"date_updated":"2026-09-16T07:03:56Z","page":"411-424","abstract":[{"text":"Polynomial quantified entailments with existentially and universally quantified variables arise in many problems of verification and program analysis. We present PolyQEnt which is a tool for solving polynomial quantified entailments in which variables on both sides of the implication are real valued or unbounded integers. Our tool provides a unified framework for polynomial quantified entailment problems that arise in several papers in the literature. Our experimental evaluation over a wide range of benchmarks shows the applicability of the tool as well as its benefits as opposed to simply using existing SMT solvers to solve such constraints.","lang":"eng"}],"title":"PolyQEnt: A polynomial quantified entailment solver","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir Kafshdar","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir Kafshdar","last_name":"Goharshady"},{"last_name":"Kafshdar Goharshadi","full_name":"Kafshdar Goharshadi, Ehsan","first_name":"Ehsan","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","orcid":"0000-0002-8595-0587"},{"full_name":"Karrabi, Mehrdad","last_name":"Karrabi","orcid":"0009-0007-5253-9170","id":"67638922-f394-11eb-9cf6-f20423e08757","first_name":"Mehrdad"},{"first_name":"Milad","last_name":"Saadat","full_name":"Saadat, Milad"},{"first_name":"Maximilian","last_name":"Seeliger","full_name":"Seeliger, Maximilian"},{"full_name":"Zikelic, Dorde","last_name":"Zikelic","orcid":"0000-0002-4681-1699","first_name":"Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87"}],"publication":"23rd International Symposium on Automated Technology for Verification and Analysis","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783032087065"],"issn":["0302-9743"]},"alternative_title":["LNCS"],"_id":"20648","year":"2025","conference":{"location":"Bengaluru, India","name":"ATVA: Automated Technology for Verification and Analysis","end_date":"2025-10-31","start_date":"2025-10-27"},"citation":{"ama":"Chatterjee K, Goharshady AK, Goharshady E, et al. PolyQEnt: A polynomial quantified entailment solver. In: <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>. Vol 16145. Springer Nature; 2025:411-424. doi:<a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">10.1007/978-3-032-08707-2_19</a>","mla":"Chatterjee, Krishnendu, et al. “PolyQEnt: A Polynomial Quantified Entailment Solver.” <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>, vol. 16145, Springer Nature, 2025, pp. 411–24, doi:<a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">10.1007/978-3-032-08707-2_19</a>.","apa":"Chatterjee, K., Goharshady, A. K., Goharshady, E., Karrabi, M., Saadat, M., Seeliger, M., &#38; Zikelic, D. (2025). PolyQEnt: A polynomial quantified entailment solver. In <i>23rd International Symposium on Automated Technology for Verification and Analysis</i> (Vol. 16145, pp. 411–424). Bengaluru, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">https://doi.org/10.1007/978-3-032-08707-2_19</a>","ista":"Chatterjee K, Goharshady AK, Goharshady E, Karrabi M, Saadat M, Seeliger M, Zikelic D. 2025. PolyQEnt: A polynomial quantified entailment solver. 23rd International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 16145, 411–424.","ieee":"K. Chatterjee <i>et al.</i>, “PolyQEnt: A polynomial quantified entailment solver,” in <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>, Bengaluru, India, 2025, vol. 16145, pp. 411–424.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Ehsan Goharshady, Mehrdad Karrabi, Milad Saadat, Maximilian Seeliger, and Dorde Zikelic. “PolyQEnt: A Polynomial Quantified Entailment Solver.” In <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>, 16145:411–24. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">https://doi.org/10.1007/978-3-032-08707-2_19</a>.","short":"K. Chatterjee, A.K. Goharshady, E. Goharshady, M. Karrabi, M. Saadat, M. Seeliger, D. Zikelic, in:, 23rd International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2025, pp. 411–424."},"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2025-11-16T23:01:24Z","publisher":"Springer Nature","acknowledgement":"This work was supported by the following grants: ERC CoG 863818 (ForM-SMArt), Austrian Science Fund (FWF) 10.55776/COE12, ERC StG 101222524 (SPES), the Ethereum Foundation Research Grant FY24-1793, and the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant (Project ID:22-SISSMU-100).","fulldoi":"https://doi.org/10.1007/978-3-032-08707-2_19"},{"publication":"2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science","author":[{"first_name":"Thomas","full_name":"Brihaye, Thomas","last_name":"Brihaye"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Mohr, Stefanie","last_name":"Mohr","first_name":"Stefanie"},{"id":"02ab0197-cc70-11ed-ab61-918e71f56881","first_name":"Maximilian","orcid":"0000-0002-0163-2152","full_name":"Weininger, Maximilian","last_name":"Weininger"}],"title":"Risk-aware Markov decision processes using cumulative prospect theory","abstract":[{"text":"Cumulative prospect theory (CPT) is the first theory for decision-making under uncertainty that combines full theoretical soundness and empirically realistic features [1], [Page 2]. While CPT was originally considered in one-shot settings for risk-aware decision-making, we consider CPT in sequential decision-making. The most fundamental and well-studied models for sequential decision-making are Markov chains (MCs), and their generalization Markov decision processes (MDPs). The complexity theoretic study of MCs and MDPs with CPT is a fundamental problem that has not been addressed in the literature.Our contributions are as follows: First, we present an alternative viewpoint for the CPT-value of MCs and MDPs. This allows us to establish a connection with multi-objective reachability analysis and conclude the strategy complexity result that memoryless randomized strategies are necessary and sufficient for optimality. Second, based on this connection, we provide an algorithm for computing the CPT-value in MDPs with infinite-horizon objectives. We show that the problem is in EXPTIME and fixed-parameter tractable. Moreover, we provide a polynomial-time algorithm for the special case of MCs.","lang":"eng"}],"page":"458-471","_id":"20690","conference":{"name":"LICS: Logic in Computer Science","location":"Singapore, Singapore","end_date":"2025-06-26","start_date":"2025-06-23"},"year":"2025","publication_identifier":{"eisbn":["9798331579005"]},"publication_status":"published","article_processing_charge":"No","day":"09","ec_funded":1,"arxiv":1,"date_updated":"2026-09-16T07:05:13Z","publisher":"IEEE","date_created":"2025-11-24T14:43:47Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This project has received funding from the Fonds de la Recherche Scientifique - FNRS under grant No. T.0027.21, the Belgian National Lottery; the ERC CoG 863818 (ForM-SMArt), the Austrian Science Fund (FWF) 10.55776/COE12; the DFG project 427755713, GOPro, and the DFG research training group GRK 2428 Continuous Verification of Cyber-Physical Systems\r\n(ConVeY); the EU’s Horizon 2020 research and innovation programmes under the Marie Sklodowska-Curie grant agreement No. 101034413 (IST-BRIDGE) and the ERC Starting Grant DEUCE (101077178).","fulldoi":"https://doi.org/10.1109/lics65433.2025.00041","oa":1,"citation":{"short":"T. Brihaye, K. Chatterjee, S. Mohr, M. Weininger, in:, 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2025, pp. 458–471.","chicago":"Brihaye, Thomas, Krishnendu Chatterjee, Stefanie Mohr, and Maximilian Weininger. “Risk-Aware Markov Decision Processes Using Cumulative Prospect Theory.” In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 458–71. IEEE, 2025. <a href=\"https://doi.org/10.1109/lics65433.2025.00041\">https://doi.org/10.1109/lics65433.2025.00041</a>.","ieee":"T. Brihaye, K. Chatterjee, S. Mohr, and M. Weininger, “Risk-aware Markov decision processes using cumulative prospect theory,” in <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Singapore, Singapore, 2025, pp. 458–471.","ista":"Brihaye T, Chatterjee K, Mohr S, Weininger M. 2025. Risk-aware Markov decision processes using cumulative prospect theory. 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 458–471.","ama":"Brihaye T, Chatterjee K, Mohr S, Weininger M. Risk-aware Markov decision processes using cumulative prospect theory. In: <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2025:458-471. doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00041\">10.1109/lics65433.2025.00041</a>","mla":"Brihaye, Thomas, et al. “Risk-Aware Markov Decision Processes Using Cumulative Prospect Theory.” <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2025, pp. 458–71, doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00041\">10.1109/lics65433.2025.00041</a>.","apa":"Brihaye, T., Chatterjee, K., Mohr, S., &#38; Weininger, M. (2025). Risk-aware Markov decision processes using cumulative prospect theory. In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 458–471). Singapore, Singapore: IEEE. <a href=\"https://doi.org/10.1109/lics65433.2025.00041\">https://doi.org/10.1109/lics65433.2025.00041</a>"},"OA_place":"repository","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"},{"grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"department":[{"_id":"KrCh"}],"status":"public","corr_author":"1","scopus_import":"1","doi":"10.1109/lics65433.2025.00041","month":"10","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2505.09514"}],"OA_type":"green","date_published":"2025-10-09T00:00:00Z","type":"conference","oa_version":"Preprint","external_id":{"arxiv":["2505.09514"]},"language":[{"iso":"eng"}]},{"corr_author":"1","department":[{"_id":"KrCh"}],"project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12"}],"OA_place":"repository","status":"public","doi":"10.1109/lics65433.2025.00044","scopus_import":"1","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2504.18277"}],"OA_type":"green","month":"10","language":[{"iso":"eng"}],"external_id":{"arxiv":["2504.18277"]},"type":"conference","date_published":"2025-10-09T00:00:00Z","oa_version":"Preprint","_id":"20689","conference":{"location":"Singapore, Singapore","name":"LICS: Logic in Computer Science","start_date":"2025-06-23","end_date":"2025-06-26"},"year":"2025","publication_identifier":{"eisbn":["9798331579005"]},"publication":"2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science","author":[{"last_name":"Baier","full_name":"Baier, Christel","first_name":"Christel"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","first_name":"Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1"},{"full_name":"Piribauer, Jakob","last_name":"Piribauer","first_name":"Jakob"}],"title":"Multiplicative rewards in Markovian models","page":"499-512","abstract":[{"lang":"eng","text":"This paper studies the expected value of multiplicative rewards, where rewards obtained in each step are multiplied (instead of the usual addition), in Markov chains (MCs) and Markov decision processes (MDPs). One of the key differences to additive rewards is that the expected value may diverge to ∞ not only due to recurrent, but also due to transient states.For MCs, computing the value is shown to be possible in polynomial time given an oracle for the comparison of succinctly represented integers (CSRI), which is only known to be solvable in polynomial time subject to number-theoretic conjectures. Interestingly, distinguishing whether the value is ∞ or 0 is at least as hard as CSRI, while determining if it is one of these two can be done in polynomial time. In MDPs, the optimal value can be computed in polynomial space. Further refined complexity results and results on the complexity of optimal schedulers are presented. The techniques developed for MDPs additionally allow to solve the multiplicative variant of the stochastic shortest path problem. Finally, for MCs and MDPs where an absorbing state is reached almost surely, all considered problems are solvable in polynomial time."}],"date_updated":"2026-09-16T07:05:41Z","arxiv":1,"article_processing_charge":"No","day":"09","publication_status":"published","ec_funded":1,"acknowledgement":"This work was partly funded by the ERC CoG 863818 (ForM-SMArt), the Austrian Science Fund (FWF) 10.55776/COE12, the DFG Grant 389792660 as part of TRR 248 (Foundations of Perspicuous Software Systems), the Cluster of Excellence EXC 2050/1 (CeTI, project ID\r\n390696704, as part of Germany’s Excellence Strategy), and by the BMBF (Federal Ministry of Education and Research) in DAAD project 57616814 (SECAI, School of Embedded and\r\nComposite AI) as part of the program Konrad Zuse Schools of Excellence in Artificial Intelligence.","fulldoi":"https://doi.org/10.1109/lics65433.2025.00044","date_created":"2025-11-24T14:24:00Z","publisher":"IEEE","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"citation":{"short":"C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2025, pp. 499–512.","chicago":"Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Multiplicative Rewards in Markovian Models.” In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 499–512. IEEE, 2025. <a href=\"https://doi.org/10.1109/lics65433.2025.00044\">https://doi.org/10.1109/lics65433.2025.00044</a>.","ama":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Multiplicative rewards in Markovian models. In: <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2025:499-512. doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00044\">10.1109/lics65433.2025.00044</a>","mla":"Baier, Christel, et al. “Multiplicative Rewards in Markovian Models.” <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2025, pp. 499–512, doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00044\">10.1109/lics65433.2025.00044</a>.","apa":"Baier, C., Chatterjee, K., Meggendorfer, T., &#38; Piribauer, J. (2025). Multiplicative rewards in Markovian models. In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 499–512). Singapore, Singapore: IEEE. <a href=\"https://doi.org/10.1109/lics65433.2025.00044\">https://doi.org/10.1109/lics65433.2025.00044</a>","ista":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2025. Multiplicative rewards in Markovian models. 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 499–512.","ieee":"C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Multiplicative rewards in Markovian models,” in <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Singapore, Singapore, 2025, pp. 499–512."}},{"language":[{"iso":"eng"}],"volume":122,"external_id":{"pmid":["41397136"]},"date_published":"2025-12-15T00:00:00Z","type":"journal_article","intvolume":"       122","oa_version":"Published Version","quality_controlled":"1","file":[{"date_updated":"2025-12-29T09:36:50Z","file_name":"2025_PNAS_Svoboda.pdf","content_type":"application/pdf","creator":"dernst","checksum":"dd50b62a1efc28c0133fe9c11dbee53c","file_size":2308124,"relation":"main_file","access_level":"open_access","success":1,"file_id":"20860","date_created":"2025-12-29T09:36:50Z"}],"OA_type":"hybrid","ddc":["000"],"month":"12","doi":"10.1073/pnas.2524109122","pmid":1,"scopus_import":"1","corr_author":"1","department":[{"_id":"KrCh"}],"OA_place":"publisher","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"status":"public","has_accepted_license":"1","article_type":"original","issue":"51","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","oa":1,"file_date_updated":"2025-12-29T09:36:50Z","citation":{"short":"J. Svoboda, K. Chatterjee, Proceedings of the National Academy of Sciences 122 (2025) e2524109122.","chicago":"Svoboda, Jakub, and Krishnendu Chatterjee. “Promoters of Cooperation in Evolutionary Games.” <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences, 2025. <a href=\"https://doi.org/10.1073/pnas.2524109122\">https://doi.org/10.1073/pnas.2524109122</a>.","ista":"Svoboda J, Chatterjee K. 2025. Promoters of cooperation in evolutionary games. Proceedings of the National Academy of Sciences. 122(51), e2524109122.","mla":"Svoboda, Jakub, and Krishnendu Chatterjee. “Promoters of Cooperation in Evolutionary Games.” <i>Proceedings of the National Academy of Sciences</i>, vol. 122, no. 51, National Academy of Sciences, 2025, p. e2524109122, doi:<a href=\"https://doi.org/10.1073/pnas.2524109122\">10.1073/pnas.2524109122</a>.","apa":"Svoboda, J., &#38; Chatterjee, K. (2025). Promoters of cooperation in evolutionary games. <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.2524109122\">https://doi.org/10.1073/pnas.2524109122</a>","ama":"Svoboda J, Chatterjee K. Promoters of cooperation in evolutionary games. <i>Proceedings of the National Academy of Sciences</i>. 2025;122(51):e2524109122. doi:<a href=\"https://doi.org/10.1073/pnas.2524109122\">10.1073/pnas.2524109122</a>","ieee":"J. Svoboda and K. Chatterjee, “Promoters of cooperation in evolutionary games,” <i>Proceedings of the National Academy of Sciences</i>, vol. 122, no. 51. National Academy of Sciences, p. e2524109122, 2025."},"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)"},"acknowledgement":"J.S. and K.C. were supported by the European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","fulldoi":"https://doi.org/10.1073/pnas.2524109122","date_created":"2025-12-28T23:01:26Z","publisher":"National Academy of Sciences","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-16T07:20:45Z","APC_amount":"3003,56 EUR","article_processing_charge":"Yes (in subscription journal)","day":"15","publication_status":"published","ec_funded":1,"_id":"20857","year":"2025","publication_identifier":{"eissn":["1091-6490"]},"title":"Promoters of cooperation in evolutionary games","author":[{"orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","full_name":"Svoboda, Jakub","last_name":"Svoboda"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"}],"publication":"Proceedings of the National Academy of Sciences","page":"e2524109122","abstract":[{"text":"Evolutionary games provide a flexible mathematical framework for many problems in biology and social evolution. Prisoners’ dilemma, and in particular, the important special case of donation games, represents social dilemmas where cooperation is mutually beneficial, yet defection is preferred by selfish agents. In evolutionary games on networks, the agents interact over a population structure. The existence of population structures that promote cooperative behavior is a fascinating and active research topic. Previous research establishes structures promoting cooperation in the limit of weak selection where the benefit-to-cost ratio β exceeds 1.5. The existence of such structures for medium and strong selection for 1 < ß < 2 and for weak selection for 1 < ß < 1.5 has been a long-standing open question. First, we answer the open questions in the affirmative: For every selection strength and every ß > 1, we construct networks promoting cooperation. Second, we present a robustness result with respect to β and selection strength: Our structures promote cooperation for a range of these parameter values rather than specific parameter values. Finally, we supplement our theoretical results with simulation results on small population structures that show the effectiveness of our construction over well-studied population structures.","lang":"eng"}]},{"ec_funded":1,"day":"30","article_processing_charge":"No","publication_status":"published","date_updated":"2026-09-16T07:25:05Z","arxiv":1,"abstract":[{"text":"Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. \r\nThis model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have a random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon’s distribution. Alijani et al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single threshold, a ratio of 1/2 is actually achievable for several larger classes of horizon distributions, with the largest being known as the 𝒢 class in reliability theory. Moreover, we show that this does not extend to its dual, the  ̅𝒢 class (which includes the decreasing hazard rate class), while it can be extended to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms.","lang":"eng"}],"title":"IID prophet inequality with random horizon: Going beyond increasing hazard rates","author":[{"first_name":"Giordano","full_name":"Giambartolomei, Giordano","last_name":"Giambartolomei"},{"first_name":"Frederik","full_name":"Mallmann-Trenn, Frederik","last_name":"Mallmann-Trenn"},{"full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","orcid":"0000-0001-5103-038X"}],"publication":"52nd International Colloquium on Automata, Languages, and Programming","publication_identifier":{"isbn":["9783959773720"]},"alternative_title":["LIPIcs"],"_id":"21320","conference":{"location":"Aarhus, Denmark","name":"ICALP: Automata, Languages and Programming","start_date":"2025-07-08","end_date":"2025-07-11"},"year":"2025","file_date_updated":"2026-02-19T07:41:55Z","citation":{"ama":"Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. IID prophet inequality with random horizon: Going beyond increasing hazard rates. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">10.4230/LIPIcs.ICALP.2025.87</a>","apa":"Giambartolomei, G., Mallmann-Trenn, F., &#38; Saona Urmeneta, R. J. (2025). IID prophet inequality with random horizon: Going beyond increasing hazard rates. In <i>52nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 334). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">https://doi.org/10.4230/LIPIcs.ICALP.2025.87</a>","mla":"Giambartolomei, Giordano, et al. “IID Prophet Inequality with Random Horizon: Going beyond Increasing Hazard Rates.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">10.4230/LIPIcs.ICALP.2025.87</a>.","ista":"Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. 2025. IID prophet inequality with random horizon: Going beyond increasing hazard rates. 52nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 334.","ieee":"G. Giambartolomei, F. Mallmann-Trenn, and R. J. Saona Urmeneta, “IID prophet inequality with random horizon: Going beyond increasing hazard rates,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025, vol. 334.","short":"G. Giambartolomei, F. Mallmann-Trenn, R.J. Saona Urmeneta, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","chicago":"Giambartolomei, Giordano, Frederik Mallmann-Trenn, and Raimundo J Saona Urmeneta. “IID Prophet Inequality with Random Horizon: Going beyond Increasing Hazard Rates.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Vol. 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">https://doi.org/10.4230/LIPIcs.ICALP.2025.87</a>."},"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2026-02-18T10:44:14Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","fulldoi":"https://doi.org/10.4230/LIPIcs.ICALP.2025.87","acknowledgement":"We would like to thank José Correa for his precious advice, Bruno Ziliotto and Vasilis Livanos for early conversations. Giambartolomei, Giordano: EPSRC grants EP/W005573/1 and EP/X021696/1. Mallmann-Trenn, Frederik: EPSRC grant EP/W005573/1. Saona, Raimundo: ERC grant CoG 863818 (ForM-SMArt), ANID Chile grant ACT210005, French Agence Nationale de la Recherche (ANR) grant ANR-21-CE40-0020 (CONVERGENCE), and Austrian Science Fund (FWF) grant 10.55776/COE12.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"doi":"10.4230/LIPIcs.ICALP.2025.87","has_accepted_license":"1","status":"public","department":[{"_id":"KrCh"}],"OA_place":"publisher","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"oa_version":"Published Version","type":"conference","date_published":"2025-06-30T00:00:00Z","intvolume":"       334","language":[{"iso":"eng"}],"external_id":{"arxiv":["2407.11752"]},"volume":334,"month":"06","file":[{"content_type":"application/pdf","checksum":"960110956c26a5cefadde8e47888bfbe","creator":"dernst","date_updated":"2026-02-19T07:41:55Z","file_name":"2025_ICALP_Giambartolomei.pdf","success":1,"file_id":"21331","access_level":"open_access","date_created":"2026-02-19T07:41:55Z","file_size":876167,"relation":"main_file"}],"ddc":["000"],"OA_type":"gold","quality_controlled":"1"},{"publication_status":"published","day":"30","article_processing_charge":"No","ec_funded":1,"arxiv":1,"date_updated":"2026-09-16T07:23:50Z","publication":"52nd International Colloquium on Automata, Languages, and Programming","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Doyen","full_name":"Doyen, Laurent","first_name":"Laurent"},{"first_name":"Jean-Francois","full_name":"Raskin, Jean-Francois","last_name":"Raskin"},{"last_name":"Sankur","full_name":"Sankur, Ocan","first_name":"Ocan"}],"title":"The value problem for multiple-environment MDPs with parity objective","abstract":[{"text":"We consider multiple-environment Markov decision processes (MEMDP), which consist of a finite set of MDPs over the same state space, representing different scenarios of transition structure and probability. The value of a strategy is the probability to satisfy the objective, here a parity objective, in the worst-case scenario, and the value of an MEMDP is the supremum of the values achievable by a strategy.\r\nWe show that deciding whether the value is 1 is a PSPACE-complete problem, and even in P when the number of environments is fixed, along with new insights to the almost-sure winning problem, which is to decide if there exists a strategy with value 1. Pure strategies are sufficient for theses problems, whereas randomization is necessary in general when the value is smaller than 1. We present an algorithm to approximate the value, running in double exponential space. Our results are in contrast to the related model of partially-observable MDPs where all these problems are known to be undecidable.","lang":"eng"}],"year":"2025","_id":"21268","conference":{"start_date":"2025-07-08","end_date":"2025-07-11","location":"Aarhus, Denmark","name":"ICALP: Automata, Languages and Programming"},"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959773720"]},"article_number":"150","oa":1,"citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, Jean-Francois Raskin, and Ocan Sankur. “The Value Problem for Multiple-Environment MDPs with Parity Objective.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">https://doi.org/10.4230/LIPIcs.ICALP.2025.150</a>.","short":"K. Chatterjee, L. Doyen, J.-F. Raskin, O. Sankur, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ieee":"K. Chatterjee, L. Doyen, J.-F. Raskin, and O. Sankur, “The value problem for multiple-environment MDPs with parity objective,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025.","apa":"Chatterjee, K., Doyen, L., Raskin, J.-F., &#38; Sankur, O. (2025). The value problem for multiple-environment MDPs with parity objective. In <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">https://doi.org/10.4230/LIPIcs.ICALP.2025.150</a>","mla":"Chatterjee, Krishnendu, et al. “The Value Problem for Multiple-Environment MDPs with Parity Objective.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, 150, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">10.4230/LIPIcs.ICALP.2025.150</a>.","ama":"Chatterjee K, Doyen L, Raskin J-F, Sankur O. The value problem for multiple-environment MDPs with parity objective. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">10.4230/LIPIcs.ICALP.2025.150</a>","ista":"Chatterjee K, Doyen L, Raskin J-F, Sankur O. 2025. The value problem for multiple-environment MDPs with parity objective. 52nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, , 150."},"file_date_updated":"2026-02-18T07:50:56Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2026-02-17T07:49:17Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"acknowledgement":"Krishnendu Chatterjee: ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund\r\n(FWF) 10.55776/COE12. Jean-François Raskin: PDR Weave project FORM-LEARN-POMDP funded by FNRS and DFG, and the support of the Fondation ULB. Ocan Sankur: ANR BisoUS (ANR-22-CE48-0012) and ANR EpiRL (ANR-22-CE23-0029).","fulldoi":"https://doi.org/10.4230/LIPIcs.ICALP.2025.150","scopus_import":"1","doi":"10.4230/LIPIcs.ICALP.2025.150","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"OA_place":"publisher","department":[{"_id":"KrCh"}],"status":"public","has_accepted_license":"1","corr_author":"1","date_published":"2025-07-30T00:00:00Z","type":"conference","oa_version":"Published Version","external_id":{"arxiv":["2504.15960"]},"language":[{"iso":"eng"}],"month":"07","quality_controlled":"1","OA_type":"gold","ddc":["000"],"file":[{"file_name":"2025_LIPIcs_Chatterjee.pdf","date_updated":"2026-02-18T07:50:56Z","checksum":"4477a7fd4fbf0ba6c8e9b15683b5a6b8","creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":1075724,"date_created":"2026-02-18T07:50:56Z","file_id":"21313","success":1,"access_level":"open_access"}]},{"status":"public","has_accepted_license":"1","department":[{"_id":"KrCh"}],"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"OA_place":"publisher","doi":"10.4230/LIPIcs.DISC.2025.23","scopus_import":"1","file":[{"file_id":"21418","success":1,"access_level":"open_access","date_created":"2026-03-09T11:51:59Z","file_size":1130069,"relation":"main_file","content_type":"application/pdf","checksum":"8e3d1594365df60163d9df22158a37b1","creator":"dernst","date_updated":"2026-03-09T11:51:59Z","file_name":"2025_DISC_Chatterjee.pdf"}],"ddc":["000"],"OA_type":"gold","quality_controlled":"1","month":"10","language":[{"iso":"eng"}],"external_id":{"arxiv":["2508.14524"],"cryptoeprintid":["2025/1484"]},"volume":356,"oa_version":"Published Version","type":"conference","date_published":"2025-10-22T00:00:00Z","intvolume":"       356","publication_identifier":{"isbn":["9783959774024"],"issn":["1868-8969"]},"alternative_title":["LIPIcs"],"_id":"21412","year":"2025","conference":{"end_date":"2025-10-31","start_date":"2025-10-27","name":"DISC: Symposium on Distributed Computing","location":"Berlin, Germany"},"abstract":[{"text":"Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over p parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the p cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an 𝒪(p) approximation algorithm for the problem with p parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to 𝒪(√p). We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.","lang":"eng"}],"author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"first_name":"Jan Matyáš","full_name":"Křišťan, Jan Matyáš","last_name":"Křišťan"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"full_name":"Svoboda, Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X"}],"publication":"39th International Symposium on Distributed Computing","cryptoeprintid":1,"title":"Boosting payment channel network liquidity with topology optimization and transaction selection","date_updated":"2026-09-16T07:27:09Z","arxiv":1,"ec_funded":1,"day":"22","article_processing_charge":"No","publication_status":"published","fulldoi":"https://doi.org/10.4230/LIPIcs.DISC.2025.23","acknowledgement":"Chatterjee, Krishnendu: European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.\r\nKřišťan, Jan Matyáš: Czech Science Foundation Grant no. 24-12046S.\r\nSchmid, Stefan: German Research Foundation (DFG) project ReNO (SPP 2378) from 2023-2027.\r\nSvoboda, Jakub: European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.\r\nYeo, Michelle: MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms).","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2026-03-08T23:01:46Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2026-03-09T11:51:59Z","citation":{"chicago":"Chatterjee, Krishnendu, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection.” In <i>39th International Symposium on Distributed Computing</i>, Vol. 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">https://doi.org/10.4230/LIPIcs.DISC.2025.23</a>.","short":"K. Chatterjee, J.M. Křišťan, S. Schmid, J. Svoboda, M.X. Yeo, in:, 39th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ista":"Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. 2025. Boosting payment channel network liquidity with topology optimization and transaction selection. 39th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 356, 23.","apa":"Chatterjee, K., Křišťan, J. M., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2025). Boosting payment channel network liquidity with topology optimization and transaction selection. In <i>39th International Symposium on Distributed Computing</i> (Vol. 356). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">https://doi.org/10.4230/LIPIcs.DISC.2025.23</a>","mla":"Chatterjee, Krishnendu, et al. “Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection.” <i>39th International Symposium on Distributed Computing</i>, vol. 356, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">10.4230/LIPIcs.DISC.2025.23</a>.","ama":"Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. Boosting payment channel network liquidity with topology optimization and transaction selection. In: <i>39th International Symposium on Distributed Computing</i>. Vol 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">10.4230/LIPIcs.DISC.2025.23</a>","ieee":"K. Chatterjee, J. M. Křišťan, S. Schmid, J. Svoboda, and M. X. Yeo, “Boosting payment channel network liquidity with topology optimization and transaction selection,” in <i>39th International Symposium on Distributed Computing</i>, Berlin, Germany, 2025, vol. 356."},"oa":1,"article_number":"23"},{"publication_identifier":{"issn":["2663-337X"]},"alternative_title":["ISTA Thesis"],"doi_confirm":"1","year":"2025","_id":"20234","page":"125","abstract":[{"lang":"eng","text":"Game Theory is the mathematical formalization of social dynamics - systems where agents interact over time and the evolution of the state of the system depends on the decisions of every player. \r\nThis thesis takes the perspective of a single player and focuses on what they can guarantee in the worst case over the behavior of other players.\r\nIn other words, we consider that the objective of every other player in the game is exactly the opposite to the player.\r\nWe focus on sustained interactions over time, where the players repeatedly obtain quantitative rewards over time, and they are interested in maximizing their long-term performance.\t\r\nFormally, this thesis focuses on zero-sum games with the liminf average objective.\r\nTwo fundamental questions that Game Theory aims to answer are the following.\r\n\r\n1. How much can a player guarantee to obtain after the interaction?\r\n\r\n2. How to act in order to obtain the previously mentioned guarantee?\r\n\r\nThese questions are formalized by the concepts of \"value\" and \"optimal strategies\". \t\r\nWe study their properties on games that exhibit one or more of the following properties. \r\n\r\n1. Partial Observation: \r\nthe players can not perfectly observe the current state of the system during the game. We consider the model of (finite) Partially Observable Markov Decision Processes and prove that finite-memory strategies are sufficient to approximately guarantee the value.\r\n\r\n2. Perturbed Description: \r\nthe formal description of the game is perturbed by a small parameter.\r\nWe consider the model of (finite) Perturbed Matrix Games, and provide algorithms to check various robustness properties and to compute the parameterized value and optimal strategies.\r\n\r\n3. Stochastic Transitions: \r\nthe actions of the players determine the behavior of the evolution of the system, described as a probability distribution over the next state.\r\nWe consider the model of (finite) Perturbed Stochastic Games and provide formulas for the marginal value.\r\n\r\n4. Infinite States: \r\nthe system can be in infinitely many states.\r\nWe consider the model of Random Dynamic Games on a class of infinite graphs, prove the existence of the value, and quantify the concentration of finite-horizon values."}],"title":"Robustness of solutions in game theory: Values and strategies in partially observable, perturbed, stochastic, and infinite games","author":[{"orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta"}],"date_updated":"2026-10-02T11:30:08Z","supervisor":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"}],"ec_funded":1,"article_processing_charge":"No","day":"27","publication_status":"published","acknowledgement":"Funding sources The works included in this thesis were partially supported by:\r\n• Austrian Science Fund (FWF), grants 10.55776/COE12 and No RiSE/SHiNE S11407,\r\n• French Agence Nationale de la Recherche (ANR), grants ANR-21-CE40-0020 (CONVERGENCE) and ANR-20-CE40-0002 (GrHyDy),\r\n• Fondation Mathématique Jaques Hadamard, grant PGMO RSG 2018-0031H,\r\n• European Research Council (ERC), Consolidator grant 863818 (ForM-SMArt),\r\n• Agencia Nacional de Investigación y Desarrollo (ANID Chile), grant ACT210005,\r\n• Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt Chile), grant 1220174,\r\n• Comisión Nacional de Investigación Científica y Tecnológica (CONICYT Chile), grant\r\nPII 20150140,\r\n• Evaluation-orientation de la Coopération Scientifique and Comisión Nacional de Investigación Científica y Tecnológica (ECOS-CONICYT), grant C15E03,\r\n• European Cooperation in Science and Technology (E-COST), grants CA16228 - European\r\nNetwork for Game Theory (GAMENET) and E-COST-GRANT-CA16228-c5a69859.\r\n","fulldoi":"https://doi.org/10.15479/AT-ISTA-20234","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2025-08-27T14:00:13Z","publisher":"Institute of Science and Technology Austria","file_date_updated":"2025-08-28T14:47:12Z","citation":{"short":"R.J. Saona Urmeneta, Robustness of Solutions in Game Theory: Values and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games, Institute of Science and Technology Austria, 2025.","chicago":"Saona Urmeneta, Raimundo J. “Robustness of Solutions in Game Theory: Values and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20234\">https://doi.org/10.15479/AT-ISTA-20234</a>.","ieee":"R. J. Saona Urmeneta, “Robustness of solutions in game theory: Values and strategies in partially observable, perturbed, stochastic, and infinite games,” Institute of Science and Technology Austria, 2025.","ama":"Saona Urmeneta RJ. Robustness of solutions in game theory: Values and strategies in partially observable, perturbed, stochastic, and infinite games. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20234\">10.15479/AT-ISTA-20234</a>","mla":"Saona Urmeneta, Raimundo J. <i>Robustness of Solutions in Game Theory: Values and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20234\">10.15479/AT-ISTA-20234</a>.","apa":"Saona Urmeneta, R. J. (2025). <i>Robustness of solutions in game theory: Values and strategies in partially observable, perturbed, stochastic, and infinite games</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20234\">https://doi.org/10.15479/AT-ISTA-20234</a>","ista":"Saona Urmeneta RJ. 2025. Robustness of solutions in game theory: Values and strategies in partially observable, perturbed, stochastic, and infinite games. Institute of Science and Technology Austria."},"oa":1,"corr_author":"1","status":"public","has_accepted_license":"1","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"OA_place":"publisher","project":[{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"related_material":{"record":[{"id":"9311","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"19508","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"17037"},{"relation":"part_of_dissertation","id":"18266","status":"public"}]},"doi":"10.15479/AT-ISTA-20234","file":[{"success":1,"file_id":"20240","access_level":"open_access","date_created":"2025-08-28T14:47:07Z","file_size":1503623,"relation":"main_file","content_type":"application/pdf","checksum":"394a651f7de7085e509ef856ffe7bd97","creator":"rsaonaur","date_updated":"2025-08-28T14:47:07Z","file_name":"2025_Saona_Raimundo_Thesis.pdf"},{"file_size":622747,"relation":"source_file","access_level":"closed","file_id":"20241","date_created":"2025-08-28T14:47:12Z","date_updated":"2025-08-28T14:47:12Z","file_name":"2025_Saona_Raimundo_Thesis.zip","content_type":"application/zip","creator":"rsaonaur","checksum":"09fb2633e66aac80433d373f4180c5b4"}],"ddc":["519"],"month":"08","language":[{"iso":"eng"}],"oa_version":"Published Version","degree_awarded":"PhD","type":"dissertation","date_published":"2025-08-27T00:00:00Z"},{"year":"2025","_id":"17037","publication_identifier":{"issn":["0364-765X"],"eissn":["1526-5471"]},"title":"Marginal values of a stochastic game","author":[{"full_name":"Attia, Luc","last_name":"Attia","first_name":"Luc"},{"last_name":"Oliu-Barton","full_name":"Oliu-Barton, Miquel","first_name":"Miquel"},{"full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","orcid":"0000-0001-5103-038X"}],"publication":"Mathematics of Operations Research","page":"482-505","abstract":[{"text":"Zero-sum stochastic games are parameterized by payoffs, transitions, and possibly a discount rate. In this article, we study how the main solution concepts, the discounted and undiscounted values, vary when these parameters are perturbed. We focus on the marginal values, introduced by Mills in 1956 in the context of matrix games—that is, the directional derivatives of the value along any fixed perturbation. We provide a formula for the marginal values of a discounted stochastic game. Further, under mild assumptions on the perturbation, we provide a formula for their limit as the discount rate vanishes and for the marginal values of an undiscounted stochastic game. We also show, via an example, that the two latter differ in general.","lang":"eng"}],"date_updated":"2026-10-02T11:29:44Z","day":"01","article_processing_charge":"No","publication_status":"published","ec_funded":1,"acknowledgement":"This work was supported by Fondation CFM pour la Recherche; the European Research Council [Grant ERC-CoG-863818 (ForM-SMArt)]; and Agence Nationale de la Recherche [Grant ANR-21-CE40-0020].","fulldoi":"https://doi.org/10.1287/moor.2023.0297","date_created":"2024-05-22T11:41:14Z","publisher":"Institute for Operations Research and the Management Sciences","isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_type":"original","issue":"1","das_tickbox":"0","researchdata_availability":"unclear","citation":{"short":"L. Attia, M. Oliu-Barton, R.J. Saona Urmeneta, Mathematics of Operations Research 50 (2025) 482–505.","chicago":"Attia, Luc, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta. “Marginal Values of a Stochastic Game.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2025. <a href=\"https://doi.org/10.1287/moor.2023.0297\">https://doi.org/10.1287/moor.2023.0297</a>.","ieee":"L. Attia, M. Oliu-Barton, and R. J. Saona Urmeneta, “Marginal values of a stochastic game,” <i>Mathematics of Operations Research</i>, vol. 50, no. 1. Institute for Operations Research and the Management Sciences, pp. 482–505, 2025.","ista":"Attia L, Oliu-Barton M, Saona Urmeneta RJ. 2025. Marginal values of a stochastic game. Mathematics of Operations Research. 50(1), 482–505.","mla":"Attia, Luc, et al. “Marginal Values of a Stochastic Game.” <i>Mathematics of Operations Research</i>, vol. 50, no. 1, Institute for Operations Research and the Management Sciences, 2025, pp. 482–505, doi:<a href=\"https://doi.org/10.1287/moor.2023.0297\">10.1287/moor.2023.0297</a>.","ama":"Attia L, Oliu-Barton M, Saona Urmeneta RJ. Marginal values of a stochastic game. <i>Mathematics of Operations Research</i>. 2025;50(1):482-505. doi:<a href=\"https://doi.org/10.1287/moor.2023.0297\">10.1287/moor.2023.0297</a>","apa":"Attia, L., Oliu-Barton, M., &#38; Saona Urmeneta, R. J. (2025). Marginal values of a stochastic game. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2023.0297\">https://doi.org/10.1287/moor.2023.0297</a>"},"supplementarymaterial":"unclear","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"status":"public","related_material":{"record":[{"relation":"dissertation_contains","id":"20234","status":"public"}]},"doi":"10.1287/moor.2023.0297","scopus_import":"1","quality_controlled":"1","OA_type":"closed access","month":"02","language":[{"iso":"eng"}],"volume":50,"external_id":{"isi":["001184648000001"]},"date_published":"2025-02-01T00:00:00Z","type":"journal_article","intvolume":"        50","oa_version":"None"},{"citation":{"short":"K. Chatterjee, J.P. Katoen, S. Mohr, M. Weininger, T. Winkler, Formal Methods in System Design 63 (2024) 40–80.","chicago":"Chatterjee, Krishnendu, Joost P Katoen, Stefanie Mohr, Maximilian Weininger, and Tobias Winkler. “Stochastic Games with Lexicographic Objectives.” <i>Formal Methods in System Design</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s10703-023-00411-4\">https://doi.org/10.1007/s10703-023-00411-4</a>.","mla":"Chatterjee, Krishnendu, et al. “Stochastic Games with Lexicographic Objectives.” <i>Formal Methods in System Design</i>, vol. 63, Springer Nature, 2024, pp. 40–80, doi:<a href=\"https://doi.org/10.1007/s10703-023-00411-4\">10.1007/s10703-023-00411-4</a>.","ama":"Chatterjee K, Katoen JP, Mohr S, Weininger M, Winkler T. Stochastic games with lexicographic objectives. <i>Formal Methods in System Design</i>. 2024;63:40-80. doi:<a href=\"https://doi.org/10.1007/s10703-023-00411-4\">10.1007/s10703-023-00411-4</a>","apa":"Chatterjee, K., Katoen, J. P., Mohr, S., Weininger, M., &#38; Winkler, T. (2024). Stochastic games with lexicographic objectives. <i>Formal Methods in System Design</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10703-023-00411-4\">https://doi.org/10.1007/s10703-023-00411-4</a>","ista":"Chatterjee K, Katoen JP, Mohr S, Weininger M, Winkler T. 2024. Stochastic games with lexicographic objectives. Formal Methods in System Design. 63, 40–80.","ieee":"K. Chatterjee, J. P. Katoen, S. Mohr, M. Weininger, and T. Winkler, “Stochastic games with lexicographic objectives,” <i>Formal Methods in System Design</i>, vol. 63. Springer Nature, pp. 40–80, 2024."},"file_date_updated":"2025-01-09T07:31:31Z","oa":1,"article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"publisher":"Springer Nature","date_created":"2023-03-19T23:00:59Z","fulldoi":"https://doi.org/10.1007/s10703-023-00411-4","acknowledgement":"Tobias Winkler and Joost-Pieter Katoen are supported by the DFG RTG 2236 UnRAVeL and the innovation programme under the Marie Skłodowska-Curie grant agreement No. 101008233 (Mission). Krishnendu Chatterjee is supported by the ERC CoG 863818 (ForM-SMArt) and the Vienna Science and Technology Fund (WWTF) Project ICT15-003. Maximilian Weininger is supported by the DFG projects 383882557 Statistical Unbounded Verification (SUV) and 427755713 Group-By Objectives in Probabilistic Verification (GOPro). Stefanie Mohr is supported by the DFG RTG 2428 CONVEY. Open Access funding enabled and organized by Projekt DEAL.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ec_funded":1,"publication_status":"published","day":"01","article_processing_charge":"Yes (via OA deal)","date_updated":"2026-04-16T09:31:13Z","abstract":[{"lang":"eng","text":"We study turn-based stochastic zero-sum games with lexicographic preferences over objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as controllable and adversarial non-determinism. Lexicographic order allows one to consider multiple objectives with a strict preference order. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. For a mixture of reachability and safety objectives, we show that deterministic lexicographically optimal strategies exist and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP, matching the current known bound for single objectives; and in general the decision problem is PSPACE-hard and can be solved in NEXPTIME∩coNEXPTIME. We present an algorithm that computes the lexicographically optimal strategies via a reduction to the computation of optimal strategies in a sequence of single-objectives games. For omega-regular objectives, we restrict our analysis to one-player games, also known as Markov decision processes. We show that lexicographically optimal strategies exist and need either randomization or finite memory. We present an algorithm that solves the relevant decision problem in polynomial time. We have implemented our algorithms and report experimental results on various case studies."}],"page":"40-80","title":"Stochastic games with lexicographic objectives","publication":"Formal Methods in System Design","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"Katoen, Joost P","last_name":"Katoen","orcid":"0000-0002-6143-1926","first_name":"Joost P","id":"4524F760-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stefanie","full_name":"Mohr, Stefanie","last_name":"Mohr"},{"first_name":"Maximilian","full_name":"Weininger, Maximilian","last_name":"Weininger"},{"first_name":"Tobias","last_name":"Winkler","full_name":"Winkler, Tobias"}],"publication_identifier":{"eissn":["1572-8102"]},"_id":"12738","year":"2024","oa_version":"Published Version","intvolume":"        63","type":"journal_article","date_published":"2024-10-01T00:00:00Z","external_id":{"isi":["000946174300001"]},"volume":63,"language":[{"iso":"eng"}],"month":"10","ddc":["000"],"OA_type":"hybrid","file":[{"date_created":"2025-01-09T07:31:31Z","access_level":"open_access","file_id":"18781","success":1,"relation":"main_file","file_size":2614190,"creator":"dernst","checksum":"111e76b76163640a2c89237642af586f","content_type":"application/pdf","file_name":"2024_FromMethodsSys_Chatterjee.pdf","date_updated":"2025-01-09T07:31:31Z"}],"quality_controlled":"1","scopus_import":"1","doi":"10.1007/s10703-023-00411-4","related_material":{"record":[{"status":"public","id":"8272","relation":"earlier_version"}]},"status":"public","has_accepted_license":"1","OA_place":"publisher","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"}],"department":[{"_id":"KrCh"}]},{"doi":"10.1016/j.tcs.2023.114353","related_material":{"record":[{"relation":"earlier_version","id":"19985","status":"public"}]},"scopus_import":"1","corr_author":"1","has_accepted_license":"1","status":"public","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"external_id":{"isi":["001168211400001"]},"volume":989,"keyword":["General Computer Science","Theoretical Computer Science"],"language":[{"iso":"eng"}],"oa_version":"Published Version","intvolume":"       989","type":"journal_article","date_published":"2024-03-21T00:00:00Z","ddc":["000"],"file":[{"relation":"main_file","file_size":603570,"date_created":"2024-07-16T12:02:25Z","access_level":"open_access","file_id":"17263","success":1,"file_name":"2024_TheorComputerScience_Schmid.pdf","date_updated":"2024-07-16T12:02:25Z","creator":"dernst","checksum":"efd5b7e738bf845312ba53889a3e13e4","content_type":"application/pdf"}],"quality_controlled":"1","month":"03","date_updated":"2025-12-02T14:02:37Z","ec_funded":1,"publication_status":"published","day":"21","article_processing_charge":"Yes (via OA deal)","publication_identifier":{"issn":["0304-3975"]},"_id":"14820","year":"2024","abstract":[{"lang":"eng","text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on \r\n increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3)  for some arbitrary E>0."}],"publication":"Theoretical Computer Science","author":[{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"full_name":"Svoboda, Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809","last_name":"Yeo","full_name":"Yeo, Michelle X"}],"title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","article_type":"original","citation":{"chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>.","short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>, vol. 989, 114353, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. 2024;989. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>","apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” <i>Theoretical Computer Science</i>, vol. 989. Elsevier, 2024."},"file_date_updated":"2024-07-16T12:02:25Z","article_number":"114353","oa":1,"acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021-2024.","fulldoi":"https://doi.org/10.1016/j.tcs.2023.114353","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"publisher":"Elsevier","date_created":"2024-01-16T13:40:41Z"},{"doi":"10.4230/LIPIcs.OPODIS.2023.11","scopus_import":"1","corr_author":"1","has_accepted_license":"1","status":"public","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"department":[{"_id":"KrCh"}],"external_id":{"isi":["001585185800011"],"arxiv":["2102.13457"]},"volume":286,"language":[{"iso":"eng"}],"oa_version":"Published Version","intvolume":"       286","date_published":"2024-01-18T00:00:00Z","type":"conference","ddc":["000"],"file":[{"content_type":"application/pdf","checksum":"4fc7eea6e4ba140b904781fc7df868ec","creator":"dernst","date_updated":"2024-02-26T09:04:58Z","file_name":"2024_LIPICs_Hirvonen.pdf","success":1,"file_id":"15028","access_level":"open_access","date_created":"2024-02-26T09:04:58Z","file_size":867363,"relation":"main_file"}],"quality_controlled":"1","month":"01","arxiv":1,"date_updated":"2025-12-02T13:38:16Z","ec_funded":1,"publication_status":"published","article_processing_charge":"No","day":"18","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773089"]},"_id":"15006","conference":{"end_date":"2023-12-08","start_date":"2023-12-06","location":"Tokyo, Japan","name":"OPODIS: Conference on Principles of Distributed Systems"},"year":"2024","alternative_title":["LIPIcs"],"abstract":[{"lang":"eng","text":"Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of \"natural\" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of \"time-constrained\" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood."}],"title":"On the convergence time in graphical games: A locality-sensitive approach","publication":"27th International Conference on Principles of Distributed Systems","author":[{"first_name":"Juho","full_name":"Hirvonen, Juho","last_name":"Hirvonen"},{"orcid":"0000-0002-6978-7329","id":"38B437DE-F248-11E8-B48F-1D18A9856A87","first_name":"Laura","full_name":"Schmid, Laura","last_name":"Schmid"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"}],"citation":{"chicago":"Hirvonen, Juho, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>.","short":"J. Hirvonen, L. Schmid, K. Chatterjee, S. Schmid, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. 2024. On the convergence time in graphical games: A locality-sensitive approach. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 11.","ama":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. On the convergence time in graphical games: A locality-sensitive approach. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>","mla":"Hirvonen, Juho, et al. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>.","apa":"Hirvonen, J., Schmid, L., Chatterjee, K., &#38; Schmid, S. (2024). On the convergence time in graphical games: A locality-sensitive approach. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>","ieee":"J. Hirvonen, L. Schmid, K. Chatterjee, and S. Schmid, “On the convergence time in graphical games: A locality-sensitive approach,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286."},"file_date_updated":"2024-02-26T09:04:58Z","article_number":"11","oa":1,"fulldoi":"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11","acknowledgement":"This work was partially funded by the Academy of Finland, grant 314888, the European Research Council CoG 863818 (ForM-SMArt), and the Austrian Science Fund (FWF) project I 4800-N (ADVISE). LS was supported by the Stochastic Analysis and Application Research Center (SAARC) under National Research Foundation of Korea grant NRF-2019R1A5A1028324.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2024-02-18T23:01:01Z"},{"day":"09","article_processing_charge":"No","date_updated":"2025-09-04T12:14:54Z","doi":"10.5281/ZENODO.10639167","related_material":{"record":[{"status":"public","id":"15083","relation":"used_in_publication"}]},"title":"Computer code for \"Efficiency and resilience of cooperation in asymmetric social dilemmas\"","author":[{"last_name":"Hübner","full_name":"Hübner, Valentin","orcid":"0009-0001-5009-4987","first_name":"Valentin","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910"},{"first_name":"Maria","full_name":"Kleshnina, Maria","last_name":"Kleshnina"}],"department":[{"_id":"KrCh"}],"status":"public","abstract":[{"lang":"eng","text":"in the research article \"Efficiency and resilience of cooperation in asymmetric social dilemmas\" (by Valentin Hübner, Manuel Staab, Christian Hilbe, Krishnendu Chatterjee, and Maria Kleshnina).\r\n\r\nWe used different implementations for the case of two and three players, both described below."}],"has_accepted_license":"1","_id":"15108","year":"2024","corr_author":"1","type":"research_data_reference","date_published":"2024-02-09T00:00:00Z","oa":1,"citation":{"ista":"Hübner V, Kleshnina M. 2024. Computer code for ‘Efficiency and resilience of cooperation in asymmetric social dilemmas’, Zenodo, <a href=\"https://doi.org/10.5281/ZENODO.10639167\">10.5281/ZENODO.10639167</a>.","ama":"Hübner V, Kleshnina M. Computer code for “Efficiency and resilience of cooperation in asymmetric social dilemmas.” 2024. doi:<a href=\"https://doi.org/10.5281/ZENODO.10639167\">10.5281/ZENODO.10639167</a>","apa":"Hübner, V., &#38; Kleshnina, M. (2024). Computer code for “Efficiency and resilience of cooperation in asymmetric social dilemmas.” Zenodo. <a href=\"https://doi.org/10.5281/ZENODO.10639167\">https://doi.org/10.5281/ZENODO.10639167</a>","mla":"Hübner, Valentin, and Maria Kleshnina. <i>Computer Code for “Efficiency and Resilience of Cooperation in Asymmetric Social Dilemmas.”</i> Zenodo, 2024, doi:<a href=\"https://doi.org/10.5281/ZENODO.10639167\">10.5281/ZENODO.10639167</a>.","ieee":"V. Hübner and M. Kleshnina, “Computer code for ‘Efficiency and resilience of cooperation in asymmetric social dilemmas.’” Zenodo, 2024.","short":"V. Hübner, M. Kleshnina, (2024).","chicago":"Hübner, Valentin, and Maria Kleshnina. “Computer Code for ‘Efficiency and Resilience of Cooperation in Asymmetric Social Dilemmas.’” Zenodo, 2024. <a href=\"https://doi.org/10.5281/ZENODO.10639167\">https://doi.org/10.5281/ZENODO.10639167</a>."},"oa_version":"Published Version","publisher":"Zenodo","month":"02","date_created":"2024-03-12T13:02:58Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"main_file_link":[{"url":"https://10.5281/zenodo.10639167","open_access":"1"}],"fulldoi":"https://doi.org/10.5281/ZENODO.10639167","ddc":["000"]},{"abstract":[{"lang":"eng","text":"Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are infinite walks on the graph where the next vertex is decided by a player that owns the current vertex. Each edge is assigned an integer weight and the payoff of a play is the discounted-sum of the weights of the play. The goal of player 1 is to maximize the discounted-sum payoff against the adversarial player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class and the existence of a polynomial-time algorithm is a major open question. Since breaking the general exponential barrier has been a challenging problem, faster parameterized algorithms have been considered. If the discount factor is expressed in unary, then discounted-sum games can be solved in polynomial time. However, if the discount factor is arbitrary (or expressed in binary), but the weights are in unary, none of the existing approaches yield a sub-exponential bound. Our main result is a new analysis technique for a classical algorithm (namely, the strategy iteration algorithm) that present a new runtime bound which is [EQUATION] for game graphs with n vertices and absolute weights of at most W. In particular, our result yields a deterministic sub-exponential bound for games with weights that are constant or represented in unary."}],"publication":"39th Annual ACM/IEEE Symposium on Logic in Computer Science","title":"Deterministic sub-exponential algorithm for discounted-sum games with unary weights","author":[{"first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","full_name":"Asadi, Ali","last_name":"Asadi"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda"},{"full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J"}],"publication_identifier":{"eissn":["1043-6871"],"isbn":["9798400706608"]},"_id":"17098","year":"2024","conference":{"location":"Tallinn, Estonia","name":"LICS: Logic in Computer Science","start_date":"2024-07-08","end_date":"2024-07-11"},"ec_funded":1,"day":"08","article_processing_charge":"No","publication_status":"published","arxiv":1,"date_updated":"2025-09-08T07:44:29Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2024-06-03T07:43:15Z","publisher":"Association for Computing Machinery","isi":1,"fulldoi":"https://doi.org/10.1145/3661814.3662080","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.\r\n","citation":{"chicago":"Asadi, Ali, Krishnendu Chatterjee, Jakub Svoboda, and Raimundo J Saona Urmeneta. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” In <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3661814.3662080\">https://doi.org/10.1145/3661814.3662080</a>.","short":"A. Asadi, K. Chatterjee, J. Svoboda, R.J. Saona Urmeneta, in:, 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Association for Computing Machinery, 2024.","ieee":"A. Asadi, K. Chatterjee, J. Svoboda, and R. J. Saona Urmeneta, “Deterministic sub-exponential algorithm for discounted-sum games with unary weights,” in <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Tallinn, Estonia, 2024.","mla":"Asadi, Ali, et al. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 6, Association for Computing Machinery, 2024, doi:<a href=\"https://doi.org/10.1145/3661814.3662080\">10.1145/3661814.3662080</a>.","apa":"Asadi, A., Chatterjee, K., Svoboda, J., &#38; Saona Urmeneta, R. J. (2024). Deterministic sub-exponential algorithm for discounted-sum games with unary weights. In <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Tallinn, Estonia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3661814.3662080\">https://doi.org/10.1145/3661814.3662080</a>","ama":"Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. In: <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Association for Computing Machinery; 2024. doi:<a href=\"https://doi.org/10.1145/3661814.3662080\">10.1145/3661814.3662080</a>","ista":"Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. 2024. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. 39th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6."},"oa":1,"article_number":"6","status":"public","department":[{"_id":"KrCh"}],"project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"corr_author":"1","scopus_import":"1","doi":"10.1145/3661814.3662080","month":"07","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2405.02479"}],"quality_controlled":"1","oa_version":"Preprint","type":"conference","date_published":"2024-07-08T00:00:00Z","language":[{"iso":"eng"}],"external_id":{"isi":["001275042100006"],"arxiv":["2405.02479"]}},{"intvolume":"       323","date_published":"2024-12-05T00:00:00Z","type":"conference","oa_version":"Published Version","external_id":{"isi":["001537516500005"],"arxiv":["2405.02486"]},"volume":323,"language":[{"iso":"eng"}],"month":"12","quality_controlled":"1","ddc":["000"],"OA_type":"gold","file":[{"content_type":"application/pdf","checksum":"5b544ab4692b93300b404435c036ddd4","creator":"dernst","date_updated":"2025-01-08T09:49:31Z","file_name":"2024_LIPIcs_Asadi.pdf","file_id":"18777","success":1,"access_level":"open_access","date_created":"2025-01-08T09:49:31Z","file_size":847960,"relation":"main_file"}],"scopus_import":"1","doi":"10.4230/LIPIcs.FSTTCS.2024.5","OA_place":"publisher","project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"department":[{"_id":"KrCh"}],"has_accepted_license":"1","status":"public","corr_author":"1","article_number":"5","oa":1,"citation":{"ieee":"A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms,” in <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Gujarat, India, 2024, vol. 323.","ama":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In: <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>","apa":"Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Svoboda, J. (2024). Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 323). Gujarat, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>","mla":"Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>.","ista":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 323, 5.","short":"A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>."},"file_date_updated":"2025-01-08T09:49:31Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","isi":1,"date_created":"2024-06-03T07:44:27Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"fulldoi":"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5","acknowledgement":"This research was partially supported by ERC CoG 863818 (ForM-SMArt), Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)","publication_status":"published","day":"05","article_processing_charge":"No","ec_funded":1,"date_updated":"2025-12-02T13:40:52Z","arxiv":1,"author":[{"first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","full_name":"Asadi, Ali","last_name":"Asadi"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"orcid":"0000-0001-5103-038X","first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J"},{"full_name":"Svoboda, Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"}],"publication":"44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","title":"Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms","abstract":[{"text":"We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order.\r\nThe computational problem we consider is the approximation of the value within an arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time.","lang":"eng"}],"conference":{"name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","location":"Gujarat, India","end_date":"2024-12-18","start_date":"2024-12-16"},"_id":"17099","year":"2024","alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773553"]}},{"publication":"arXiv","title":"Zero-sum random games on directed graphs","author":[{"first_name":"Luc","full_name":"Attia, Luc","last_name":"Attia"},{"first_name":"Lyuben","full_name":"Lichev, Lyuben","last_name":"Lichev"},{"first_name":"Dieter","full_name":"Mitsche, Dieter","last_name":"Mitsche"},{"last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"full_name":"Ziliotto, Bruno","last_name":"Ziliotto","first_name":"Bruno"}],"department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"This paper considers a class of two-player zero-sum games on directed graphs whose vertices are equipped with random payoffs of bounded support known by both players.\r\nStarting from a fixed vertex, players take turns to move a token along the edges of the graph.\r\nOn the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that the value of the game converges almost surely to a constant at an exponential rate dominated in terms of the expansion.\r\nOn the other hand, for the infinite d-ary tree that does not fall into the previous class of graphs, we show convergence at a double-exponential rate in terms of the expansion."}],"status":"public","year":"2024","_id":"17101","publication_status":"submitted","day":"29","article_processing_charge":"No","arxiv":1,"doi":"10.48550/arXiv.2401.16252","date_updated":"2024-06-03T07:50:29Z","month":"01","date_created":"2024-06-03T07:45:22Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2401.16252","open_access":"1"}],"acknowledgement":"This work was supported by the French Agence Nationale de la Recherche (ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002 (GrHyDy), and by Fondecyt grant 1220174. This collaboration was mainly conducted during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at University of Chile in 2023,\r\nunder the IRL program of CNRS.","fulldoi":"https://doi.org/10.48550/arXiv.2401.16252","article_number":"2401.16252","date_published":"2024-01-29T00:00:00Z","type":"preprint","oa":1,"oa_version":"Preprint","citation":{"chicago":"Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Zero-Sum Random Games on Directed Graphs.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2401.16252\">https://doi.org/10.48550/arXiv.2401.16252</a>.","short":"L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, ArXiv (n.d.).","ista":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random games on directed graphs. arXiv, 2401.16252.","ama":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random games on directed graphs. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2401.16252\">10.48550/arXiv.2401.16252</a>","apa":"Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., &#38; Ziliotto, B. (n.d.). Zero-sum random games on directed graphs. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2401.16252\">https://doi.org/10.48550/arXiv.2401.16252</a>","mla":"Attia, Luc, et al. “Zero-Sum Random Games on Directed Graphs.” <i>ArXiv</i>, 2401.16252, doi:<a href=\"https://doi.org/10.48550/arXiv.2401.16252\">10.48550/arXiv.2401.16252</a>.","ieee":"L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Zero-sum random games on directed graphs,” <i>arXiv</i>. ."},"external_id":{"arxiv":["2401.16252"]},"language":[{"iso":"eng"}]},{"month":"04","ddc":["000"],"file":[{"content_type":"application/pdf","creator":"dernst","checksum":"9243ded966f71df1572be5466019be5c","date_updated":"2024-06-27T07:48:16Z","file_name":"2024_ProcACMProgLanguage_Chatterjee.pdf","access_level":"open_access","success":1,"file_id":"17182","date_created":"2024-06-27T07:48:16Z","file_size":413096,"relation":"main_file"}],"quality_controlled":"1","oa_version":"Published Version","intvolume":"         8","date_published":"2024-04-29T00:00:00Z","type":"journal_article","volume":8,"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"department":[{"_id":"KrCh"}],"scopus_import":"1","doi":"10.1145/3649824","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Association for Computing Machinery","date_created":"2024-06-23T22:01:02Z","fulldoi":"https://doi.org/10.1145/3649824","acknowledgement":"This work was supported in part by the European Research Council (ERC) under Grant No. 863818\r\n(ForM-SMArt) and the Hong Kong Research Grants Council under ECS Project No. 26208122.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Tobias Meggendorfer, and Dorde Zikelic. “Quantitative Bounds on Resource Usage of Probabilistic Programs.” <i>Proceedings of the ACM on Programming Languages</i>. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3649824\">https://doi.org/10.1145/3649824</a>.","short":"K. Chatterjee, A.K. Goharshady, T. Meggendorfer, D. Zikelic, Proceedings of the ACM on Programming Languages 8 (2024).","mla":"Chatterjee, Krishnendu, et al. “Quantitative Bounds on Resource Usage of Probabilistic Programs.” <i>Proceedings of the ACM on Programming Languages</i>, vol. 8, no. OOPSLA1, 107, Association for Computing Machinery, 2024, doi:<a href=\"https://doi.org/10.1145/3649824\">10.1145/3649824</a>.","ama":"Chatterjee K, Goharshady AK, Meggendorfer T, Zikelic D. Quantitative bounds on resource usage of probabilistic programs. <i>Proceedings of the ACM on Programming Languages</i>. 2024;8(OOPSLA1). doi:<a href=\"https://doi.org/10.1145/3649824\">10.1145/3649824</a>","apa":"Chatterjee, K., Goharshady, A. K., Meggendorfer, T., &#38; Zikelic, D. (2024). Quantitative bounds on resource usage of probabilistic programs. <i>Proceedings of the ACM on Programming Languages</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3649824\">https://doi.org/10.1145/3649824</a>","ista":"Chatterjee K, Goharshady AK, Meggendorfer T, Zikelic D. 2024. Quantitative bounds on resource usage of probabilistic programs. Proceedings of the ACM on Programming Languages. 8(OOPSLA1), 107.","ieee":"K. Chatterjee, A. K. Goharshady, T. Meggendorfer, and D. Zikelic, “Quantitative bounds on resource usage of probabilistic programs,” <i>Proceedings of the ACM on Programming Languages</i>, vol. 8, no. OOPSLA1. Association for Computing Machinery, 2024."},"file_date_updated":"2024-06-27T07:48:16Z","article_number":"107","oa":1,"issue":"OOPSLA1","article_type":"original","abstract":[{"text":"Cost analysis, also known as resource usage analysis, is the task of finding bounds on the total cost of a program and is a well-studied problem in static analysis. In this work, we consider two classical quantitative problems in cost analysis for probabilistic programs. The first problem is to find a bound on the expected total cost of the program. This is a natural measure for the resource usage of the program and can also be directly applied to average-case runtime analysis. The second problem asks for a tail bound, i.e. ‍given a threshold t the goal is to find a probability bound p such that ℙ[total cost ≥ t] ≤ p. Intuitively, given a threshold t on the resource, the problem is to find the likelihood that the total cost exceeds this threshold.\r\nFirst, for expectation bounds, a major obstacle in previous works on cost analysis is that they can handle only non-negative costs or bounded variable updates. In contrast, we provide a new variant of the standard notion of cost martingales, that allows us to find expectation bounds for a class of programs with general positive or negative costs and no restriction on the variable updates. More specifically, our approach is applicable as long as there is a lower bound on the total cost incurred along every path.\r\nSecond, for tail bounds, all previous methods are limited to programs in which the expected total cost is finite. In contrast, we present a novel approach, based on a combination of our martingale-based method for expectation bounds with a quantitative safety analysis, to obtain a solution to the tail bound problem that is applicable even to programs with infinite expected cost. Specifically, this allows us to obtain runtime tail bounds for programs that do not terminate almost-surely.\r\nIn summary, we provide a novel combination of martingale-based cost analysis and quantitative safety analysis that is able to find expectation and tail cost bounds for probabilistic programs, without the restrictions of non-negative costs, bounded updates, or finiteness of the expected total cost. Finally, we provide experimental results showcasing that our approach can solve instances that were beyond the reach of previous methods.","lang":"eng"}],"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir Kafshdar","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir Kafshdar","last_name":"Goharshady"},{"last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","orcid":"0000-0002-1712-2165"},{"orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","first_name":"Dorde","last_name":"Zikelic","full_name":"Zikelic, Dorde"}],"title":"Quantitative bounds on resource usage of probabilistic programs","publication":"Proceedings of the ACM on Programming Languages","publication_identifier":{"eissn":["2475-1421"]},"_id":"17162","year":"2024","ec_funded":1,"publication_status":"published","article_processing_charge":"Yes (in subscription journal)","day":"29","date_updated":"2025-04-14T07:52:47Z"},{"citation":{"ista":"Andriushchenko R, Bork A, Budde CE, Češka M, Grover K, Hahn EM, Hartmanns A, Israelsen B, Jansen N, Jeppson J, Junges S, Köhl MA, Könighofer B, Kretinsky J, Meggendorfer T, Parker D, Pranger S, Quatmann T, Ruijters E, Taylor L, Volk M, Weininger M, Zhang Z. 2024. Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report. TOOLympics Challenge 2023. , LNCS, vol. 14550, 90–146.","mla":"Andriushchenko, Roman, et al. “Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report.” <i>TOOLympics Challenge 2023</i>, vol. 14550, Springer Nature, 2024, pp. 90–146, doi:<a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">10.1007/978-3-031-67695-6_4</a>.","ama":"Andriushchenko R, Bork A, Budde CE, et al. Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report. In: <i>TOOLympics Challenge 2023</i>. Vol 14550. Springer Nature; 2024:90-146. doi:<a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">10.1007/978-3-031-67695-6_4</a>","apa":"Andriushchenko, R., Bork, A., Budde, C. E., Češka, M., Grover, K., Hahn, E. M., … Zhang, Z. (2024). Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report. In <i>TOOLympics Challenge 2023</i> (Vol. 14550, pp. 90–146). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">https://doi.org/10.1007/978-3-031-67695-6_4</a>","ieee":"R. Andriushchenko <i>et al.</i>, “Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report,” in <i>TOOLympics Challenge 2023</i>, 2024, vol. 14550, pp. 90–146.","chicago":"Andriushchenko, Roman, Alexander Bork, Carlos E. Budde, Milan Češka, Kush Grover, Ernst Moritz Hahn, Arnd Hartmanns, et al. “Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report.” In <i>TOOLympics Challenge 2023</i>, 14550:90–146. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">https://doi.org/10.1007/978-3-031-67695-6_4</a>.","short":"R. Andriushchenko, A. Bork, C.E. Budde, M. Češka, K. Grover, E.M. Hahn, A. Hartmanns, B. Israelsen, N. Jansen, J. Jeppson, S. Junges, M.A. Köhl, B. Könighofer, J. Kretinsky, T. Meggendorfer, D. Parker, S. Pranger, T. Quatmann, E. Ruijters, L. Taylor, M. Volk, M. Weininger, Z. Zhang, in:, TOOLympics Challenge 2023, Springer Nature, 2024, pp. 90–146."},"oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"publisher":"Springer Nature","date_created":"2024-12-01T23:01:53Z","acknowledgement":"The authors are ordered alphabetically. This work was supported by DFG RTG 2236/2 (UnRAVeL) and DFG project TRR 248 (CPEC, ID 389792660), by the EU under MSCA grant agreements 101008233 (MISSION), 101034413 (IST-BRIDGE), and 101067199 (ProSVED), by ERC Starting Grant 101077178 (DEUCE), ERC Consolidator Grant 864075 (CAESAR), and ERC Advanced Grant 834115 (FUN2MODEL), by GAČR grant GA23-06963S (VESCAA), by National Science Foundation grant 1856733, by NextGenerationEU project D53D23008400006 (SMARTITUDE), and by NWO VENI grant 639.021.754.","fulldoi":"https://doi.org/10.1007/978-3-031-67695-6_4","publication_status":"published","day":"01","article_processing_charge":"No","date_updated":"2025-09-08T14:45:11Z","arxiv":1,"abstract":[{"lang":"eng","text":"The analysis of formal models that include quantitative aspects such as timing or probabilistic choices is performed by quantitative verification tools. Broad and mature tool support is available for computing basic properties such as expected rewards on basic models such as Markov chains. Previous editions of QComp, the comparison of tools for the analysis of quantitative formal models, focused on this setting. Many application scenarios, however, require more advanced property types such as LTL and parameter synthesis queries as well as advanced models like stochastic games and partially observable MDPs. For these, tool support is in its infancy today. This paper presents the outcomes of QComp 2023: a survey of the state of the art in quantitative verification tool support for advanced property types and models. With tools ranging from first research prototypes to well-supported integrations into established toolsets, this report highlights today’s active areas and tomorrow’s challenges in tool-focused research for quantitative verification."}],"page":"90-146","publication":"TOOLympics Challenge 2023","author":[{"first_name":"Roman","last_name":"Andriushchenko","full_name":"Andriushchenko, Roman"},{"first_name":"Alexander","full_name":"Bork, Alexander","last_name":"Bork"},{"last_name":"Budde","full_name":"Budde, Carlos E.","first_name":"Carlos E."},{"full_name":"Češka, Milan","last_name":"Češka","first_name":"Milan"},{"last_name":"Grover","full_name":"Grover, Kush","first_name":"Kush"},{"first_name":"Ernst Moritz","full_name":"Hahn, Ernst Moritz","last_name":"Hahn"},{"first_name":"Arnd","full_name":"Hartmanns, Arnd","last_name":"Hartmanns"},{"first_name":"Bryant","full_name":"Israelsen, Bryant","last_name":"Israelsen"},{"last_name":"Jansen","full_name":"Jansen, Nils","first_name":"Nils"},{"first_name":"Joshua","full_name":"Jeppson, Joshua","last_name":"Jeppson"},{"last_name":"Junges","full_name":"Junges, Sebastian","first_name":"Sebastian"},{"first_name":"Maximilian A.","last_name":"Köhl","full_name":"Köhl, Maximilian A."},{"first_name":"Bettina","last_name":"Könighofer","full_name":"Könighofer, Bettina"},{"last_name":"Kretinsky","full_name":"Kretinsky, Jan","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"},{"full_name":"Meggendorfer, Tobias","last_name":"Meggendorfer","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","orcid":"0000-0002-1712-2165"},{"full_name":"Parker, David","last_name":"Parker","first_name":"David"},{"first_name":"Stefan","last_name":"Pranger","full_name":"Pranger, Stefan"},{"full_name":"Quatmann, Tim","last_name":"Quatmann","first_name":"Tim"},{"full_name":"Ruijters, Enno","last_name":"Ruijters","first_name":"Enno"},{"first_name":"Landon","last_name":"Taylor","full_name":"Taylor, Landon"},{"full_name":"Volk, Matthias","last_name":"Volk","first_name":"Matthias"},{"full_name":"Weininger, Maximilian","last_name":"Weininger","id":"02ab0197-cc70-11ed-ab61-918e71f56881","first_name":"Maximilian"},{"full_name":"Zhang, Zhen","last_name":"Zhang","first_name":"Zhen"}],"title":"Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031676949"]},"_id":"18600","year":"2024","alternative_title":["LNCS"],"oa_version":"Preprint","intvolume":"     14550","date_published":"2024-11-01T00:00:00Z","type":"conference","external_id":{"isi":["001434957500004"],"arxiv":["2405.13583"]},"volume":14550,"language":[{"iso":"eng"}],"month":"11","OA_type":"green","quality_controlled":"1","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2405.13583"}],"scopus_import":"1","doi":"10.1007/978-3-031-67695-6_4","status":"public","OA_place":"repository","department":[{"_id":"KrCh"}]},{"month":"05","main_file_link":[{"open_access":"1","url":"https://schmiste.github.io/noms24.pdf"}],"quality_controlled":"1","OA_type":"green","type":"conference","date_published":"2024-05-01T00:00:00Z","oa_version":"Submitted Version","language":[{"iso":"eng"}],"external_id":{"isi":["001270140300143"]},"department":[{"_id":"KrCh"}],"OA_place":"other","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"},{"_id":"bd622a5c-d553-11ed-ba76-bae280ba8aff","grant_number":"894907","name":"Graphical Games"}],"status":"public","corr_author":"1","scopus_import":"1","doi":"10.1109/noms59830.2024.10575579","date_created":"2025-01-27T15:06:45Z","isi":1,"publisher":"IEEE","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Research was supported by the Austrian Science Fund (FWF), project I 5025-N (DELTA), 2020-2024. Esra Ceylan’s research was supported by FFG, FEMtech Praktika für Studentinnen. Jakub Svoboda and Krishnendu Chatterjee were supported by the European Research Council (ERC) CoG 863818 (ForM-SMArt).","fulldoi":"https://doi.org/10.1109/noms59830.2024.10575579","oa":1,"citation":{"ista":"Ceylan E, Chatterjee K, Schmid S, Svoboda J. 2024. Congestion-free rerouting of network flows: Hardness and an FPT algorithm. NOMS 2024-2024 IEEE Network Operations and Management Symposium. NOMS: Network Operations and Management Symposiu .","mla":"Ceylan, Esra, et al. “Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>, IEEE, 2024, doi:<a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">10.1109/noms59830.2024.10575579</a>.","apa":"Ceylan, E., Chatterjee, K., Schmid, S., &#38; Svoboda, J. (2024). Congestion-free rerouting of network flows: Hardness and an FPT algorithm. In <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. Seoul, Republic of Korea: IEEE. <a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">https://doi.org/10.1109/noms59830.2024.10575579</a>","ama":"Ceylan E, Chatterjee K, Schmid S, Svoboda J. Congestion-free rerouting of network flows: Hardness and an FPT algorithm. In: <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. IEEE; 2024. doi:<a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">10.1109/noms59830.2024.10575579</a>","ieee":"E. Ceylan, K. Chatterjee, S. Schmid, and J. Svoboda, “Congestion-free rerouting of network flows: Hardness and an FPT algorithm,” in <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>, Seoul, Republic of Korea, 2024.","chicago":"Ceylan, Esra, Krishnendu Chatterjee, Stefan Schmid, and Jakub Svoboda. “Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” In <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. IEEE, 2024. <a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">https://doi.org/10.1109/noms59830.2024.10575579</a>.","short":"E. Ceylan, K. Chatterjee, S. Schmid, J. Svoboda, in:, NOMS 2024-2024 IEEE Network Operations and Management Symposium, IEEE, 2024."},"publication":"NOMS 2024-2024 IEEE Network Operations and Management Symposium","title":"Congestion-free rerouting of network flows: Hardness and an FPT algorithm","author":[{"full_name":"Ceylan, Esra","last_name":"Ceylan","id":"cb1ca1d8-dcc0-11ef-baa5-9f1b3ef75933","first_name":"Esra"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"},{"orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","last_name":"Svoboda","full_name":"Svoboda, Jakub"}],"abstract":[{"text":"Given the increasingly stringent requirements on the performance and efficiency of communication networks, over the last years, great efforts have been made to render networks more flexible and programmable. In particular, modern networks support a flexible rerouting of flows, e.g., depending on the dynamically changing traffic or network conditions. However, the underlying algorithmic problems are still not well-understood today.In this paper, we revisit the k-Network Flow Update problem that asks for a schedule to reroute k unsplittable flows from their current paths to the given new paths, in a congestion-free manner in a capacitated network. We show that the problem is already NP-hard for three acyclic flows on simple directed graphs. Our main contribution is an efficient algorithm for sparse networks; specifically the algorithm is fixed parameter tractable in the number of flows and the treewidth of a graph that is the union of all flows. Our results also settle the open complexity question in the literature.","lang":"eng"}],"year":"2024","_id":"18925","conference":{"location":"Seoul, Republic of Korea","name":"NOMS: Network Operations and Management Symposiu ","start_date":"2024-05-06","end_date":"2024-05-10"},"publication_identifier":{"eissn":["2374-9709"],"isbn":["9798350327946"]},"article_processing_charge":"No","day":"01","publication_status":"published","ec_funded":1,"date_updated":"2025-11-05T07:34:27Z"},{"alternative_title":["PMLR"],"_id":"18974","conference":{"location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning","start_date":"2024-07-21","end_date":"2024-07-27"},"year":"2024","page":"47331-47344","abstract":[{"text":"Reinforcement Learning (RL) from temporal logical specifications is a fundamental problem in sequential decision making. One of the basic and core such specification is the reachability specification that requires a target set to be eventually visited. Despite strong empirical results for RL from such specifications, the theoretical guarantees are bleak, including the impossibility of Probably Approximately Correct (PAC) guarantee for reachability specifications. Given the impossibility result, in this work we consider the problem of RL from reachability specifications along with the information of expected conditional distance (ECD). We present (a) lower bound results which establish the necessity of ECD information for PAC guarantees and (b) an algorithm that establishes PAC-guarantees given the ECD information. To the best of our knowledge, this is the first RL from reachability specifications that does not make any assumptions on the underlying environment to learn policies.","lang":"eng"}],"author":[{"full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","orcid":"0000-0002-1419-3267"},{"last_name":"Bansal","full_name":"Bansal, Suguman","first_name":"Suguman"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"}],"title":"Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance","publication":"41st International Conference on Machine Learning","date_updated":"2025-01-30T07:46:16Z","article_processing_charge":"No","day":"29","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2025-01-30T07:45:22Z","publisher":"ML Research Press","citation":{"ama":"Svoboda J, Bansal S, Chatterjee K. Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. In: <i>41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:47331-47344.","mla":"Svoboda, Jakub, et al. “Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance.” <i>41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 47331–44.","apa":"Svoboda, J., Bansal, S., &#38; Chatterjee, K. (2024). Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. In <i>41st International Conference on Machine Learning</i> (Vol. 235, pp. 47331–47344). Vienna, Austria: ML Research Press.","ista":"Svoboda J, Bansal S, Chatterjee K. 2024. Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 47331–47344.","ieee":"J. Svoboda, S. Bansal, and K. Chatterjee, “Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance,” in <i>41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 47331–47344.","short":"J. Svoboda, S. Bansal, K. Chatterjee, in:, 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 47331–47344.","chicago":"Svoboda, Jakub, Suguman Bansal, and Krishnendu Chatterjee. “Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance.” In <i>41st International Conference on Machine Learning</i>, 235:47331–44. ML Research Press, 2024."},"oa":1,"corr_author":"1","status":"public","department":[{"_id":"KrCh"}],"OA_place":"publisher","scopus_import":"1","OA_type":"green","quality_controlled":"1","main_file_link":[{"url":"https://openreview.net/forum?id=mXUDDL4r1Q","open_access":"1"}],"month":"07","language":[{"iso":"eng"}],"volume":235,"oa_version":"Preprint","date_published":"2024-07-29T00:00:00Z","type":"conference","intvolume":"       235"}]