Función supermodular

Clase de función matemática

En matemáticas , una función

${\displaystyle f\colon \mathbb {R} ^{k}\to \mathbb {R} }$

es supermodular si

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

para todos , , donde denota el máximo por componentes y el mínimo por componentes de y . ${\displaystyle x}$ ${\displaystyle y\in \mathbb {R} ^{k}}$ ${\displaystyle x\uparrow y}$ ${\displaystyle x\downarrow y}$ ${\displaystyle x}$ ${\displaystyle y}$

Si − f es supermodular entonces f se llama submodular , y si la desigualdad se cambia a igualdad la función es modular .

Si f es dos veces continuamente diferenciable, entonces la supermodularidad es equivalente a la condición ^[1]

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

Supermodularidad en economía y teoría de juegos.

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

Considere un juego simétrico con una función de pago uniforme definida sobre las acciones de dos o más jugadores . Supongamos que el espacio de acción es continuo; Para simplificar, supongamos que cada acción se elige de un intervalo: . En este contexto, la supermodularidad de implica que un aumento en la elección del jugador aumenta el pago marginal de la acción para todos los demás jugadores . Es decir, si algún jugador elige un valor más alto , todos los demás jugadores tienen un incentivo para aumentar sus opciones 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í. ^[2] Esta es la propiedad básica que subyace a los ejemplos de equilibrios múltiples en juegos de coordinación . ^[3] ${\displaystyle \,f}$ ${\displaystyle \,z_{i}}$ ${\displaystyle i\in {1,2,\dots ,N}}$ ${\displaystyle z_{i}\in [a,b]}$ ${\displaystyle \,f}$ ${\displaystyle \,i}$ ${\displaystyle \,z_{i}}$ ${\displaystyle df/dz_{j}}$ ${\displaystyle \,z_{j}}$ ${\displaystyle \,j}$ ${\displaystyle \,i}$ ${\displaystyle \,z_{i}}$ ${\displaystyle \,j}$ ${\displaystyle \,z_{j}}$

El caso opuesto de supermodularidad de , llamado submodularidad, corresponde a la situación de sustituibilidad estratégica . Un aumento de reduce el pago marginal de todas las elecciones de los demás jugadores , por lo que las estrategias son sustitutas. Es decir, si elige un valor más alto , otros jugadores tienen un incentivo para elegir uno más bajo . ${\displaystyle \,f}$ ${\displaystyle \,z_{i}}$ ${\displaystyle \,z_{j}}$ ${\displaystyle \,i}$ ${\displaystyle \,z_{i}}$ ${\displaystyle \,z_{j}}$

Por ejemplo, Bulow et al. Consideremos las interacciones de muchas empresas imperfectamente competitivas . Cuando un aumento de la producción de una empresa aumenta los ingresos marginales de las otras empresas, las decisiones de producción son complementos estratégicos. Cuando un aumento de la producción de una empresa reduce los ingresos marginales de las otras empresas, las decisiones de producción son sustitutos estratégicos.

Una función de utilidad supermodular suele estar relacionada con bienes complementarios . Sin embargo, esta opinión es discutida. ^[4]

Funciones submodulares de subconjuntos.

La supermodularidad y la submodularidad también se definen para funciones definidas sobre subconjuntos de un conjunto mayor. Intuitivamente, una función submodular sobre los subconjuntos demuestra "rendimientos decrecientes". Existen técnicas especializadas para optimizar funciones submodulares.

Sea S un conjunto finito. Una función es submodular si para cualquiera y , . Para la supermodularidad, la desigualdad se invierte. ${\displaystyle f\colon 2^{S}\to \mathbb {R} }$ ${\displaystyle A\subset B\subset S}$ ${\displaystyle x\in S\setminus B}$ ${\displaystyle f(A\cup \{x\})-f(A)\geq f(B\cup \{x\})-f(B)}$

La definición de submodularidad puede formularse de manera equivalente como

${\displaystyle f(A)+f(B)\geq f(A\cap B)+f(A\cup B)}$

para todos los subconjuntos A y B de S .

Los algoritmos de teoría y 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. ^[5]

Ver también

• Función pseudobooleana
• teorema de topkis
• Función de conjunto submodular
• superaditivo
• Funciones de utilidad sobre bienes indivisibles.

notas y referencias

1. La equivalencia entre la definición de supermodularidad y su formulación de cálculo a veces se denomina teorema de caracterización de Topkis . Véase Milgrom, Paul; Roberts, Juan (1990). "Racionalizabilidad, aprendizaje y equilibrio en juegos con complementariedades estratégicas". Econométrica . 58 (6): 1255-1277 [p. 1261]. doi :10.2307/2938316. JSTOR  2938316.
2. Bulow, Jeremy I.; Geanakoplos, John D.; Klemperer, Paul D. (1985). "Oligopolio multimercado: sustitutos y complementos estratégicos". Revista de Economía Política . 93 (3): 488–511. CiteSeerX 10.1.1.541.2368 . doi :10.1086/261312. S2CID  154872708. 
3. Cooper, Russell; Juan, Andrés (1988). "Coordinación de fallas de coordinación en modelos keynesianos" (PDF) . Revista Trimestral de Economía . 103 (3): 441–463. doi :10.2307/1885539. JSTOR  1885539.
4. Cámaras, Christopher P.; Echenique, Federico (2009). "Supermodularidad y preferencias". Revista de teoría económica . 144 (3): 1004. CiteSeerX 10.1.1.122.6861 . doi :10.1016/j.jet.2008.06.004. 
5. Goldengorin, Boris (1 de octubre de 2009). "Maximización de funciones submodulares: Teoría y algoritmos de enumeración". Revista europea de investigación operativa . 198 (1): 102–112. doi :10.1016/j.ejor.2008.08.022. ISSN  0377-2217.