Supermodular function explained
In mathematics, a function
is
supermodular if
f(x\uparrowy)+f(x\downarrowy)\geqf(x)+f(y)
for all
,
, where
denotes the componentwise maximum and
the componentwise minimum of
and
.
If -f is supermodular then f is called submodular, and if the inequality is changed to an equality the function is modular.
If f is twice continuously differentiable, then supermodularity is equivalent to the condition[1]
| \partial2f |
\partialzi\partialzj |
\geq0foralli ≠ j.
Supermodularity 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
defined over actions
of two or more players
. Suppose the action space is continuous; for simplicity, suppose each action is chosen from an interval:
. In this context, supermodularity of
implies that an increase in player
's choice
increases the marginal payoff
of action
for all other players
. That is, if any player
chooses a higher
, all other players
have an incentive to raise their choices
too. Following the terminology of Bulow,
Geanakoplos, and
Klemperer (1985), economists call this situation
strategic complementarity, because players' strategies are complements to each other.
[2] This is the basic property underlying examples of multiple equilibria in
coordination games.
[3] The opposite case of supermodularity of
, called submodularity, corresponds to the situation of
strategic substitutability. An increase in
lowers the marginal payoff to all other player's choices
, so strategies are substitutes. That is, if
chooses a higher
, other players have an incentive to pick a
lower
.
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.[4]
Submodular functions of subsets
Supermodularity and submodularity are also defined for functions defined over subsets of a larger set. Intuitively, a submodular function over the subsets demonstrates "diminishing returns". There are specialized techniques for optimizing submodular functions.
Let S be a finite set. A function
is submodular if for any
and
,
f(A\cup\{x\})-f(A)\geqf(B\cup\{x\})-f(B)
. For supermodularity, the inequality is reversed.
The definition of submodularity can equivalently be formulated as
f(A)+f(B)\geqf(A\capB)+f(A\cupB)
for all subsets
A and
B of
S.
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.[5]
See also
Notes and References
- The equivalence between the definition of supermodularity and its calculus formulation is sometimes called Topkis' characterization theorem. See Paul . Milgrom . John . Roberts . 1990 . Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities . . 58 . 6 . 1255–1277 [p. 1261] . 2938316 . 10.2307/2938316 .
- Jeremy I. . Bulow . John D. . Geanakoplos . Paul D. . Klemperer . 1985 . Multimarket Oligopoly: Strategic Substitutes and Complements . . 93 . 3 . 488–511 . 10.1086/261312 . 10.1.1.541.2368 . 154872708 .
- Russell . Cooper . Andrew . John . 1988 . Coordinating coordination failures in Keynesian models . . 103 . 3 . 441–463 . 10.2307/1885539 . 1885539 .
- 10.1016/j.jet.2008.06.004 . Supermodularity and preferences . . 144 . 3 . 1004 . 2009 . Chambers . Christopher P. . Echenique . Federico . 10.1.1.122.6861 .
- Goldengorin . Boris . 2009-10-01 . Maximization of submodular functions: Theory and enumeration algorithms . European Journal of Operational Research . en . 198 . 1 . 102–112 . 10.1016/j.ejor.2008.08.022 . 0377-2217.