Submodular function

Dependencies:

  1. Set function

$f: 2^{\Omega} \to \mathbb{R}$ be a function. Then $f$ is submodular iff it satisfies one of the following equivalent conditions:

  1. $\forall Y \subseteq \Omega, \forall X \subseteq Y, \forall Z \in \Omega \setminus Y,$ $f(Z \mid X) \ge f(Z \mid Y)$.
  2. $\forall P \subseteq \Omega, \forall Q \subseteq \Omega,$ $f(P) + f(Q) \ge f(P \cup Q) + f(P \cap Q)$.

$f$ is said to be supermodular if $-f$ is submodular.

Proof of equivalence of definitions

Definition 1 implies definition 2 if we let $Y = P$, $X = P \cap Q$ and $Z = Q - P$.

Definition 2 implies definition 1 if we let $P = X \cup Z$ and $Q = Y$.

Dependency for:

  1. Residual of submodular function is submodular
  2. Sum of submodular functions is submodular
  3. A set function is additive iff it is submodular and supermodular iff it is subadditive and superadditive.
  4. Submodularity implies subadditivity, supermodularity implies superadditivity
  5. Matroid: rank is submodular
  6. Matroid: weighted rank is submodular
  7. PROPm implies PROP1
  8. EFX implies EF1
  9. EFX
  10. PROPx
  11. PROP cake division doesn't exist for supermodular valuations
  12. PROP doesn't imply M1S for unit-demand valuations
  13. EF doesn't imply PROP for supermodular valuations

Info:

Transitive dependencies:

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