集合関数，劣モジュラ性とは

更新 2021/03/07

集合関数と劣モジュラ性についての基本を紹介します。

集合関数

今回は，以下のような実数値集合関数
fff
 を扱います。
入力：集合。台集合
EEE
の部分集合ならなんでもOK。
出力：実数。
例
台集合を
E={1,2}E=\{1,2\}E={1,2}
 とすると，入力として考えられるのは4通り。例えば，集合関数
fff
 の例としては，
f(∅)=0f(\emptyset)=0f(∅)=0，f({1})=3f(\{1\})=3f({1})=3，f({2})=1f(\{2\})=1f({2})=1，f({1,2})=10f(\{1,2\})=10f({1,2})=10
なるものが考えられる。
1が米，2が明太子，fff
 は効用（嬉しさ）を表すものと考えてみましょう。米だけある嬉しさは
333，明太子だけだと
111，両方あると相性抜群なので嬉しさは
101010
 という感じです。
このように，相性が良かったり，逆に悪かったりする状況も考えられるので，必ずしも
f({1})+f({2})=f({1,2})f(\{1\})+f(\{2\})=f(\{1,2\})f({1})+f({2})=f({1,2})
 が成立するとは限りません。
集合関数を使えば様々な状況が記述できそうですね。

劣モジュラ性の定義1

任意の $A\:(\subseteq E)$ と $i,j\in E\setminus A$ に対して

$f(A+i)-f(A)\\\geq f(A+i+j)-f(A+j)$

が成立するとき，集合関数 $f$ は劣モジュラ関数であると言う。

なお， $A\cup \{i\}$ のことを $A+i$ などと書いています。

定義1の式は限界効用逓減性とも呼ばれます。ざっくり言うと同じもの $i$ をもらうときには，裕福な人（ $A+j$ を持っている人）よりも貧しい人（ $A$ だけ持っている人）の方が幸せに感じるという性質です。

みなさんも，日々生活している中で「限界効用逓減してるなあ」と感じる瞬間があるはずです（例えば，1杯目のおかわりの方が2杯目のおかわりより嬉しいとか）。

劣モジュラ性の定義2

任意の $A,B\:(\subseteq E)$ に対して

$f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$

が成立するとき，集合関数 $f$ は劣モジュラ関数であると言う。

なお，不等号が等号で成立するとき「モジュラ関数」，逆向きで成立するとき「優モジュラ関数」と言います。

定義1と定義2が同値であることは比較的簡単に証明できます。特に2→1が簡単なのでこちらだけやっておきます。

定義2→定義1

定義2の不等式において $A$ を $A+i$ ， $B$ を $A+j$ とすると，

$f(A+i)+f(A+j)\geq f(A+i+j)+f(A)$

これを移項すると，

$f(A+i)-f(A)\geq f(A+i+j)-f(A+j)$

となり定義1の不等式を得る。

逆向きもやってみてください！

劣モジュラ性がなぜ嬉しいのか

1．世の中には劣モジュラ性を持つ集合関数がたくさんある。
例えば，
線形関数
グラフのカット関数
行列のランク（より一般にマトロイドのランク）
2．劣モジュラ関数の最適化問題は幅広く研究されている
特に，劣モジュラ関数の最小化は多項式時間でできます！（Schrijver 2000, Iwata-Fleischer-Fujishige 2001）
一方，劣モジュラ関数の最大化はNP困難です。
このような話題が面白いと感じる方へ：離散数学という分野も検討してみてはいかがでしょうか。

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！