Subadditive set function

Let ${\displaystyle \Omega }$ be a set and ${\displaystyle f\colon 2^{\Omega }\rightarrow \mathbb {R} }$ be a set function, where ${\displaystyle 2^{\Omega }}$ denotes the power set of ${\displaystyle \Omega }$. The function f is subadditive if for each subset ${\displaystyle S}$ and ${\displaystyle T}$ of ${\displaystyle \Omega }$, we have ${\displaystyle f(S)+f(T)\geq f(S\cup T)}$.[1][2]

Every non-negative submodular set function is subadditive (the family of non-negative submodular functions is strictly contained in the family of subadditive functions).

The function that counts the number of sets required to cover a given set is subadditive. Let ${\displaystyle T_{1},\dotsc ,T_{m}\subseteq \Omega }$ such that ${\displaystyle \cup _{i=1}^{m}T_{i}=\Omega }$. Define ${\displaystyle f}$ as the minimum number of subsets required to cover a given set. Formally, ${\displaystyle f(S)}$ is the minimum number ${\displaystyle t}$ such that there are sets ${\displaystyle T_{i_{1}},\dotsc ,T_{i_{t}}}$ satisfying ${\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}}$. Then ${\displaystyle f}$ is subadditive.

The maximum of additive set functions is subadditive (dually, the minimum of additive functions is superadditive). Formally, for each ${\displaystyle i\in \{1,\dotsc ,m\}}$, let ${\displaystyle a_{i}\colon \Omega \to \mathbb {R} _{+}}$ be additive set functions. Then ${\displaystyle f(S)=\max _{i}\left(\sum _{x\in S}a_{i}(x)\right)}$ is a subadditive set function.

Fractionally subadditive set functions are a generalization of submodular functions and a special case of subadditive functions. A subadditive function ${\displaystyle f}$ is furthermore fractionally subadditive if it satisfies the following definition.[1] For every ${\displaystyle S\subseteq \Omega }$, every ${\displaystyle X_{1},\dotsc ,X_{n}\subseteq \Omega }$, and every ${\displaystyle \alpha _{1},\dotsc ,\alpha _{n}\in [0,1]}$, if ${\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}}$, then ${\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})}$. The set of fractionally subadditive functions equals the set of functions that can be expressed as the maximum of additive functions, as in the example in the previous paragraph.[1]

• Submodular set function
• Utility functions on indivisible goods