劣加法集合関数

数学において、劣加法集合関数とは、その値が、非公式には、2 つの集合の和集合上の関数の値が、各集合上の関数の値の合計以下であるという特性を持つ集合関数です。これは、実数値関数の 劣加法性特性と主題的に関連しています。

を集合、を集合関数とする。ここで は の冪集合を表す。関数fが劣加法であるとは、 の各部分集合および に対して が成り立つことを意味する。[ 1 ^{] [2]}${\displaystyle \オメガ}$${\displaystyle f\colon 2^{\Omega }\rightarrow \mathbb {R} }$${\displaystyle 2^{\Omega}}$${\displaystyle \オメガ}$${\displaystyle S}$${\displaystyle T}$${\displaystyle \オメガ}$${\displaystyle f(S)+f(T)\geq f(S\cup T)}$

すべての非負サブモジュラ集合関数は劣加法です (非負サブモジュラ関数の族は、劣加法関数の族に厳密に含まれます)。

与えられた集合をカバーするために必要な集合の数を数える関数は劣加法的です。 となる とします。を、与えられた集合をカバーするために必要な部分集合の最小数 と定義します。正式には、を満たす集合が存在する最小の数です。この場合、は劣加法的です。 ${\displaystyle T_{1},\dotsc ,T_{m}\subseteq \Omega }$${\displaystyle \cup _{i=1}^{m}T_{i}=\Omega }$${\displaystyle f}$${\displaystyle f(S)}$${\displaystyle t}$${\displaystyle T_{i_{1}},\dotsc ,T_{i_{t}}}$${\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}}$${\displaystyle f}$

加法集合関数の最大値は劣加法 です（双対的に、加法関数の最小値は優加法です）。正式には、各 に対して、を加法集合関数とします。この場合、は劣加法集合関数です。 ${\displaystyle i\in \{1,\dotsc ,m\}}$${\displaystyle a_{i}\colon \Omega \to \mathbb {R} _{+}}$${\displaystyle f(S)=\max _{i}\left(\sum _{x\in S}a_{i}(x)\right)}$

分数劣加法集合関数は、劣モジュラ関数の一般化であり、劣加法関数の特殊なケースです。さらに、劣加法関数は、次の定義を満たす場合、分数劣加法です。^[1]すべての、すべての、すべてのについて、 であれば です。分数劣加法関数の集合は、前の段落の例のように、加法関数の最大値として表現できる関数の集合に等しくなります。^[1]${\displaystyle f}$${\displaystyle S\subseteq \Omega }$${\displaystyle X_{1},\dotsc ,X_{n}\subseteq \Omega }$${\displaystyle \alpha _{1},\dotsc ,\alpha _{n}\in [0,1]}$${\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}}$${\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})}$

• 劣モジュラー集合関数
• 分割不可能な財に関する効用関数