2015/05/14

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

分野: 集合,命題,論証  レベル: 大学数学

集合関数と劣モジュラ性についての基本事項を解説します。

集合関数

今回は,以下のような実数値集合関数 $f$ を扱います。
入力:集合。台集合 $E$ の部分集合ならなんでもOK。
出力:実数。

台集合を $E=\{1,2\}$ とすると,入力として考えられるのは4通り。例えば,集合関数 $f$ の例としては,
$f(\emptyset)=0$,$f(\{1\})=3$,$f(\{2\})=1$,$f(\{1,2\})=10$
なるものが考えられる。

1が米,2が明太子,$f$ は効用(嬉しさ)を表すものと考えてみましょう。米だけある嬉しさは $3$,明太子だけだと $1$,両方あると相性抜群なので嬉しさは $10$ という感じです。

このように,相性が良かったり,逆に悪かったりする状況も考えられるので,必ずしも $f(\{1\})+f(\{2\})=f(\{1,2\})$ が成立するとは限りません。

集合関数を使えば様々な状況が記述できそうですね。

劣モジュラ性の定義1

任意の $A\:(\subseteq E)$ と $i,j\in E\backslash 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困難です。

このような話題が面白いと感じる方へ:離散数学という分野も検討してみてはいかがでしょうか。
分野: 集合,命題,論証  レベル: 大学数学