超模函数

超模函数（supermodular function）是边际增量随背景集合扩大而不减的集合函数。它可刻画组合后的互补：已有成员越多，新成员可与它们形成的协作对越多。超模性的准确含义是并交不等式，不能仅凭“规模更大收益更高”判断。

在一个三人合作网络中，顶点为 $a,b,c$，潜在合作边是 $ab,bc$，每条已启用合作边贡献一。令 $h(S)$ 统计两端都属于所选成员 $S$ 的边数。单独加入 $b$ 没有合作收益；已有 $a$ 时加入 $b$ 增加一；已有 $a,c$ 时加入 $b$ 增加二。增加的是新成员与已有成员之间被一并启用的边。

定义及符号变换

有限底集为 $E$，函数 $h:2^E\to ℝ$ 称为超模，如果对任意 $A,B\subseteq E$， $$h(A)+h(B)\le h(A\cup B)+h(A\cap B).$$ 它等价于对任意 $A\subseteq B$ 及 $e\notin B$ 有 $$h(A+e)-h(A)\le h(B+e)-h(B).$$ 这里 $A+e$ 简记 $A\cup \{e\}$。两种表述等价，可以将次模函数的并交—边际证明全部反向；也可以直接对 $-h$ 应用已证明的等价性。

逐项乘以负一立即得到：$h$ 超模当且仅当 $-h$ 次模。这个变换会反转最大化与最小化的目标方向。对集合取补则不会反转次模与超模：若 $g(S)=h(E\setminus S)$，德摩根律只是交换并与交的位置，所以 $g$ 仍超模。把“负号”和“补集”混淆会导致错误的优化结论。

内部边权的完整证明

更一般地，设 $G=(V,F)$ 为有限无向简单图、$w_{uv}\ge 0$，定义 $$h(S)=\sum _{uv\in F,u,v\in S}{w}_{uv},S\subseteq V.$$ 加入 $v\notin S$ 仅会新增连接 $v$ 与 $S$ 的边，因此 $$h(S+v)-h(S)=\sum _{u\in S:uv\in F}{w}_{uv}.$$ 若 $A\subseteq B$，右端从 $A$ 到 $B$ 只增加非负项，所以边际递增，证明了超模性。非负性还保证本例单调，但这个单调结论来自权重条件，不是超模定义的自动结果。

背景集合扩大后，加入 b 可以同时启用两条合作边。

在三人例中取 $A=\{a,b\}$、$B=\{b,c\}$。有 $h(A)=h(B)=1$，$h(A\cup B)=2$、$h(A\cap B)=0$，本次恰取等号。取 $A=\{a\}$、$B=\{b\}$ 则为 $0+0<1+0$，严格反映两人同时在场才产生的收益。

也可通过计数配对构造超模函数 $q(S)=(\genfrac{}{}{0ex}{}{|S|}{2})$。向含 $k$ 个成员的集合加入一人，新增 $k$ 对，故边际随 $k$ 增大。若只用“集合越大函数越大”判断，则无法区分 $q$ 与同样单调的覆盖函数；后者的边际反而递减。

条件变化与反例

变式。 给路径边赋权 $w_{ab}=2,w_{bc}=3$。向 $\{a\}$ 加入 $b$ 增加二；向 $\{a,c\}$ 加入 $b$ 增加五。取 $A=\{a\},B=\{b,c\}$，并交式为 $0+3\le 5+0$。两个计算分别检验了边际定义与并交定义。

若只有一条权为负一的边 $ab$，内部边权函数的边际在空背景为零，在 $\{a\}$ 背景为负一，违反 $0\le -1$，所以非负边权不能删去。不过超模函数本身可以下降，例如 $h(S)=-|S|$ 是模函数，因此同时次模和超模，却严格随包含下降。

超模函数若单调非减且不附加约束，最大值当然在全集达到；若存在预算、容量或恰选若干人的限制，原来的结论便不能直接使用。特别是对超模函数做最大化，等价于对其次模负函数做最小化并保留同一约束；不能因无约束次模最小化的已知算法，就省略约束所带来的难点。