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

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

集合関数

今回は,以下のような実数値集合関数 ff を扱います。

  • 入力:集合。台集合 EE の部分集合ならなんでもOK。
  • 出力:実数。

台集合を E={1,2}E=\{1,2\} とすると,入力として考えられるのは4通り。例えば,集合関数 ff の例としては,

f()=0f(\emptyset)=0f({1})=3f(\{1\})=3f({2})=1f(\{2\})=1f({1,2})=10f(\{1,2\})=10

なるものが考えられる。

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

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

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

劣モジュラ性の定義1

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

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

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

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

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

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

劣モジュラ性の定義2

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

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

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

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

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

定義2→定義1

定義2の不等式において AAA+iA+iBBA+jA+j とすると,

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

これを移項すると,

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

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

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

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

1.世の中には劣モジュラ性を持つ集合関数がたくさんある。

例えば,

  • 線形関数
  • グラフのカット関数
  • 行列のランク(より一般にマトロイドのランク)

2.劣モジュラ関数の最適化問題は幅広く研究されている

特に,劣モジュラ関数の最小化は多項式時間でできます!(Schrijver 2000, Iwata-Fleischer-Fujishige 2001)

一方,劣モジュラ関数の最大化はNP困難です。

このような話題が面白いと感じる方へ:離散数学という分野も検討してみてはいかがでしょうか。