[{"day":"20","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"ToHe"}],"doi":"10.4230/LIPIcs.MFCS.2025.30","status":"public","publication_status":"published","file_date_updated":"2025-09-08T07:11:12Z","oa":1,"intvolume":"       345","external_id":{"arxiv":["2502.0531"]},"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"scopus_import":"1","abstract":[{"lang":"eng","text":"We consider equilibria in multiplayer stochastic graph games with terminal-node rewards. In such games, Nash equilibria are defined assuming that each player seeks to maximise their expected payoff, ignoring their aversion or tolerance to risk. We therefore study risk-sensitive equilibria (RSEs), where the expected payoff is replaced by a risk measure. A classical risk measure in the literature is the entropic risk measure, where each player has a real valued parameter capturing their risk-averseness. We introduce the extreme risk measure, which corresponds to extreme cases of entropic risk measure, where players are either extreme optimists or extreme pessimists. Under extreme risk measure, every player is an extremist: an extreme optimist perceives their reward as the maximum payoff that can be achieved with positive probability, while an extreme pessimist expects the minimum payoff achievable with positive probability. We argue that the extreme risk measure, especially in multi-player graph based settings, is particularly relevant as they can model several real life instances such as interactions between secure systems and potential security threats, or distributed controls for safety critical systems. We prove that RSEs defined with the extreme risk measure are guaranteed to exist when all rewards are non-negative. Furthermore, we prove that the problem of deciding whether a given game contains an RSE that generates risk measures within specified intervals is decidable and NP-complete for our extreme risk measure, and even PTIME-complete when all players are extreme optimists, while that same problem is undecidable using the entropic risk measure or even the classical expected payoff. This establishes, to our knowledge, the first decidable fragment for equilibria in simple stochastic games without restrictions on strategy types or number of players."}],"article_number":"30","volume":345,"date_created":"2025-09-07T22:01:32Z","oa_version":"Published Version","OA_type":"gold","file":[{"file_id":"20306","creator":"dernst","file_name":"2025_MFCS_Brice.pdf","date_created":"2025-09-08T07:11:12Z","checksum":"9bc6b8e537662d371d2a27444cbc0b75","file_size":1149694,"access_level":"open_access","date_updated":"2025-09-08T07:11:12Z","success":1,"content_type":"application/pdf","relation":"main_file"}],"_id":"20290","date_updated":"2025-09-08T07:15:40Z","citation":{"mla":"Brice, Léonard, et al. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 345, 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">10.4230/LIPIcs.MFCS.2025.30</a>.","ama":"Brice L, Henzinger TA, Thejaswini KS. Finding equilibria: Simpler for pessimists, simplest for optimists. In: <i>50th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">10.4230/LIPIcs.MFCS.2025.30</a>","ieee":"L. Brice, T. A. Henzinger, and K. S. Thejaswini, “Finding equilibria: Simpler for pessimists, simplest for optimists,” in <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Warsaw, Poland, 2025, vol. 345.","short":"L. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 50th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","apa":"Brice, L., Henzinger, T. A., &#38; Thejaswini, K. S. (2025). Finding equilibria: Simpler for pessimists, simplest for optimists. In <i>50th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">https://doi.org/10.4230/LIPIcs.MFCS.2025.30</a>","ista":"Brice L, Henzinger TA, Thejaswini KS. 2025. Finding equilibria: Simpler for pessimists, simplest for optimists. 50th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 345, 30.","chicago":"Brice, Léonard, Thomas A Henzinger, and K. S. Thejaswini. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” In <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">https://doi.org/10.4230/LIPIcs.MFCS.2025.30</a>."},"month":"08","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","corr_author":"1","year":"2025","conference":{"end_date":"2025-08-29","start_date":"2025-08-25","location":"Warsaw, Poland","name":"MFCS: Mathematical Foundations of Computer Science"},"acknowledgement":"This work is a part of project VAMOS that has received funding from the European\r\nResearch Council (ERC), grant agreement No 101020093. We thank anonymous reviewers for pointing us to the Hurwicz criterion and to the work of Gallego-Hernández and Mansutti [13]. We thank Marie van den Bogaard for her valuable feedback on the first author’s PhD dissertation, which helped improve the quality of this work. ","OA_place":"publisher","quality_controlled":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773881"]},"article_processing_charge":"Yes","ddc":["000"],"publication":"50th International Symposium on Mathematical Foundations of Computer Science","has_accepted_license":"1","type":"conference","date_published":"2025-08-20T00:00:00Z","author":[{"first_name":"Léonard","last_name":"Brice","full_name":"Brice, Léonard"},{"orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Thejaswini, K. S.","last_name":"Thejaswini","first_name":"K. S.","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753"}],"alternative_title":["LIPIcs"],"title":"Finding equilibria: Simpler for pessimists, simplest for optimists","ec_funded":1,"arxiv":1},{"publication":"50th International Symposium on Mathematical Foundations of Computer Science","ddc":["000"],"article_processing_charge":"No","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773881"]},"quality_controlled":"1","ec_funded":1,"arxiv":1,"title":"Resolving nondeterminism with randomness","alternative_title":["LIPIcs"],"author":[{"orcid":"0000-0002-2985-7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"first_name":"Aditya","last_name":"Prakash","full_name":"Prakash, Aditya"},{"full_name":"Thejaswini, K. S.","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","first_name":"K. S.","last_name":"Thejaswini"}],"date_published":"2025-08-20T00:00:00Z","type":"conference","has_accepted_license":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","corr_author":"1","language":[{"iso":"eng"}],"month":"08","_id":"20291","date_updated":"2025-09-08T07:06:11Z","citation":{"ieee":"T. A. Henzinger, A. Prakash, and K. S. Thejaswini, “Resolving nondeterminism with randomness,” in <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Warsaw, Poland, 2025, vol. 345.","ama":"Henzinger TA, Prakash A, Thejaswini KS. Resolving nondeterminism with randomness. In: <i>50th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">10.4230/LIPIcs.MFCS.2025.57</a>","mla":"Henzinger, Thomas A., et al. “Resolving Nondeterminism with Randomness.” <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 345, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">10.4230/LIPIcs.MFCS.2025.57</a>.","ista":"Henzinger TA, Prakash A, Thejaswini KS. 2025. Resolving nondeterminism with randomness. 50th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 345, 57.","short":"T.A. Henzinger, A. Prakash, K.S. Thejaswini, in:, 50th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","apa":"Henzinger, T. A., Prakash, A., &#38; Thejaswini, K. S. (2025). Resolving nondeterminism with randomness. In <i>50th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">https://doi.org/10.4230/LIPIcs.MFCS.2025.57</a>","chicago":"Henzinger, Thomas A, Aditya Prakash, and K. S. Thejaswini. “Resolving Nondeterminism with Randomness.” In <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">https://doi.org/10.4230/LIPIcs.MFCS.2025.57</a>."},"file":[{"file_name":"2025_MFCS_HenzingerT.pdf","checksum":"6068b772aba6cb0d01f3e5a90abed973","file_size":1009644,"date_created":"2025-09-08T06:56:56Z","file_id":"20305","creator":"dernst","content_type":"application/pdf","relation":"main_file","access_level":"open_access","date_updated":"2025-09-08T06:56:56Z","success":1}],"OA_place":"publisher","acknowledgement":"This work is a part of project VAMOS that has received funding from the European Research Council (ERC), grant agreement No 101020093.","conference":{"name":"MFCS: Mathematical Foundations of Computer Science","location":"Warsaw, Poland","start_date":"2025-08-25","end_date":"2025-08-29"},"year":"2025","scopus_import":"1","external_id":{"arxiv":["2502.12872"]},"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"intvolume":"       345","OA_type":"gold","oa_version":"Published Version","volume":345,"date_created":"2025-09-07T22:01:32Z","article_number":"57","abstract":[{"lang":"eng","text":"We define and study classes of ω-regular automata for which the nondeterminism can be resolved by a policy that uses a combination of memory and randomness on any input word, based solely on the prefix read so far. We examine two settings for providing the input word to an automaton. In the first setting, called adversarial resolvability, the input word is constructed letter-by-letter by an adversary, dependent on the resolver’s previous decisions. In the second setting, called stochastic resolvability, the adversary pre-commits to an infinite word and reveals it letter-by-letter. In each setting, we require the existence of an almost-sure resolver, i.e., a policy that ensures that as long as the adversary provides a word in the language of the underlying nondeterministic automaton, the run constructed by the policy is accepting with probability 1.\r\nThe class of automata that are adversarially resolvable is the well-studied class of history-deterministic automata. The case of stochastically resolvable automata, on the other hand, defines a novel class. Restricting the class of resolvers in both settings to stochastic policies without memory introduces two additional new classes of automata. We show that the new automata classes offer interesting trade-offs between succinctness, expressivity, and computational complexity, providing a fine gradation between deterministic automata and nondeterministic automata."}],"publication_status":"published","status":"public","doi":"10.4230/LIPIcs.MFCS.2025.57","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"ToHe"}],"day":"20","project":[{"name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"file_date_updated":"2025-09-08T06:56:56Z","oa":1}]