Encyclopedia

Supermodular function

Class of mathematical functions

Wikipedia contributorsAdapted for Fathomly · View authors

3 min read
Source updated July 30, 2026

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.

01Definition

Let $(X,\preceq )$ be a lattice. A real-valued function $f:X\rightarrow \mathbb {R}$ is called supermodular if $f(x\vee y)+f(x\wedge y)\geq f(x)+f(y)$

for all $x,y\in X$ .

If the inequality is strict, then $f$ is strictly supermodular on $X$ . If $-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 $\mathbb {R} ^{n}$ . Then the function $f:\mathbb {R} ^{n}\to \mathbb {R}$ is supermodular if

$f(x\uparrow y)+f(x\downarrow y)\geq f(x)+f(y)$

for all $x$ , $y\in \mathbb {R} ^{n}$ , where $x\uparrow y$ denotes the componentwise maximum and $x\downarrow y$ the componentwise minimum of $x$ and $y$ .

If f is twice continuously differentiable, then supermodularity is equivalent to the condition

${\frac {\partial ^{2}f}{\partial z_{i}\,\partial z_{j}}}\geq 0{\mbox{ for all }}i\neq j.$

02Supermodularity in economics and game theory

The concept of supermodularity is used in the social sciences to analyze how one agent's decision affects the incentives of others.

Consider a symmetric game with a smooth payoff function $\,f$ defined over actions $\,z_{i}$ of two or more players $i\in {1,2,\dots ,N}$ . Suppose the action space is continuous; for simplicity, suppose each action is chosen from an interval: $z_{i}\in [a,b]$ . In this context, supermodularity of $\,f$ implies that an increase in player $\,i$ 's choice $\,z_{i}$ increases the marginal payoff $df/dz_{j}$ of action $\,z_{j}$ for all other players $\,j$ . That is, if any player $\,i$ chooses a higher $\,z_{i}$ , all other players $\,j$ have an incentive to raise their choices $\,z_{j}$ too. Following the terminology of Bulow, Geanakoplos, and Klemperer (1985), economists call this situation strategic complementarity, because players' strategies are complements to each other. This is the basic property underlying examples of multiple equilibria in coordination games.

The opposite case of supermodularity of $\,f$ , called submodularity, corresponds to the situation of strategic substitutability. An increase in $\,z_{i}$ lowers the marginal payoff to all other player's choices $\,z_{j}$ , so strategies are substitutes. That is, if $\,i$ chooses a higher $\,z_{i}$ , other players have an incentive to pick a lower $\,z_{j}$ .

For example, Bulow et al. consider the interactions of many imperfectly competitive firms. When an increase in output by one firm raises the marginal revenues of the other firms, production decisions are strategic complements. When an increase in output by one firm lowers the marginal revenues of the other firms, production decisions are strategic substitutes.

A supermodular utility function is often related to complementary goods. However, this view is disputed.

03Supermodular set functions

Supermodularity can also be defined for set functions, which are functions defined over subsets of a larger set. Many properties of submodular set functions can be rephrased to apply to supermodular set functions.

Intuitively, a supermodular function over a set of subsets demonstrates "increasing returns". This means that if each subset is assigned a real number that corresponds to its value, the value of a subset will always be less than the value of a larger subset which contains it. Alternatively, this means that as we add elements to a set, we increase its value.

Definition

Let $S$ be a finite set. A set function $f:2^{S}\to \mathbb {R}$ is supermodular if it satisfies the following (equivalent) conditions:

$f(A)+f(B)\leq f(A\cap B)+f(A\cup B)$ for all $A,B\subseteq S$ .
$f(A\cup \{v\})-f(A)\leq f(B\cup \{v\})-f(B)$ for all $A\subset B\subset V$ , where $v\notin B$ .

A set function $f$ is submodular if $-f$ is supermodular, and modular if it is both supermodular and submodular.

Additional Facts

If $f$ is modular and $g$ is submodular, then $f-g$ is a supermodular function.
A non-negative supermodular function is also a superadditive function.

04Optimization Techniques

There are specialized techniques for optimizing submodular functions. Theory and enumeration algorithms for finding local and global maxima (minima) of submodular (supermodular) functions can be found in "Maximization of submodular functions: Theory and enumeration algorithms", B. Goldengorin.

Watch videos about Supermodular functionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Supermodular function”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Supermodular function

01Definition

02Supermodularity in economics and game theory

03Supermodular set functions

Definition

Additional Facts

04Optimization Techniques

Sources and credits

Related topics

Pseudo-Boolean function

Topkis's theorem

Submodular set function