Diminishing returns characterization of submodularity (${\Delta }_{x}f(A)\ge {\Delta }_{x}f(B)(A\subseteq B,x\notin B)$)

For a real-valued set function on a finite ground set, the displayed marginal increment comparison is equivalent to submodularity. The interpretation is that an additional item contributes no more after more items have already been chosen. This concerns relative increments, which may be negative; it does not assert the monotone set function property.

Proof. Applying the defining inequality for a submodular set function to $A+x$ and $B$ gives the comparison immediately. Conversely, list $A\setminus B=\{x_1,\dots ,x_m\}$ and compare adding these elements, in the same order, first to $A\cap B$ and then to $B$. At every step the first conditioning set is contained in the second, so the first marginal increment is at least the second. The telescoping sums givewhich rearranges to submodularity.