BRÁZDIL, Tomáš, Taolue CHEN, Vojtěch FOREJT, Petr NOVOTNÝ a 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. s. 487-499. ISBN 978-3-939897-64-4. doi:10.4230/LIPIcs.FSTTCS.2013.487.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Solvency Markov Decision Processes with Interest
Autoři BRÁZDIL, Tomáš (203 Česká republika, garant, domácí), Taolue CHEN (156 Čína), Vojtěch FOREJT (203 Česká republika, domácí), Petr NOVOTNÝ (203 Česká republika, domácí) a Aistis SIMAITIS (440 Litva).
Vydání Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), od s. 487-499, 13 s. 2013.
Nakladatel IBFI Schloss Dagstuhl
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Forma vydání elektronická verze "online"
WWW URL
Kód RIV RIV/00216224:14330/13:00066380
Organizační jednotka Fakulta informatiky
ISBN 978-3-939897-64-4
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.487
Klíčová slova anglicky stochastic systems; markov decision processes; reward functions
Štítky best2, firank_B, formela-conference
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 24. 4. 2014 18:37.
Anotace
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.
Návaznosti
GPP202/12/P612, projekt VaVNázev: Formální verifikace stochastických systémů s reálným časem (Akronym: Formální verifikace stochastických systémů s reáln)
Investor: Grantová agentura ČR, Postdoktorské projekty
MUNI/A/0760/2012, interní kód MUNázev: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.)
Investor: Masarykova univerzita, Grantová agentura MU, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
VytisknoutZobrazeno: 17. 1. 2021 01:57