Solvency Markov Decision Processes with Interest

D 2013

Solvency Markov Decision Processes with Interest

BRÁZDIL, Tomáš, Taolue CHEN, Vojtěch FOREJT, Petr NOVOTNÝ, Aistis SIMAITIS et. al.

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

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"

Odkazy

URL

Kód RIV

RIV/00216224:14330/13:00066380

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-64-4

ISSN

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, core_B, firank_B, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 24. 4. 2014 18:37, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 VaV

Ná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, Formální verifikace stochastických systémů s reálným časem

MUNI/A/0760/2012, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

BRÁZDIL, Tomáš, Taolue CHEN, Vojtěch FOREJT, Petr NOVOTNÝ a Aistis SIMAITIS. Solvency Markov Decision Processes with Interest. Online. 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. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.487.

@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.

Podrobný výpis o publikaci