Intuition/illustration of difference between supermodularity and increasing differences of a function?

Question

Question: I am wondering if someone can explain to me the difference between these two concepts (or provide an illustration).

My thoughts I've been thinking about it and all I can come up with -- but not strongly convince myself of -- is that the difference might lie in the fact that the function can treat the join/meet of two points $x,y$ very different than it treats $x,y$. That it, i feel like supermodularity puts some restrictions on the upper/lower bounds that increasing differences doesn't.

Definitions: Let $(S,\leq)$ be a lattice and $g$ be a real valued function on $S$. Define $g$ to be supermodular on $S$ if for all $x,y \in S$ $$g(x\wedge y) + g(x\vee y) \geq g(x) + g(y)$$

Let $S$ and $T$ be lattices and $g:S\times T\to \mathbb{R}$. Define $g$ to have increasing differences in $(x,y)$ if for all $y\geq y'$ and $x\geq x'$, $$g(x,y)-g(x,y') \geq g(x',y)-g(x',y')$$

Answer 1

Supermodularity implies increasing differences. Increasing differences and supermodularity in each dimension implies supermodularity.

To be more precise, let me quote versions of two results from Topkis (1998). Fix a collection of lattices $\{X_i\}_{i\in I}$, and let $X$ be a sublattice of $\times_{i\in I}X_i$. $f$ maps $X$ into $\mathbb R$. In this setting, the definition of supermodularity is exactly the same, while the definition of increasing differences generalises naturally.

The first result is Topkis' theorem 2.6.1.

If $f$ is supermodular on $X$, then $f$ has increasing differences on $X$.

The next result is theorem 2.6.2.

Suppose that $I = \{1,2,\ldots,n \}$, and $f$ has increasing differences on $\times_{i=1}^n X_i$. If, for all $i$, $f(x)$ is supermodular in $x_{i}$ on $X_i$ for all fixed $x_j \in X_j$, $j \neq i$, then $f$ is supermodular on $\times_{i=1}^n X_i$.

Here is an example of a function that exhibits increasing differences but not supermodularity, also taken from Topkis.

Let $X_i = \{0,1 \}$ for $i=1,2,\ldots$, and $x=(x_1,x_2,\ldots) \in \times_{i=1}^\infty X_i$. Define $f$ so that $f(x)=1$ if $x_i = 1$ for an infinite set of indices $i$ and $f(x)=0$ otherwise. Since $f$ is constant with respect to any finite set of components of $x$, $f$ has increasing differences.

Let $x^\prime$ be such that $x_i^\prime = 1$ for $i$ odd, and $x_i^\prime = 0$ otherwise. Similarly, define $x^{\prime\prime}$ such that $x_i^{\prime\prime}=1$ for $i$ even and $x_i^{\prime\prime}=0$ for $i$ odd.

Then,

$$ f\left(x^\prime\right) + f\left(x^{\prime\prime}\right)= 2 > 1 = f\left(x^\prime \vee x^{\prime\prime}\right) + f\left(x^\prime \wedge x^{\prime\prime}\right), $$

so $f$ is not supermodular.

Admittedly, I don't find this example very enlightening. However, this might be because, as far as I can tell, for most practical purposes, supermodularity and increasing differences are essentially the same property.