= Diminishing returns characterization of submodularity
{title2=$\Delta_x f(A)\geq\Delta_x f(B)\quad(A\subseteq B,\ x\notin B)$}
= Diminishing returns
{synonym}
= Diminishing returns characterisation of submodularity
{synonym}
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.
\b[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,\ldots,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> give
$$
f(A)-f(A\cap B)\geq f(A\cup B)-f(B),
$$
which rearranges to <submodularity>.
Back to article page
