Función supermodular

En matemáticas, una función supermodular es una función en un retículo que, informalmente, se caracteriza por tener "diferencias crecientes". Desde la perspectiva de las funciones de conjunto , esto también puede interpretarse como una relación de "rendimientos crecientes", donde añadir más elementos a un subconjunto aumenta su valor. En economía , las funciones supermodulares se utilizan a menudo como expresión formal de la complementariedad en las preferencias entre bienes. Estas funciones se estudian y tienen aplicaciones en la teoría de juegos , la economía , la teoría de retículos , la optimización combinatoria y el aprendizaje automático .

Dejar${\displaystyle (X,\preceq )}$ser una red . Una función de valor real${\displaystyle f:X\rightarrow \mathbb {R} }$se denomina supermodular si ${\displaystyle f(x\vee y)+f(x\wedge y)\geq f(x)+f(y)}$

a pesar de${\displaystyle x,y\in X}$. ^{[ 1 ]}

Si la desigualdad es estricta, entonces${\displaystyle f}$es estrictamente supermodular en${\displaystyle X}$. Si${\displaystyle -f}$Si f es (estrictamente) supermodular, entonces se denomina ( estrictamente) submodular . Una función que es a la vez submodular y supermodular se denomina modular . Esto corresponde a que la desigualdad se convierta en una igualdad.

También podemos definir funciones supermodulares donde la red subyacente es el espacio vectorial.${\displaystyle \mathbb {R} ^{n}}$. Luego la función ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$es supermodular si

${\displaystyle f(x\uparrow y)+f(x\downarrow y)\geq f(x)+f(y)}$

a pesar de${\displaystyle x}$,${\displaystyle y\in \mathbb {R} ^{n}}$, dónde${\displaystyle x\uparrow y}$denota el máximo por componentes y${\displaystyle x\downarrow y}$el mínimo por componentes de${\displaystyle x}$y${\displaystyle y}$.

Si f es dos veces continuamente diferenciable, entonces la supermodularidad es equivalente a la condición ^{[ 2 ].}

${\displaystyle {\frac {\partial ^{2}f}{\partial z_{i}\,\partial z_{j}}}\geq 0{\mbox{ para todo }}i\neq j.}$

El concepto de supermodularidad se utiliza en las ciencias sociales para analizar cómo la decisión de un agente afecta los incentivos de los demás.

Consideremos un juego simétrico con una función de pago suave.${\displaystyle \,f}$definido sobre acciones${\displaystyle \,z_{i}}$de dos o más jugadores${\displaystyle i\in {1,2,\dots ,N}}$Supongamos que el espacio de acciones es continuo; para simplificar, supongamos que cada acción se elige de un intervalo:${\displaystyle z_{i}\in [a,b]}$. En este contexto, la supermodularidad de${\displaystyle \,f}$implica que un aumento en el jugador${\displaystyle \,i}$la elección${\displaystyle \,z_{i}}$aumenta la ganancia marginal${\displaystyle df/dz_{j}}$de acción${\displaystyle \,z_{j}}$para todos los demás jugadores${\displaystyle \,j}$. Es decir, si algún jugador${\displaystyle \,i}$elige uno superior${\displaystyle \,z_{i}}$, todos los demás jugadores${\displaystyle \,j}$tienen un incentivo para elevar sus opciones${\displaystyle \,z_{j}}$También. Siguiendo la terminología de Bulow, Geanakoplos y Klemperer (1985), los economistas llaman a esta situación complementariedad estratégica , porque las estrategias de los jugadores se complementan entre sí. ^{[ 3 ]} Esta es la propiedad básica que subyace a los ejemplos de equilibrios múltiples en juegos de coordinación . ^{[ 4 ]}

El caso opuesto de supermodularidad de${\displaystyle \,f}$, denominada submodularidad, corresponde a la situación de sustituibilidad estratégica . Un aumento en${\displaystyle \,z_{i}}$reduce la recompensa marginal para todas las demás opciones del jugador.${\displaystyle \,z_{j}}$, por lo tanto, las estrategias son sustitutas. Es decir, si${\displaystyle \,i}$elige uno superior${\displaystyle \,z_{i}}$, otros jugadores tienen un incentivo para elegir una opción más baja${\displaystyle \,z_{j}}$.

Por ejemplo, Bulow et al. analizan las interacciones de numerosas empresas en competencia imperfecta . Cuando un aumento en la producción de una empresa incrementa los ingresos marginales de las demás, las decisiones de producción son estratégicamente complementarias. Por el contrario, cuando un aumento en la producción de una empresa reduce los ingresos marginales de las demás, las decisiones de producción son estratégicamente sustitutivas.

Una función de utilidad supermodular suele estar relacionada con bienes complementarios . Sin embargo, esta visión es controvertida. ^{[ 5 ]}

La supermodularidad también puede definirse para funciones de conjunto , que son funciones definidas sobre subconjuntos de un conjunto mayor. Muchas propiedades de las funciones de conjunto submodulares pueden reformularse para aplicarse a las funciones de conjunto supermodulares.

Intuitivamente, una función supermodular sobre un conjunto de subconjuntos demuestra "rendimientos crecientes". Esto significa que si a cada subconjunto se le asigna un número real que corresponde a su valor, el valor de un subconjunto siempre será menor que el valor de un subconjunto mayor que lo contiene. En otras palabras, a medida que agregamos elementos a un conjunto, aumentamos su valor.

Existen técnicas especializadas para optimizar funciones submodulares. La teoría y los algoritmos de enumeración para encontrar máximos (mínimos) locales y globales de funciones submodulares (supermodulares) se pueden encontrar en "Maximización de funciones submodulares: Teoría y algoritmos de enumeración", B. Goldengorin. ^{[ 7 ]}

• Función pseudobooleana
• Teorema de Topkis
• Función de conjunto submodular
• Superaditivo
• Funciones de utilidad sobre bienes indivisibles