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

Info:

Transitive dependencies:

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