Supermodular function

In mathematics, a function

f\colon \mathbb {R} ^{k}\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} ^{k}$ , where $x\uparrow y$ denotes the componentwise maximum and $x\downarrow y$ the componentwise minimum of $x$ and $y$ .

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]

{\frac {\partial ^{2}f}{\partial z_{i}\,\partial z_{j}}}\geq 0{\mbox{ for all }}i\neq 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 $\,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.^[2] This is the basic property underlying examples of multiple equilibria in coordination games.^[3]

The opposite case of submodularity of $\,f$ 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.^[4]

Supermodular 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 $f\colon 2^{S}\to \mathbb {R}$ is supermodular if for any $A\subset B\subset S$ and $x\in S\setminus B$ , $f(A\cup \{x\})-f(A)\leq f(B\cup \{x\})-f(B)$ . For submodularity, the inequality is reversed.

The definition of supermodularity can equivalently be formulated as

f(A)+f(B)\leq f(A\cap B)+f(A\cup B)

for all subsets A and B of S.

Notes and references

↑ The equivalence between the definition of supermodularity and its calculus formulation is sometimes called Topkis' characterization theorem. See Milgrom, Paul; Roberts, John (1990). "Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities". Econometrica. 58 (6): 1255–1277 [p. 1261]. JSTOR 2938316.
↑ Bulow, Jeremy I.; Geanakoplos, John D.; Klemperer, Paul D. (1985). "Multimarket Oligopoly: Strategic Substitutes and Complements". Journal of Political Economy. 93 (3): 488–511. doi:10.1086/261312.
↑ Cooper, Russell; John, Andrew (1988). "Coordinating coordination failures in Keynesian models". Quarterly Journal of Economics. 103 (3): 441–463. doi:10.2307/1885539.
↑ Chambers, Christopher P.; Echenique, Federico (2009). "Supermodularity and preferences". Journal of Economic Theory. 144 (3): 1004. doi:10.1016/j.jet.2008.06.004.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Supermodular function

Supermodularity in economics and game theory

Supermodular functions of subsets

See also

Notes and references