Solvency games are a gambling problem on infinite-state Markov
decision processes in which the state n∈N
represents the investor's fortune. In every round, the
investor chooses an action from a finite action set, and every action
yields a distribution over integer-valued gains in an interval
{-l, …, m}. The risk-averse investor
wants to minimise the probability of eventual ruin (reaching a fortune
≤ 0).
It was shown in [3]
that memoryless deterministic optimal strategies exist,
but they are not eventually constant in general.
Even in the special case of gains in {-2, …, 1}, the optimal strategy
may need to make use of two different actions at arbitrarily high
fortunes.
We show that optimal strategies in solvency games need not be
ultimately periodic in general (thus disproving a 2012 conjecture of Kucera [11,
Sec. 3]).
Already in the case of gains in {-3, …, 1}, it is possible
for the optimal strategy to be unique but aperiodic.
For gains in {-2, …, 1}, there always exists an optimal
strategy whose tail is constant or alternates between two actions.
Finally, we show that the optimal strategy is computable if it is unique.
Moreover, (some) optimal strategy can always be computed
in the case of gains in {-l, …, 1} for any
l ∈ N. Computability in
the general case however remains open.
Submitted, 2026. 23 pages.
PDF
© 2026 Quentin Guilmant, Florian Luca, Richard Mayr,
Joël Ouaknine, and James Worrell.