Supermodular function

Dependencies:

1. Set function

$f: 2^{\Omega} \to \mathbb{R}$ be a function. Then $f$ is supermodular 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) \le f(Z \mid Y)$.
2. $\forall P \subseteq \Omega, \forall Q \subseteq \Omega,$ $f(P) + f(Q) \le f(P \cup Q) + f(P \cap Q)$.

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 supermodular function is also a superadditive function
2. A set function is additive iff it is submodular and supermodular iff it is subadditive and superadditive.
3. EFX implies EF1
4. EFX
5. PROPx
6. PROP cake division doesn't exist for supermodular valuations

Info:

• Depth: 3
• Number of transitive dependencies: 3

Transitive dependencies:

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