Solvency Markov decision processes with interest

DOI10.4230/LIPICS.FSTTCS.2013.487zbMATH Open1360.91091arXiv1310.3119OpenAlexW2963565802MaRDI QIDQ2963937FDOQ2963937

Authors: Tomáš Brázdil, Taolue Chen, Vojtech Forejt, Petr Novotný, Aistis Simaitis 

Publication date: 21 February 2017

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 both NP and 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.

Full work available at URL: https://arxiv.org/abs/1310.3119

Recommendations

• scientific article; zbMATH DE number 6096477
• One-counter Markov decision processes
• The complexity of solving stochastic games on graphs
• The complexity of mean payoff games on graphs
• The complexity of stochastic games

zbMATH Keywords

algorithmscomplexityMarkov decision processesmarket models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26) Markov and semi-Markov decision processes (90C40) Other game-theoretic models (91A40)

Cited In (3)

• Percentile queries in multi-dimensional Markov decision processes
• A Markov decision problem in a risk model with interest rate and Markovian environment
• Markov decision process algorithms for wealth allocation problems with defaultable bonds

This page was built for publication: Solvency Markov decision processes with interest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963937)