Supermodular function: Difference between revisions

Revision as of 15:17, 22 December 2024

Revision as of 20:55, 19 February 2025

Line 2:

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

=== Definition ===

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

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

Line 39:

=== Definition ===

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=Submodular Function Minimization |date=2005 |series=Handbooks in Operations Research and Management Science |volume=12 |pages=321–391 |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>.