Optimal strategies in solvency games can be aperiodic and computable
On Periodic and Aperiodic Optimal Strategies in Solvency Games
Computer Science and Game Theory
Summary
Solvency games model an investor repeatedly choosing actions that affect their fortune, trying to avoid bankruptcy. The authors study the patterns of the best possible ways to play these games, showing that the best strategies don’t always follow simple repeating cycles as previously conjectured. They prove that sometimes the best strategy is unique but never settles into a simple repetitive pattern. However, in some simpler cases, optimal strategies do have periodic or almost repeating patterns. They also show when these best strategies can be computed by a machine.
What this means in practice
- •For financial risk modelers: Determine when risk-averse investment strategies require complex, non-repeating decision patterns to minimize chance of ruin under certain gain-loss conditions.
- •For automated decision system developers: Find computable optimal policies for systems modeled by solvency games with bounded losses, aiding design of robust control algorithms.
A theory result. No direct application yet.
Authors
Quentin Guilmant, Florian Luca, Richard Mayr, Joël Ouaknine, James Worrell
Abstract
Solvency games are a gambling problem on infinite-state Markov decision processes in which the state $n \in \mathbb{N}$ represents an 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 $\{-\ell,\ldots,m\}$. The risk-averse investor wants to minimise the probability of eventual ruin (reaching a fortune $\le 0$). It was shown in [Berger et al.] that memoryless deterministic optimal strategies exist, but they are not eventually constant in general. Even in the special case of gains in $\{-2,\ldots,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 Kučera). Already in the case of gains in $\{-3,\ldots,1\}$, it is possible for the optimal strategy to be unique but aperiodic. For gains in $\{-2,\ldots,1\}$, there always exists an ultimately periodic 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 $\{-\ell,\ldots,1\}$ for any $\ell \in \mathbb{N}$. Computability in the general case however remains open.