劣加法的集合函数

数学における劣加法的集合函数（れつかほうてきしゅうごうかんすう、英: subadditive set function）は、二つの集合の合併に対する値が、それぞれの集合に対する値の和で上から抑えられるような集合函数を言う。点函数が劣加法的となることに似ている。

劣モジュラー ⊂ 分割劣加法的 ⊂ 劣加法的

定義

集合 Ω 上の集合函数、すなわち Ω の冪集合 2^Ω を定義域とする写像 f: 2^Ω → B が劣加法的とは

$f(S\cup T)\leq f(S)+f(T)\quad (\forall S,T\subset \Omega )$

を満たすときに言う。終域 B は任意の順序集合にもとれるが、大抵は実数直線 R または非負実数直線 R₊ である。

例

• 任意の非負劣モジュラー集合函数は劣加法的集合函数である。劣モジュラー函数全体の成す集合は劣加法的函数全体の成す集合を真に含まれる。
• 与えられた集合 S を被覆するのに必要な集合の数を数える函数 f(S) は劣加法的である。具体的には、T₁, …, T_m ⊂ Ω で ${\textstyle \bigcup _{i=1}^{m}T_{i}=\Omega }$ となるものを固定する。f は各集合に対して、それを被覆するのに必要な T_i の最小数を割り当てるもの、すなわち
  $$f(S):=\min {\Bigl \{}t\mid \exists i_{1},\dotsc ,i_{t}{\text{ s.t. }}S\subset \bigcup _{j=1}^{t}T_{i_{j}}{\Bigr \}}$$
  とすれば、これは劣加法的になる。
• 任意の非負値加法的集合函数、特に測度は劣加法的である。
• より一般に、加法的函数のあつまり ã_i: 2^Ω → R₊ (i = 1, …, m) から引数ごとに最大のものをとる函数 f(S) ≔ max_i=1,…,m ã_i(S) (∀S ⊂ Ω) は劣加法的になる。
  • このような函数は、以下の性質によって特徴付けられる:

    分割的劣加法性

    各 S ⊂ Ω に対し、X₁, …, X_n ⊂ Ω および α₁, …, α_n ∈ [0, 1] が指示函数に関して 1_S ≤ ∑n
    i=1 α_i⋅1_Xi を満たすならば必ず、f(S) ≤ ∑n
    i=1 α_i⋅f(X_i) を満たす。

  • 分割的劣加法集合函数は劣モジュラー集合函数の一般化であり、かつ特別な種類の劣加法的集合函数である。

注

参考文献

• Feige, Uriel (2009年). “On Maximizing Welfare when Utility Functions are Subadditive”. SIAM Journal on Computing 39 (1): pp. 122–142. doi:10.1137/070680977 
• Dobzinski, Shahar; Nisan, Noam; Schapira, Michael (2010年). “Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders”. Mathematics of Operations Research 35 (1): pp. 1–13. doi:10.1145/1060590.1060681 

外部リンク

• Hazewinkel, Michiel, ed. (2001), “Subadditive function”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Subadditive_function