Supermodular function: Difference between revisions

Revision as of 22:40, 29 March 2011

Latest revision as of 01:51, 24 May 2025

(41 intermediate revisions by 29 users not shown)

Line 1:

{{Short description|Class of mathematical functions}}

In [[mathematics]], a function

In mathematics, a '''supermodular function''' is a function on a [[Lattice (order)|lattice]] that, informally, has the property of being characterized by "increasing differences." Seen from the point of [[Set function|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 (order)|lattice theory]], [[combinatorial optimization]], and [[machine learning]].

:<math>f\colon R^k \to R</math>

is '''supermodular''' if

== Definition ==

:<math>

Let <math>(X, \preceq)</math> be a [[Lattice (order)|lattice]]. A real-valued function <math>f: X \rightarrow \mathbb{R}</math> is called '''supermodular''' if

f(x \lor y) + f(x \land y) \geq f(x) + f(y)

<math>f(x \vee y) + f(x \wedge y) \geq f(x) + f(y)</math>

for all <math>x, y \in X</math>.<ref>{{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}}</ref>

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

:<math>

f(x \loruparrow y) + f(x \landdownarrow y) \geq f(x) + f(y)

</math>

for all ''x'', ''y'' <math>\isin </math> ''R''^''k'', where ''x'' <math>\vee</math> ''y'' denotes the componentwise maximum and ''x'' <math>\wedge</math> ''y'' the componentwise minimum of ''x'' and ''y''.

for all ''<math>x''</math>, ''y'' <math>y \isin \mathbb{R}^{n}</math> ''R''^''k'', where ''x'' <math>x \veeuparrow y</math> ''y'' denotes the componentwise maximum and ''x'' <math>x \wedgedownarrow y</math> ''y'' the componentwise minimum of ''<math>x''</math> and ''<math>y''</math>.

If &minus;''f'' is supermodular then ''f'' is called '''submodular''', and if the inequality is changed to an equality the function is '''modular'''.

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

:<math> \frac{\partial ^2 f}{\partial z_i\, \partial z_j} \geq 0 \mbox{ for all } i \neq j.</math>

Line 16 ⟶ 25:

The concept of supermodularity is used in the social sciences to analyze how one [[Agent (economics)|agent's]] decision affects the incentives of others.

Consider a [[symmetric game]] with a smooth payoff function <math>\,f\,</math> defined over actions <math>\,z_i\,</math> of two or more players <math>i \in {1,2,\dots,N}</math>. Suppose the action space is continuous; for simplicity, suppose each action is chosen from an interval: <math>z_i \in [a,b]</math>. In this context, supermodularity of <math>\,f\,</math> implies that an increase in player <math>\,i\,</math>'s choice <math>\,z_i\,</math> increases the marginal payoff <math>\frac{df}{/dz_j}</math> of action <math>\,z_j\,</math> for all other players <math>\,j\,</math>. That is, if any player <math>\,i\,</math> chooses a higher <math>\,z_i\,</math>, all other players <math>\,j\,</math> have an incentive to raise their choices <math>\,z_j\,</math> too. Following the terminology of Bulow, [[John Geanakoplos|Geanakoplos]], and [[Paul Klemperer|Klemperer]] (1985), economists call this situation [[strategic complements|strategic complementarity]], because players' strategies are complements to each other.<ref>{{cite journal |first1=Jeremy I. |last1=Bulow, |first2=John D. |last2=Geanakoplos, and |first3=Paul D. |last3=Klemperer (|year=1985), '|title=Multimarket oligopolyOligopoly: strategicStrategic substitutesSubstitutes and strategicComplements complements'. ''|journal=[[Journal of Political Economy'']] |volume=93, pp|issue=3 |pages=488–511 |doi=10.1086/261312 488&ndash;511|citeseerx=10.1.1.541.2368 |s2cid=154872708 }}</ref> This is the basic property underlying examples of [[General equilibrium#Uniqueness|multiple equilibria]] in [[coordination game]]s.<ref>Russell{{cite Cooperjournal |first1=Russell and|last1=Cooper |first2=Andrew |last2=John (|year=1988), '|title=Coordinating coordination failures in Keynesian models.' ''|journal=[[Quarterly Journal of Economics'']] |volume=103 (|issue=3), pp|pages=441–463 |doi=10.2307/1885539 441&ndash;63|jstor=1885539 |url=http://cowles.yale.edu/sites/default/files/files/pub/d07/d0745-r.pdf }}</ref>

The opposite case of submodularitysupermodularity of <math>\,f\,</math>, called submodularity, corresponds to the situation of [[strategic complements|strategic substitutability]]. An increase in <math>\,z_i\,</math> lowers the marginal payoff to all other player's choices <math>\,z_j\,</math>, so strategies are substitutes. That is, if <math>\,i\,</math> chooses a higher <math>\,z_i\,</math>, other players have an incentive to pick a ''lower'' <math>\,z_j\,</math>.

For example, Bulow et al. consider the interactions of many [[Imperfect competition|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.<ref>{{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 }}</ref>

A standard reference on the subject is by Topkis<ref>Donald M. Topkis (1998), Supermodularity and Complementarity, Princeton University Press.</ref>.

==Supermodular set functions of subsets==

Supermodularity andcan submodularityalso are alsobe defined for [[Set function|set functions]], which are functions defined over subsets of a larger set. Many Intuitively,properties aof submodular[[Submodular set function|submodular overset thefunctions]] subsetscan demonstratesbe "diminishingrephrased returns".to apply Thereto aresupermodular specialized techniques for optimizing submodularset 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 function <math>f\colon 2^S \to R</math> is submodular if for any <math>A \subset B \subset S</math> and <math>x \in S \setminus B</math>, <math>f(A \cup \{x\})-f(A) \geq f(B \cup \{x\})-f(B)</math>. For supermodularity, the inequality is reversed.

=== Definition ===

A simple illustration example motivates this definition of submodular. Let S be a set of different foods, <math>M \subset S</math> a meal, and <math>f(M)</math> the "goodness" of that meal. Then A above is one meal, and B is A but with even more options. Let x be ice cream. Adding ice cream to a meal is always good, but it is best if there is not already a dessert. If A and B either both have a dessert or both do not, then adding ice cream to them is comparably good. But if A does not have dessert and B does, then the effect of adding ice cream is more pronounced in A.

Let <math>S</math> be a finite set. A set function <math>f: 2^S \to \mathbb{R}</math> is '''supermodular''' if it satifies the following (equivalent) conditions:<ref>{{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}}</ref>

# <math> f(A)+f(B) \leq f(A \cap B) + f(A \cup B) </math> for all <math> A, B \subseteq S </math>.

The definition of submodularity can equivalently be formulated as

:# <math> f(A \cup \{v\})+ - f(BA) \geqleq f(AB \capcup B\{v\}) +- f(B) </math> for all <math> A \cupsubset B \subset V </math>, where <math> v \notin B) </math>.

for all subsets ''A'' and ''B'' of ''S''.

A set function <math>f</math> is submodular if <math>-f</math> is supermodular, and modular if it is both supermodular and submodular.

=== Additional Facts ===

* If <math> f </math> is modular and <math> g </math> is submodular, then <math> f-g </math> is a supermodular function.

* A non-negative supermodular function is also a superadditive function.

== Optimization 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.<ref>{{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 }}</ref>

==See also==

* [[Pseudo-Boolean function]]

* [[Topkis's theorem]]

* [[Submodular set function]]

* [[Superadditive]]

* [[Utility functions on indivisible goods]]

==Notes and references==

{{Reflist}}

<references />

==External links==

{{DEFAULTSORT:Supermodular Function}}

[[Category:Order theory]]

[[Category:Optimization of ordered sets]]

[[Category:Generalized convexity]]

[[Category:Supermodular functions]]

[[fr:Fonction sous-modulaire]]

[[ru:Супермодулярность]]