Tight approximations of dynamic risk measures

Abstract

This paper compares two frameworks for measuring risk in a multiperiod setting. The first corresponds to applying a single coherent risk measure to the cumulative future costs, and the second involves applying a composition of one-step coherent risk mappings. We characterize several necessary and sufficient conditions under which one measurement always dominates the other and introduce a metric to quantify how close the two measures are. Using this notion, we address the question of how tightly a given coherent measure can be approximated by lower or upper bounding compositional measures. We exhibit an interesting asymmetry between the two cases: the tightest upper bound can be exactly characterized and corresponds to a popular construction in the literature, whereas the tightest lower bound is not readily available. We show that testing domination and computing the approximation factors are generally NP-hard, even when the risk measures are comonotonic and law-invariant. However, we characterize conditions and discuss examples where polynomial-time algorithms are possible. One such case is the well-known conditional value-at-risk measure, which we explore in more detail. Our theoretical and algorithmic constructions exploit interesting connections between the study of risk measures and the theory of submodularity and combinatorial optimization, which may be of independent interest.