Entropic Risk for Turn-Based Stochastic Games

Christel BaierChristel Baier, Krishnendu ChatterjeeKrishnendu Chatterjee, Tobias MeggendorferTobias Meggendorfer, Jakob PiribauerJakob Piribauer

DOI Link

Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, Jakob Piribauer
Entropic Risk for Turn-Based Stochastic Games
In Jérôme Leroux and Sylvain Lombardy and David Peleg, eds., 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, 15:1--15:16, 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Details
Bibtex

KurzfassungAbstract
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. Furthermore, an approximation algorithm for the optimal value of ERisk is provided.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{BCMP2023,
  author    = {Christel Baier and Krishnendu Chatterjee and Tobias Meggendorfer
               and Jakob Piribauer},
  title     = {Entropic Risk for Turn-Based Stochastic Games},
  editor    = {J{\'{e}}r{\^{o}}me Leroux and Sylvain Lombardy and David Peleg},
  booktitle = {48th International Symposium on Mathematical Foundations of
               Computer Science, {MFCS} 2023, August 28 to September 1, 2023,
               Bordeaux, France},
  series    = {LIPIcs},
  volume    = {272},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2023},
  pages     = {15:1--15:16},
  doi       = {10.4230/LIPICS.MFCS.2023.15}
}