Supermodular function

In mathematics, a supermodular function is a function on a lattice that, informally, has the property of being characterized by "increasing differences." Seen from the point of set functions, this can also be viewed as a relationship of "increasing returns", where adding more elements to a subset increases its valuation. In economics, supermodular functions are often used as a formal expression of complementarity in preferences among goods. Supermodular functions are studied and have applications in game theory, economics, lattice theory, combinatorial optimization, and machine learning.

Definition

Let

(

X

,

⪯

)

{\displaystyle (X,\preceq )}

be a lattice. A real-valued function

f

:

X

→

R

{\displaystyle f:X\rightarrow \mathbb {R} }

is called supermodular if

f

(

x

∨

y

)

+

f

(

x

∧

y

)

≥

f

(

x

)

+

f

(

y

)

{\displaystyle f(x\vee y)+f(x\wedge y)\geq f(x)+f(y)}

for all

x

,

y

∈

X

{\displaystyle x,y\in X}

.

If the inequality is strict, then

f

{\displaystyle f}

is strictly supermodular on

X

{\displaystyle X}

. If

−

f

{\displaystyle -f}

is (strictly) supermodular then f is called (strictly) submodular. A function that is both submodular and supermodular is called modular. This corresponds to the inequality being changed to an equality.

We can also define supermodular functions where the underlying lattice is the vector space

R

n

{\displaystyle \mathbb {R} ^{n}}

.