---
OA_place: publisher
OA_type: gold
_id: '20290'
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.'
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. "
alternative_title:
- LIPIcs
article_number: '30'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Léonard
  full_name: Brice, Léonard
  last_name: Brice
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
- first_name: K. S.
  full_name: Thejaswini, K. S.
  id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753
  last_name: Thejaswini
citation:
  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>'
  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>'
  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>.'
  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.'
  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.'
  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>.'
  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.
conference:
  end_date: 2025-08-29
  location: Warsaw, Poland
  name: 'MFCS: Mathematical Foundations of Computer Science'
  start_date: 2025-08-25
corr_author: '1'
date_created: 2025-09-07T22:01:32Z
date_published: 2025-08-20T00:00:00Z
date_updated: 2025-09-08T07:15:40Z
day: '20'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2025.30
ec_funded: 1
external_id:
  arxiv:
  - '2502.0531'
file:
- access_level: open_access
  checksum: 9bc6b8e537662d371d2a27444cbc0b75
  content_type: application/pdf
  creator: dernst
  date_created: 2025-09-08T07:11:12Z
  date_updated: 2025-09-08T07:11:12Z
  file_id: '20306'
  file_name: 2025_MFCS_Brice.pdf
  file_size: 1149694
  relation: main_file
  success: 1
file_date_updated: 2025-09-08T07:11:12Z
has_accepted_license: '1'
intvolume: '       345'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 50th International Symposium on Mathematical Foundations of Computer
  Science
publication_identifier:
  isbn:
  - '9783959773881'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Finding equilibria: Simpler for pessimists, simplest for optimists'
tmp:
  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)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 345
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20291'
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."
acknowledgement: This work is a part of project VAMOS that has received funding from
  the European Research Council (ERC), grant agreement No 101020093.
alternative_title:
- LIPIcs
article_number: '57'
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
- first_name: Aditya
  full_name: Prakash, Aditya
  last_name: Prakash
- first_name: K. S.
  full_name: Thejaswini, K. S.
  id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753
  last_name: Thejaswini
citation:
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2025-08-29
  location: Warsaw, Poland
  name: 'MFCS: Mathematical Foundations of Computer Science'
  start_date: 2025-08-25
corr_author: '1'
date_created: 2025-09-07T22:01:32Z
date_published: 2025-08-20T00:00:00Z
date_updated: 2025-09-08T07:06:11Z
day: '20'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2025.57
ec_funded: 1
external_id:
  arxiv:
  - '2502.12872'
file:
- access_level: open_access
  checksum: 6068b772aba6cb0d01f3e5a90abed973
  content_type: application/pdf
  creator: dernst
  date_created: 2025-09-08T06:56:56Z
  date_updated: 2025-09-08T06:56:56Z
  file_id: '20305'
  file_name: 2025_MFCS_HenzingerT.pdf
  file_size: 1009644
  relation: main_file
  success: 1
file_date_updated: 2025-09-08T06:56:56Z
has_accepted_license: '1'
intvolume: '       345'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 50th International Symposium on Mathematical Foundations of Computer
  Science
publication_identifier:
  isbn:
  - '9783959773881'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Resolving nondeterminism with randomness
tmp:
  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)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 345
year: '2025'
...