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 investoru27s wealth, we introduceinterest, 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.
展开▼
机译：Berger等人介绍的偿付能力游戏提供了一个抽象框架，用于为规避风险的投资者的决策建模，其目标是避免破产。我们研究了该模型的一个新变体，除了随机环境和固定或递增或递减的投资者财富外，我们还引入利息，利息分别根据当前的储蓄或债务水平赚取或支付。与最小初始财富足以避免破产（即财富的稳步减少）有关，概率至少为p。我们提出了一种近似最小初始财富的指数时间算法，并表明除非P = NP，否则多项式时间近似是不可能的。对于定性情况，即p = 1，我们证明了给定数是否大于等于或等于最小初始资产的财富属于NP cap coNP，并且表明多项式时间算法将产生用于均值收益博弈的多项式时间算法，该算法的存在是一个长期存在的开放问题。我们还确定了在P中存在此问题的某些类别的偿付能力MDP。在上述所有情况下，算法还提供了相应的避免破产策略。
展开▼
