Subadditive and superadditive set functions

Dependencies:

1. Set function

A set function $f: 2^Ω → ℝ$ is subadditive iff $f(A ∪ B) ≤ f(A) + f(B)$ for all disjoint sets $A$ and $B$. $f$ is superadditive iff $f(A ∪ B) ≥ f(A) + f(B)$ for all disjoint sets $A$ and $B$.

$f$ is subadditive iff $-f$ is superadditive.

Equivalently, $f$ is subadditive iff $f(B \mid A) ≤ f(B)$ for all disjoint sets $A$ and $B$, and superadditive iff $f(B \mid A) ≥ f(B)$ for all disjoint sets $A$ and $B$.

Dependency for:

1. A set function is additive iff it is submodular and supermodular iff it is subadditive and superadditive.
2. Submodularity implies subadditivity, supermodularity implies superadditivity
3. EFX implies PROPm
4. MEFS implies PROP for subadditive valuations
5. EF1 implies PROP1
6. PROP implies WMMS and pessShare
7. PROP implies EF for n=2
8. PROP implies EF for superadditive identical valuations
9. PROP-unsat implies someone is superPROP

Info:

• Depth: 3
• Number of transitive dependencies: 3

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function