劣モジュラ性と限界効用逓減性が同値であることの証明

結構簡単だけど日本語だと見つからなかった（探し方が悪かっただけかもしれない）のでメモ．

$U$ を集合， $f : 2^U \to \mathbb{R}$ を集合関数とする．
Dfn. 1. $f$ が劣モジュラ (submodular) であるとは， $\forall X, Y \subseteq U, \; f(X) + f(Y) \ge f(X \cup Y) + f(X \cap Y)$ であること．
Dfn. 2. $f$ が限界効用逓減 (diminishing returns) とは， $\forall X \subseteq Y \subseteq U, \; Z \subseteq U \setminus Y, \; f(X \cup Z ) - f(X) \ge f(Y \cup Z ) - f(Y) \$ であること．

Prop. 1. $f$ が劣モジュラ $\Leftrightarrow$ $f$ は限界効用逓減．

pf.
$\Rightarrow$ の方向：（これはかなり簡単）．
$f$ が劣モジュラと仮定する．仮定より，任意の $X \subseteq Y$ と $Z \subseteq U \setminus Y$ に対して $f(X \cup Z) + f(Y) \ge f(Y \cup Z) + f(X)$ が成り立つ（劣モジュラ不等式において， $X$ を $X \cup Z$ とした）．したがって，
$f(X \cup Z) - f(X) \ge f(Y \cup Z) - f(Y)$ である．

$\Leftarrow$ の方向：
$f$ が限界効用逓減であると仮定する． $X, Y\subseteq U$ を任意に取る． $X = Y$ であれば $X = Y = X \cup Y = X \cap Y$ だから劣モジュラ不等式は明らかにしたがう．以下， $X \neq Y$ と仮定する．
$X' = X \cap Y$ とすると， $X' \subseteq Y \subseteq U$ である．また， $Z = X \setminus Y$ とすると， $Z \subseteq U \setminus Y$ である．このとき，仮定より
$f(X' \cup Z) - f(X') \ge f(Y \cup Z) - f(Y)$
となるが， $X' \cup Z = X, \; Y \cup Z = X \cup Y, \; X' = X \cap Y$ なので， $f(X) - f(X \cap Y) \ge f(X \cup Y) - f(Y)$ であり，変形すると，
$f(X) + f(Y) \ge f(X \cup Y) + f(X \cap Y)$
が言える．（証明終）