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 una 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 los demás.

Consideremos un juego simétrico con una función de pago suave definida sobre las acciones de dos o más jugadores . Supongamos que el espacio de acciones 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 cualquier jugador elige un mayor , todos los demás jugadores tienen un incentivo para aumentar también sus elecciones. 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 son complementarias entre sí. ^[2] Esta es la propiedad básica que subyace a los ejemplos de equilibrios múltiples en los 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 la recompensa marginal de todas las elecciones de los demás jugadores , por lo que las estrategias son sustitutivas. Es decir, si elige una mayor , los demás jugadores tienen un incentivo para elegir una menor . ${\displaystyle \,f}$ ${\displaystyle \,z_{i}}$ ${\displaystyle \,z_{j}}$ ${\displaystyle \,i}$ ${\displaystyle \,z_{i}}$ ${\displaystyle \,z_{j}}$

Por ejemplo, Bulow et al. analizan las interacciones de muchas empresas imperfectamente competitivas . Cuando un aumento de la producción de una empresa eleva los ingresos marginales de las otras, 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, las decisiones de producción son sustitutos estratégicos.

Una función de utilidad supermodular suele estar relacionada con bienes complementarios . Sin embargo, esta visión es controvertida. ^[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 muestra "rendimientos decrecientes". Existen técnicas especializadas para optimizar funciones submodulares.

Sea S un conjunto finito. Una función es submodular si para cualquier 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 se puede formular 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 .

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. ^[5]

Véase también

• Función pseudo-booleana
• 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 se denomina a veces teorema de caracterización de Topkis . Véase Milgrom, Paul; Roberts, John (1990). "Racionalizabilidad, aprendizaje y equilibrio en juegos con complementariedades estratégicas". Econometrica . 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; John, Andrew (1988). "Coordinación de fallas de coordinación en los modelos keynesianos" (PDF) . Quarterly Journal of Economics . 103 (3): 441–463. doi :10.2307/1885539. JSTOR  1885539.
4. Chambers, 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.