Supermodular function: Difference between revisions

Revision as of 18:27, 16 December 2017

Revision as of 22:18, 14 February 2018

Line 25:

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>

==SupermodularSubmodular 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 supermodularsubmodular 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 submodularitysupermodularity, 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.

-->

The definition of supermodularitysubmodularity can equivalently be formulated as

:<math> f(A)+f(B) \geq f(A \cap B) + f(A \cup B) </math>

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