---
_id: '14417'
abstract:
- lang: eng
  text: Entropic risk (ERisk) is an established risk measure in finance, quantifying
    risk by an exponential re-weighting of rewards. We study ERisk for the first time
    in the context of turn-based stochastic games with the total reward objective.
    This gives rise to an objective function that demands the control of systems in
    a risk-averse manner. We show that the resulting games are determined and, in
    particular, admit optimal memoryless deterministic strategies. This contrasts
    risk measures that previously have been considered in the special case of Markov
    decision processes and that require randomization and/or memory. We provide several
    results on the decidability and the computational complexity of the threshold
    problem, i.e. whether the optimal value of ERisk exceeds a given threshold. In
    the most general case, the problem is decidable subject to Shanuel’s conjecture.
    If all inputs are rational, the resulting threshold problem can be solved using
    algebraic numbers, leading to decidability via a polynomial-time reduction to
    the existential theory of the reals. Further restrictions on the encoding of the
    input allow the solution of the threshold problem in NP∩coNP. Finally, an approximation
    algorithm for the optimal value of ERisk is provided.
acknowledgement: "This work was partly funded by the ERC CoG 863818 (ForM-SMArt),
  the DFG Grant\r\n389792660 as part of TRR 248 (Foundations of Perspicuous Software
  Systems), the Cluster of\r\nExcellence EXC 2050/1 (CeTI, project ID 390696704, as
  part of Germany’s Excellence Strategy), and the DFG projects BA-1679/11-1 and BA-1679/12-1."
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Christel
  full_name: Baier, Christel
  last_name: Baier
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Tobias
  full_name: Meggendorfer, Tobias
  id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
  last_name: Meggendorfer
  orcid: 0000-0002-1712-2165
- first_name: Jakob
  full_name: Piribauer, Jakob
  last_name: Piribauer
citation:
  ama: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based
    stochastic games. In: <i>48th International Symposium on Mathematical Foundations
    of Computer Science</i>. Vol 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2023. doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2023.15">10.4230/LIPIcs.MFCS.2023.15</a>'
  apa: 'Baier, C., Chatterjee, K., Meggendorfer, T., &#38; Piribauer, J. (2023). Entropic
    risk for turn-based stochastic games. In <i>48th International Symposium on Mathematical
    Foundations of Computer Science</i> (Vol. 272). Bordeaux, France: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2023.15">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>'
  chicago: Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob
    Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” In <i>48th International
    Symposium on Mathematical Foundations of Computer Science</i>, Vol. 272. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2023.15">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>.
  ieee: C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk
    for turn-based stochastic games,” in <i>48th International Symposium on Mathematical
    Foundations of Computer Science</i>, Bordeaux, France, 2023, vol. 272.
  ista: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2023. Entropic risk for
    turn-based stochastic games. 48th International Symposium on Mathematical Foundations
    of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science,
    LIPIcs, vol. 272, 15.'
  mla: Baier, Christel, et al. “Entropic Risk for Turn-Based Stochastic Games.” <i>48th
    International Symposium on Mathematical Foundations of Computer Science</i>, vol.
    272, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2023.15">10.4230/LIPIcs.MFCS.2023.15</a>.
  short: C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 48th International
    Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik, 2023.
conference:
  end_date: 2023-09-01
  location: Bordeaux, France
  name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
  start_date: 2023-08-28
date_created: 2023-10-09T09:21:05Z
date_published: 2023-08-21T00:00:00Z
date_updated: 2025-07-14T09:09:57Z
day: '21'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2023.15
ec_funded: 1
external_id:
  arxiv:
  - '2307.06611'
file:
- access_level: open_access
  checksum: 402281b17ed669bbf149d0fdf68ac201
  content_type: application/pdf
  creator: dernst
  date_created: 2023-10-09T09:19:11Z
  date_updated: 2023-10-09T09:19:11Z
  file_id: '14418'
  file_name: 2023_LIPIcsMFCS_Baier.pdf
  file_size: 826843
  relation: main_file
  success: 1
file_date_updated: 2023-10-09T09:19:11Z
has_accepted_license: '1'
intvolume: '       272'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 48th International Symposium on Mathematical Foundations of Computer
  Science
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959772921'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Entropic risk for turn-based stochastic games
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: 272
year: '2023'
...