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

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


 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)
が言える.(証明終)