Supermodular function: Difference between revisions

Revision as of 00:36, 16 July 2017

Revision as of 12:17, 7 August 2017

Line 1:

In [[mathematics]], a function

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

is '''supermodular''' if

:<math>

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

</math>

for all ''x'', ''y'' <math>\isin x</math>, ''R''<supmath>''y \isin \mathbb{R}^{k''}</supmath>, where ''x'' <math>x \uparrow y</math> ''y'' denotes the componentwise maximum and ''x'' <math>x \downarrow 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 twice 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 |first=Paul |last=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 1261[p. 1261] |jstor=2938316 }}</ref>

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

Line 16:

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>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 |first=Jeremy I. |last=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 488&ndash;511|pages=488–511 |doi=10.1086/261312 }}</ref> This is the basic property underlying examples of [[General equilibrium#Uniqueness|multiple equilibria]] in [[coordination game]]s.<ref>{{cite journal |first=Russell |last=Cooper and |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 441&ndash;63|doi=10.2307/1885539 }}</ref>

The opposite case of submodularity of <math>\,f</math> 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>.

Line 23:

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 }}</ref>

==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 <math>f\colon 2^S \to \mathbb{R}</math> is supermodular 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) \leq f(B \cup \{x\})-f(B)</math>. For submodularity, the inequality is reversed.

<!--

A simple illustrative 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.