A submodular function on a finite set 
is a real-valued function 
on its subsets
satisfying
 |
for every 
.
This inequality expresses diminishing marginal gains:
the change from adding an element outside a set
is at least as large for a subset as for the containing
set (Bach 2013, p. 154). A normalized function
has 
,
and a nondecreasing function satisfies 
when 
. Matroid rank is
an integer-valued example. Polymatroids
use normalized nondecreasing submodular functions as capacity bounds.
