License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.487
URN: urn:nbn:de:0030-drops-43959
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4395/
Go to the corresponding LIPIcs Volume Portal

Brázdil, Tomás ; Chen, Taolue ; Forejt, Vojtech ; Novotný, Petr ; Simaitis, Aistis

Solvency Markov Decision Processes with Interest

pdf-format:
37.pdf (0.5 MB)

Abstract

Solvency games, introduced by Berger et al., provide an abstract framework for modelling 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 study problems related to the minimum initial wealth sufficient to avoid bankruptcy (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 \cap 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.

BibTeX - Entry

@InProceedings{brzdil_et_al:LIPIcs:2013:4395,
  author =	{Tom{\'a}s Br{\'a}zdil and Taolue Chen and Vojtech Forejt and Petr Novotn{\'y} and Aistis Simaitis},
  title =	{{Solvency Markov Decision Processes with Interest}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{487--499},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4395},
  URN =		{urn:nbn:de:0030-drops-43959},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.487},
  annote =	{Keywords: Markov decision processes, algorithms, complexity, market models.}
}

Keywords: Markov decision processes, algorithms, complexity, market models.
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI