  This paper compares two different frameworks recently introduced in the
literature for measuring risk in a multi-period setting. The first corresponds
to applying a single coherent risk measure to the cumulative future costs,
while the second involves applying a composition of one-step coherent risk
mappings. We summarize the relative strengths of the two methods, characterize
several necessary and sufficient conditions under which one of the measurements
always dominates the other, and introduce a metric to quantify how close the
two risk 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
possible upper-bound can be exactly characterized, and corresponds to a popular
construction in the literature, while the tightest-possible lower bound is not
readily available. We show that testing domination and computing the
approximation factors is generally NP-hard, even when the risk measures in
question are comonotonic and law-invariant. However, we characterize conditions
and discuss several examples where polynomial-time algorithms are possible. One
such case is the well-known Conditional Value-at-Risk measure, which is further
explored in our companion paper [Huang, Iancu, Petrik and Subramanian, "Static
and Dynamic Conditional Value at Risk" (2012)]. 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.
