Supermodular function#Supermodular functions of subsets

Let $(X,\; \backslash preceq)$ be a lattice. A real-valued function $f:\; X\; \backslash rightarrow\; \backslash mathbb\{R\}$ is called supermodular if

$f(x\; \backslash vee\; y)\; +\; f(x\; \backslash wedge\; y)\; \backslash geq\; f(x)\; +\; f(y)$

for all $x,\; y\; \backslash in\; X$.{{Cite book |title=Supermodularity and complementarity |date=1998 |publisher=Princeton University Press |isbn=978-0-691-03244-3 |editor-last=Topkis |editor-first=Donald M. |series=Frontiers of economic research |location=Princeton, N.J}}

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 $\backslash mathbb\{R\}^n$. Then the function $f\; :\; \backslash mathbb\{R\}^n\; \backslash to\; \backslash mathbb\{R\}$ is supermodular if

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

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

If f is twice continuously differentiable, then supermodularity is equivalent to the conditionThe equivalence between the definition of supermodularity and its calculus formulation is sometimes called Topkis' characterization theorem. See {{cite journal |first1=Paul |last1=Milgrom |first2=John |last2=Roberts |year=1990 |title=Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities |journal=Econometrica |volume=58 |issue=6 |pages=1255–1277 [p. 1261] |jstor=2938316 |doi=10.2307/2938316 }}

:$\backslash frac\{\backslash partial\; ^2\; f\}\{\backslash partial\; z\_i\backslash ,\; \backslash partial\; z\_j\}\; \backslash geq\; 0\; \backslash mbox\{\; for\; all\; \}\; i\; \backslash neq\; j.$

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 $\backslash ,f$ defined over actions $\backslash ,z\_i$ of two or more players $i\; \backslash in\; \{1,2,\backslash dots,N\}$. Suppose the action space is continuous; for simplicity, suppose each action is chosen from an interval: $z\_i\; \backslash in\; [a,b]$. In this context, supermodularity of $\backslash ,f$ implies that an increase in player $\backslash ,i$'s choice $\backslash ,z\_i$ increases the marginal payoff $df/dz\_j$ of action $\backslash ,z\_j$ for all other players $\backslash ,j$. That is, if any player $\backslash ,i$ chooses a higher $\backslash ,z\_i$, all other players $\backslash ,j$ have an incentive to raise their choices $\backslash ,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.{{cite journal |first1=Jeremy I. |last1=Bulow |first2=John D. |last2=Geanakoplos |first3=Paul D. |last3=Klemperer |year=1985 |title=Multimarket Oligopoly: Strategic Substitutes and Complements |journal=Journal of Political Economy |volume=93 |issue=3 |pages=488–511 |doi=10.1086/261312 |citeseerx=10.1.1.541.2368 |s2cid=154872708 }} This is the basic property underlying examples of multiple equilibria in coordination games.{{cite journal |first1=Russell |last1=Cooper |first2=Andrew |last2=John |year=1988 |title=Coordinating coordination failures in Keynesian models |journal=Quarterly Journal of Economics |volume=103 |issue=3 |pages=441–463 |doi=10.2307/1885539 |jstor=1885539 |url=http://cowles.yale.edu/sites/default/files/files/pub/d07/d0745-r.pdf }}

The opposite case of supermodularity of $\backslash ,f$, called submodularity, corresponds to the situation of strategic substitutability. An increase in $\backslash ,z\_i$ lowers the marginal payoff to all other player's choices $\backslash ,z\_j$, so strategies are substitutes. That is, if $\backslash ,i$ chooses a higher $\backslash ,z\_i$, other players have an incentive to pick a lower $\backslash ,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.{{Cite journal|doi=10.1016/j.jet.2008.06.004 |title=Supermodularity and preferences |journal=Journal of Economic Theory |volume=144 |issue=3 |pages=1004 |year=2009 |last1=Chambers |first1=Christopher P. |last2=Echenique |first2=Federico |citeseerx=10.1.1.122.6861 }}

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.

Let $S$ be a finite set. A set function $f:\; 2^S\; \backslash to\; \backslash mathbb\{R\}$ is supermodular if it satifies the following (equivalent) conditions:{{Citation |last=McCormick |first=S. Thomas |title=Discrete Optimization |chapter=Submodular Function Minimization |date=2005 |series=Handbooks in Operations Research and Management Science |volume=12 |pages=321–391 |chapter-url=https://linkinghub.elsevier.com/retrieve/pii/S0927050705120076 |access-date=2024-12-12 |publisher=Elsevier |language=en |doi=10.1016/s0927-0507(05)12007-6 |isbn=978-0-444-51507-0}}

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

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

• 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.

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.{{Cite journal |last=Goldengorin |first=Boris |date=2009-10-01 |title=Maximization of submodular functions: Theory and enumeration algorithms |url=https://www.sciencedirect.com/science/article/pii/S0377221708007418 |journal=European Journal of Operational Research |language=en |volume=198 |issue=1 |pages=102–112 |doi=10.1016/j.ejor.2008.08.022 |issn=0377-2217|url-access=subscription }}

• Pseudo-Boolean function
• Topkis's theorem
• Submodular set function
• Superadditive
• Utility functions on indivisible goods

{{Reflist}}

{{DEFAULTSORT:Supermodular Function}}

Category:Order theory

Category:Optimization of ordered sets

Category:Generalized convexity

Category:Supermodular functions