Standard
Entropic Risk for Turn-Based Stochastic Games. / Baier, Christel; Chatterjee, Krishnendu
; Meggendorfer, Tobias et al.
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. ed. / Jerome Leroux; Sylvain Lombardy; David Peleg. Vol. 272 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. p. 15:1-15:16 15 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272).
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Harvard
Baier, C, Chatterjee, K
, Meggendorfer, T & Piribauer, J 2023,
Entropic Risk for Turn-Based Stochastic Games. in J Leroux, S Lombardy & D Peleg (eds),
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. vol. 272, 15, Leibniz International Proceedings in Informatics, LIPIcs, vol. 272, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 15:1-15:16.
https://doi.org/10.4230/LIPIcs.MFCS.2023.15APA
Baier, C., Chatterjee, K.
, Meggendorfer, T., & Piribauer, J. (2023).
Entropic Risk for Turn-Based Stochastic Games. In J. Leroux, S. Lombardy, & D. Peleg (Eds.),
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 (Vol. 272, pp. 15:1-15:16). Article 15 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272). Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.MFCS.2023.15Vancouver
Baier C, Chatterjee K
, Meggendorfer T, Piribauer J.
Entropic Risk for Turn-Based Stochastic Games. In Leroux J, Lombardy S, Peleg D, editors, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. Vol. 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. p. 15:1-15:16. 15. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2023.15
Author
Baier, Christel ; Chatterjee, Krishnendu
; Meggendorfer, Tobias et al. /
Entropic Risk for Turn-Based Stochastic Games. 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. editor / Jerome Leroux ; Sylvain Lombardy ; David Peleg. Vol. 272 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 15:1-15:16 (Leibniz International Proceedings in Informatics, LIPIcs).
Bibtex
@inproceedings{5183f0c245c4433b9cf91db91fd5781d,
title = "Entropic Risk for Turn-Based Stochastic Games.",
abstract = "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{\textquoteright}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.",
keywords = "Stochastic games, risk-aware verification",
author = "Christel Baier and Krishnendu Chatterjee and Tobias Meggendorfer and Jakob Piribauer",
year = "2023",
month = aug,
day = "28",
doi = "10.4230/LIPIcs.MFCS.2023.15",
language = "English",
volume = "272",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "15:1--15:16",
editor = "Jerome Leroux and Sylvain Lombardy and David Peleg",
booktitle = "48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023",
}
RIS
TY - GEN
T1 - Entropic Risk for Turn-Based Stochastic Games.
AU - Baier, Christel
AU - Chatterjee, Krishnendu
AU - Meggendorfer, Tobias
AU - Piribauer, Jakob
PY - 2023/8/28
Y1 - 2023/8/28
N2 - 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.
AB - 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.
KW - Stochastic games, risk-aware verification
U2 - 10.4230/LIPIcs.MFCS.2023.15
DO - 10.4230/LIPIcs.MFCS.2023.15
M3 - Conference contribution/Paper
VL - 272
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 15:1-15:16
BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
A2 - Leroux, Jerome
A2 - Lombardy, Sylvain
A2 - Peleg, David
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ER -
