子模函数

边际效益递减

一般而言，消费者偏好某物而未能获得，或拥有数量不够大时，增加消费量则其满足感大增（边际效用增加）；但拥有数量足够时，再增加消费量则其满足感增加幅度逐渐平缓（边际效用递减）；拥有数量太多时，再增加消费量则反而感觉厌恶（边际效用减为负且继续递减，累积之总效用因此，亦减少）。在正常状况下，消费者拥有足够数量而边际效用递减后，会将有限资源配置转移以满足其他欲望，不至于消费同一商品过量到感觉厌恶。

简单来说，就是比如说，你在非常饿的时候，打开了一桶泡面，你吃下去的第一口给你带来的满足感是比吃了好几口之后给你带来的满足感要高的多的。

按照上面的这个例子，这个“边际”指的就是“当前吃的最后一口面”，“边际效益”指的是“当前这口面给你带来的满足感”。

Submodular Functions（子模函数）

存在一个集合 $E = {e_1, e_2, e_3, …,e_n}$

Definition 1

存在一个集合函数 $ f: 2^{E} \rightarrow \mathbf{R}_{+}$ ，如果对于任意的两个子集 $S\subseteq T \subseteq E$ ，$f$ 是一个子模函数当前仅当 $\forall {l}\in E \backslash T$，满足以下条件：
$$
f(T \cup{l})-f(T) \leq f(S \cup{l})-f(S)
$$

Definition 2

对于任意函数 $ f: 2^{E} \rightarrow \mathbf{R}_{+}$，该函数为单调非减函数，当且仅当满足：
$$
\forall S \subseteq T \subseteq E, f(S) \leq f(T)
$$

即对于一个子模函数而言，向小集合 $S$ 中添加元素 $l$ 所带来的的的边际效益 $f_S({l})$ 要大于向集合 $T$ 中添加元素 $l$ 所带来的边际效益 $f_T({l})$，这种特性也被称为边际效应递减，其中 $f_{S}({l})=f(S \cup{l})-f(S)$

这里面的“边际”就指的是“添加的元素 $l$”，“边际效益”指的是“ $f_S({l})$ 或 $f_T({l})$”。