Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1123332, author = {Brázdil, Tomáš and Chen, Taolue and Forejt, Vojtěch and Novotný, Petr and Simaitis, Aistis}, address = {Dagstuhl, Germany}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.487}, keywords = {stochastic systems; markov decision processes; reward functions}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Dagstuhl, Germany}, isbn = {978-3-939897-64-4}, pages = {487-499}, publisher = {IBFI Schloss Dagstuhl}, title = {Solvency Markov Decision Processes with Interest}, url = {http://drops.dagstuhl.de/opus/volltexte/2013/4395/pdf/37.pdf}, year = {2013} }
TY - JOUR ID - 1123332 AU - Brázdil, Tomáš - Chen, Taolue - Forejt, Vojtěch - Novotný, Petr - Simaitis, Aistis PY - 2013 TI - Solvency Markov Decision Processes with Interest PB - IBFI Schloss Dagstuhl CY - Dagstuhl, Germany SN - 9783939897644 KW - stochastic systems KW - markov decision processes KW - reward functions UR - http://drops.dagstuhl.de/opus/volltexte/2013/4395/pdf/37.pdf L2 - http://drops.dagstuhl.de/opus/volltexte/2013/4395/pdf/37.pdf N2 - 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. ER -
BRÁZDIL, Tomáš, Taolue CHEN, Vojtěch FOREJT, Petr NOVOTNÝ a Aistis SIMAITIS. Solvency Markov Decision Processes with Interest. Online. In \textit{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. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.487.
|