Función supermodular - Supermodular function

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 diferenciable de forma continua, entonces la supermodularidad es equivalente a la condición

${\ Displaystyle {\ frac {\ parcial ^ {2} f} {\ parcial z_ {i} \, \ parcial z_ {j}}} \ geq 0 {\ mbox {para todos}} 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; Por simplicidad, supongamos que cada acción se elige entre un intervalo de: . En este contexto, la supermodularidad de implica que un aumento en la elección del jugador aumenta la recompensa marginal de la acción para todos los demás jugadores . Es decir, si algún jugador elige una más alta , 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í. Ésta es la propiedad básica que subyace a los ejemplos de equilibrios múltiples en los juegos de coordinación . ${\ 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 contrario de submodularidad de corresponde a la situación de sustituibilidad estratégica . Un aumento en reduce el beneficio marginal de todas las opciones de los demás jugadores , por lo que las estrategias son sustitutos. Es decir, si elige una más alta , otros jugadores tienen un incentivo para elegir una más baja . ${\ Displaystyle \, f}$${\ Displaystyle \, z_ {i}}$${\ Displaystyle \, z_ {j}}$${\ Displaystyle \, i}$${\ Displaystyle \, z_ {i}}$ ${\ Displaystyle \, z_ {j}}$

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

Funciones submodulares de subconjuntos

La supermodularidad y la submodularidad también se definen para funciones definidas sobre subconjuntos de un conjunto más grande. 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 por alguna y , . Para la supermodularidad, la desigualdad se invierte. ${\ Displaystyle f \ colon 2 ^ {S} \ to \ mathbb {R}}$${\ Displaystyle A \ subconjunto B \ subconjunto 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 .

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 B. Goldengorin. Revista europea de investigación operativa 198 (1): 102-112, DOI: 10.1016 / j.ejor.2008.08.022

Ver también

• Función pseudo-booleana
• Teorema de topkis
• Función de conjunto submodular
• Superaditivo
• Funciones de utilidad sobre bienes indivisibles

notas y referencias