BRÁZDIL, Tomáš, Taolue CHEN, Vojtěch FOREJT, Petr NOVOTNÝ and Aistis SIMAITIS. Solvency Markov Decision Processes with Interest. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Dagstuhl, Germany: IBFI Schloss Dagstuhl, 2013. p. 487-499. ISBN 978-3-939897-64-4. doi:10.4230/LIPIcs.FSTTCS.2013.487.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Solvency Markov Decision Processes with Interest
Authors BRÁZDIL, Tomáš (203 Czech Republic, guarantor, belonging to the institution), Taolue CHEN (156 China), Vojtěch FOREJT (203 Czech Republic, belonging to the institution), Petr NOVOTNÝ (203 Czech Republic, belonging to the institution) and Aistis SIMAITIS (440 Lithuania).
Edition Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), p. 487-499, 13 pp. 2013.
Publisher IBFI Schloss Dagstuhl
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/13:00066380
Organization unit Faculty of Informatics
ISBN 978-3-939897-64-4
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.487
Keywords in English stochastic systems; markov decision processes; reward functions
Tags best2, firank_B, formela-conference
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 24/4/2014 18:37.
Abstract
Solvency games, introduced by Berger et al., provide an abstract framework for modeling decisions of a risk-averse investor, whose goal is to avoid ever going broke. We study a new variant of this model, where in addition to stochastic environment and fixed increments and decrements to the investor's wealth we introduce interest, which is earned or paid on the current level of savings or debt, respectively. We concentrate on problems related to the minimum initial wealth sufficient to avoid bankrupting (i.e. steady decrease of the wealth) with probability at least $p$. We present an exponential time algorithm which approximates this minimum initial wealth, and show that a polynomial time approximation is not possible unless P = NP. For the qualitative case, i.e. p=1, we show that the problem whether a given number is larger than or equal to the minimum initial wealth belongs to NP intersection coNP, and show that a polynomial time algorithm would yield a polynomial time algorithm for mean-payoff games, existence of which is a longstanding open problem. We also identify some classes of solvency MDPs for which this problem is in P. In all above cases the algorithms also give corresponding bankruptcy avoiding strategies.
Links
GPP202/12/P612, research and development projectName: Formální verifikace stochastických systémů s reálným časem (Acronym: Formální verifikace stochastických systémů s reáln)
Investor: Czech Science Foundation, Postdoctoral projects
MUNI/A/0760/2012, internal MU codeName: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Acronym: FI MAV II.)
Investor: Masaryk University, Grant Agency of Masaryk University, Category A
PrintDisplayed: 5/3/2021 03:07