= Solution
The <monotone decomposition of a submodular set function> subtracts each element's smallest possible <marginal increment>. For $x\in V$, define
$$
d_x=f(V)-f(V\setminus\{x\}),\qquad
h(S)=f(\varnothing)+\sum_{x\in S}d_x,\qquad
g(S)=f(S)-h(S).
$$
The <set function> $h$ is a <modular set function>: the contributions of each element, and the constant $f(\varnothing)$, cancel in
$$
h(A)+h(B)=h(A\cap B)+h(A\cup B).
$$
Subtracting this equality from the <submodularity> inequality for $f$ proves that $g$ is a <submodular set function>. Also $g(\varnothing)=0$, so it is a <normalised set function>.
For $x\notin S$, the inclusion $S\subseteq V\setminus\{x\}$ and <diminishing returns> imply
$$
\Delta_x g(S)=\Delta_x f(S)-d_x\geq0.
$$
Adding elements one at a time now proves that $g$ is a <monotone set function>. Since it starts at zero, it is also a <nonnegative function>. Thus \b[$f=g+h$ has all the required properties].
Here <modular set function> means equality in the intersection–union identity; a constant term is allowed. If one imposed the additional convention $h(\varnothing)=0$, the claimed decomposition of an arbitrary $f$ would require $f(\varnothing)=0$. The displayed constant is essential for the problem as stated. For $V=\varnothing$, take $g=0$ and $h=f$.
Back to article page
